图的遍历

图的遍历

图的遍历：深度优先遍历，广度（宽度）优先遍历。这两种遍历方式都是基于搜索的DFS和BFS发展来的。时间复杂度相同，但是访问的次序不同。

例子：

深度优先遍历：

#include #includeusing namespace std;const int maxn=101,maxm=141; int head[maxn]; struct node{ int to,w,next; }edge[maxm]; bool vis[maxm]; //1-->visitedvoid dfs(int x){ vis[x]=1; printf("%d\n",x); for(int i=head[x];i>0;i=edge[i].next){ if(!vis[edge[i].to])dfs(edge[i].to); //递归--回溯 }}int main(int argc, char *argv[]) { freopen("cin.txt","r",stdin); freopen("cout.txt","w",stdout); int n,m,k,i; cin>>n>>m; //规模以及实际的边数。例子中数据是8,12. for(i=0;i

结果：

6 7 4 3 2 1 5 8

广度（宽度）优先遍历：

#include #includeusing namespace std;const int maxn=101,maxm=141; int head[maxn]; struct node{ int to,w,next; }edge[maxm]; bool vis[maxm]; //1-->visitedvoid bfs(int x){ int que[maxn],iq=0; que[iq++]=x; vis[x]=1; int i,j; for(i=0;i0;j=edge[j].next){ if(!vis[edge[j].to]){ que[iq++]=edge[j].to; vis[edge[j].to]=1; } } }}int main(int argc, char *argv[]) { freopen("cin.txt","r",stdin); freopen("cout.txt","w",stdout); int n,m,k,i; cin>>n>>m; //规模以及实际的边数。例子中数据是8,12. for(i=0;i

结果：

6 7 5 1 4 8 2 3

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。