图的深度优先遍历DFS(邻接矩阵表示法)-阿里云开发者社区

开发者社区> 嗯哼9925> 正文

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

简介:
+关注继续查看

1.前言

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

2.参考文献

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

3.代码实现

  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,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10077 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10883 0
【算法导论】图的深度优先搜索遍历(DFS)
        关于图的存储在上一篇文章中已经讲述,在这里不在赘述。下面我们介绍图的深度优先搜索遍历(DFS)。         深度优先搜索遍历实在访问了顶点vi后,访问vi的一个邻接点vj;访问vj之后,又访问vj的一个邻接点,依次类推,尽可能向纵深方向搜索,所以称为深度优先搜索遍历。
1167 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13884 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11818 0
深度优先遍历DFS用邻接表表示的图
深度优先遍历用邻接表表示的图 DFS the Adjacency List Graph eryar@163.com 一、简介 创建了图之后,我们希望从图中某个顶点出发访遍图中其余顶点,且使每个顶点仅被访问一次。
887 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
7496 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
22400 0
+关注
4716
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载