图的遍历
图的遍历有两种遍历方式：深度优先遍历(depth-first search)和广度优先遍历(breadth-first search)。
1.深度优先遍历
基本思想：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。
如下图中的一个无向图
其深度优先遍历得到的序列为：
0->1->3->7->4->2->5->6
2.广度优先遍历
基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。
如上面图中
其广度优先遍历得到的序列为：
0->1->2->3->4->5->6->7
实现代码
#include<iostream> #include<queue> #include<stack> #include<stdlib.h> #define MAX 100 using namespace std; typedef struct { int edges[MAX][MAX]; //邻接矩阵 int n; //顶点数 int e; //边数 }MGraph; bool visited[MAX]; //标记顶点是否被访问过 void creatMGraph(MGraph &G) //用引用作参数 { int i,j; int s,t; //存储顶点编号 int v; //存储边的权值 for(i=0;i<G.n;i++) //初始化 { for(j=0;j<G.n;j++) { G.edges[i][j]=0; } visited[i]=false; } for(i=0;i<G.e;i++) //对矩阵相邻的边赋权值 { scanf("%d %d %d",&s,&t,&v); //输入边的顶点编号以及权值 G.edges[s][t]=v; } } void DFS(MGraph G,int v) //深度优先搜索 { int i; printf("%d ",v); //访问结点v visited[v]=true; for(i=0;i<G.n;i++) //访问与v相邻的未被访问过的结点 { if(G.edges[v][i]!=0&&visited[i]==false) { DFS(G,i); } } } void DFS1(MGraph G,int v) //非递归实现 { stack<int> s; printf("%d ",v); //访问初始结点 visited[v]=true; s.push(v); //入栈 while(!s.empty()) { int i,j; i=s.top(); //取栈顶顶点 for(j=0;j<G.n;j++) //访问与顶点i相邻的顶点 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); //访问 visited[j]=true; s.push(j); //访问完后入栈 break; //找到一个相邻未访问的顶点，访问之后则跳出循环 } } if(j==G.n) //如果与i相邻的顶点都被访问过，则将顶点i出栈 s.pop(); } } void BFS(MGraph G,int v) //广度优先搜索 { queue<int> Q; //STL模板中的queue printf("%d ",v); visited[v]=true; Q.push(v); while(!Q.empty()) { int i,j; i=Q.front(); //取队首顶点 Q.pop(); for(j=0;j<G.n;j++) //广度遍历 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); visited[j]=true; Q.push(j); } } } } int main(void) { int n,e; //建立的图的顶点数和边数 while(scanf("%d %d",&n,&e)==2&&n>0) { MGraph G; G.n=n; G.e=e; creatMGraph(G); DFS(G,0); printf("\n"); // DFS1(G,0); // printf("\n"); // BFS(G,0); // printf("\n"); } return 0; }
如需转载自行联系原作者
