图的深度优先遍历的实现C/C++ DFS
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; #define MAX 100 #define LENGTH(a) (sizeof(a) / sizeof(a[0])) int visited[MAX]; typedef struct _graph{ char vexs[MAX]; int vexnum; int edgnum; int matrix[MAX][MAX]; }Graph，*PGgraph; static int get_position(Graph g， char ch){ for(int i = 0;i<g.vexnum;i++){ if(ch == g.vexs[i]) return i; } return -1; } static char read_char(){ char ch; while(!((((ch)>='a') && ((ch)<='z')) || (((ch)>='A') && ((ch)<='Z')))) ch = getchar(); return ch; } Graph creat_graph(){ char c1，c2; int v，e; int p1，p2; Graph pG; cout<<"input number of vex > "; cin>>v; cout<<"input number of edge > "; cin>>e; //memset(pG，0，sizeof(Graph)); pG.vexnum = v; pG.edgnum = e; //Initialize vexs for(int i=0; i<pG.vexnum;i++){ //pG.vexs[i] = read_char(); cin>>pG.vexs[i] ; } //Initialize edges for(int i = 0;i < pG.edgnum; i++){ //c1 = read_char(); //c2 = read_char(); cin>>c1>>c2; cout<<c1<<c2<<endl; p1 = get_position(pG， c1); p2 = get_position(pG， c2); pG.matrix[p1][p2] = 1; pG.matrix[p2][p1] = 1; } return pG; } static int next_vertex(Graph g， int v，int w){ if(v<0 || v>g.vexnum-1|| w<0 || w>(g.vexnum-1)) return -1; for(int i=w+1; i < g.vexnum; i++){ if(g.matrix[v][i] == 1) return i; } return -1; } static int first_vertex(Graph g， int v){ if(v<0 || v>g.vexnum-1) return -1; for(int i=0; i < g.vexnum; i++){ if(g.matrix[v][i] == 1) return i; } return -1; } void DFS(Graph g， int i){ if(visited[i] == 0){ visited[i] = 1; cout<<g.vexs[i]<<" "; } int w = first_vertex(g，i); for(;w>=0; w = next_vertex(g，i，w)){ if(!visited[w]) DFS(g，w); } } int main(int argc， const char * argv[]) { for(int i = 0; i < MAX; i++){ visited[i] = 0; } Graph g; g= creat_graph(); for(int i = 0; i< g.vexnum; i++){ if(!visited[i]) DFS(g，i); } return 0; }
