且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事
您所在的位置：首页 > 图的深度优先遍历DFS(邻接矩阵表示法)

图的深度优先遍历DFS(邻接矩阵表示法)

更新时间：2022-08-12 17:56:16

1.前言

期末复习算法，第三章讲到了图，所以想将课本中的算法实现。当写完代码的时候才发现这样的复习效率太低了，看书复习是复习，写代码是写代码。不过写完以后还是有点成就感的。

2.参考文献

http://blog.csdn.net/lengyuhong/archive/2010/01/06/5145100.aspx

3.代码实现

[c-sharp] view plaincopyprint?
  1. #include<iostream>  
  2. #include<malloc.h>  
  3. using namespace std;  
  4.  
  5. #define maxNum 100 //定义邻接举证的最大定点数  
  6. int visited[maxNum];//通过visited数组来标记这个顶点是否被访问过，0表示未被访问，1表示被访问  
  7.   
  8. //图的邻接矩阵表示结构  
  9. typedef struct  
  10. {  
  11.     char v[maxNum];//图的顶点信息  
  12.     int e[maxNum][maxNum];//图的顶点信息  
  13.     int vNum;//顶点个数  
  14.     int eNum;//边的个数  
  15. }graph;  
  16.   
  17. void createGraph(graph *g);//创建图g  
  18. void DFS(graph *g);//深度优先遍历图g  
  19.   
  20. void dfs(graph *g,int i)  
  21. {  
  22.     //cout<<"顶点"<<g->v[i]<<"已经被访问"<<endl;  
  23.     cout<<"顶点"<<i<<"已经被访问"<<endl;  
  24.     visited[i]=1;//标记顶点i被访问  
  25.     for(int j=0;j<g->vNum;j++)  
  26.     {  
  27.         if(g->e[i][j]!=0&&visited[j]==0)  
  28.             dfs(g,j);  
  29.     }  
  30. }  
  31.   
  32. void DFS(graph *g)  
  33. {  
  34.     int i;  
  35.     //初始化visited数组，表示一开始所有顶点都未被访问过  
  36.     for(i=0;i<g->vNum;i++)  
  37.         visited[i]=0;  
  38.     //深度优先搜索  
  39.     for(i=0;i<g->vNum;i++)  
  40.         if(visited[i]==0)//如果这个顶点为被访问过，则从i顶点出发进行深度优先遍历  
  41.             dfs(g,i);  
  42. }  
  43.   
  44. void createGraph(graph *g)//创建图g  
  45. {  
  46.     cout<<"正在创建无向图..."<<endl;  
  47.     cout<<"请输入顶点个数vNum:";  
  48.     cin>>g->vNum;  
  49.     cout<<"请输入边的个数eNum:";  
  50.     cin>>g->eNum;  
  51.     int i,j;  
  52.   
  53.     //输入顶点信息  
  54.     //cout<<"请输入顶点信息："<<endl;  
  55.     //for(i=0;i<g->vNum;i++)  
  56.     //  cin>>g->v[i];  
  57.   
  58.     //初始画图g  
  59.     for(i=0;i<g->vNum;i++)  
  60.         for(j=0;j<g->vNum;j++)  
  61.             g->e[i][j]=0;  
  62.   
  63.     //输入边的情况  
  64.     cout<<"请输入边的头和尾"<<endl;  
  65.     for(int k=0;k<g->eNum;k++)  
  66.     {  
  67.         cin>>i>>j;  
  68.         g->e[i][j]=1;  
  69.         g->e[j][i]=1;  
  70.     }  
  71. }  
  72.   
  73. int main()  
  74. {  
  75.     graph *g;  
  76.     g=(graph*)malloc(sizeof(graph));  
  77.     createGraph(g);  
  78.     DFS(g);  
  79.     int i;  
  80.     cin>>i;  
  81.     return 0;  
  82. }  
  83.   
  84. /* 
  85. 输入： 
  86. 正在创建无向图... 
  87. 请输入顶点个数vNum:10 
  88. 请输入边的个数eNum:9 
  89. 请输入边的头和尾 
  90. 0 1 
  91. 0 3 
  92. 1 4 
  93. 1 5 
  94. 3 6 
  95. 4 8 
  96. 5 2 
  97. 6 7 
  98. 8 9 
  99. */  



本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/06/11/2297009.html，如需转载请自行联系原作者

上一篇 : ：经历2个月滞后，Win10占Windows设备份额攀升25%以上下一篇 : 三星证实！7千万美元收购美国QD Vision

相关阅读

推荐文章

网站首页网站地图Copyright © 2021-2022 且购网

免责声明：本站文章部分来源于互联网,如有侵权请联系站长,我们将在72小时内删除。