C语言数据结构图的基本操作及遍历（存储结构为邻接矩阵）请查看：http://www.omegaxyz.com/2017/05/17/graphofds2/
邻接表的存储结构遍历请看
http://www.omegaxyz.com/2017/05/16/graphofds/
下面给出C++STL实现图的深度与广度优先遍历（BFS&DFS）
其中BFS需要用栈，DFS需要用队列
下面算法所用的图为：
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
//Author: Xu Yi //www.omegaxyz.com #include<iostream> #include<stack> #include<queue> #include<cstring> #define MAX 100 using namespace std; stack<int> BFS_Stack; queue<int> DFS_Queue; int G[MAX][MAX]; int visit[MAX]; int V,E; void BFS(int s){ cout<<"BFS"<<endl; int i,j,node; memset(visit,0,sizeof(visit)); BFS_Stack.push(s); while(!BFS_Stack.empty()){ node=BFS_Stack.top(); BFS_Stack.pop(); if(visit[node])continue; visit[node]=1; cout<<node<<"-->"; for(i=0;i<V;i++){ if(G[node][i])BFS_Stack.push(i); } } cout<<"NULL"<<endl; } void DFS(int s){ cout<<"DFS"<<endl; int i,j,node; memset(visit,0,sizeof(visit)); DFS_Queue.push(s); while(!DFS_Queue.empty()){ node=DFS_Queue.front(); DFS_Queue.pop(); if(visit[node])continue; visit[node]=1; cout<<node<<"-->"; for(i=0;i<V;i++) if(G[i][node])DFS_Queue.push(i); for(j=0;j<V;j++) if(G[node][j])DFS_Queue.push(j); } cout<<"NULL"<<endl; } //////////////////////////////// int main() { memset(visit,0,sizeof(visit)); memset(predecessor,0,sizeof(predecessor)); memset(G,0,sizeof(G)); G[0][1]=1; G[1][2]=1; G[1][3]=1; G[3][5]=1; G[3][4]=1; G[3][7]=1; G[4][6]=1; G[7][4]=1; V=8; BFS(0); DFS(0); cout<<endl; return 0; } |
结果:
DFS是深度优先，BFS是广度优先
抱歉哈，当时未检查，请见谅
61行memset(predecessor,0,sizeof(predecessor));得删掉
为啥
predecessor这个没调用吧？