首页 > 搜索 > 邻接矩阵的广度优先递归算法,深度优先算法和广度优先算法(基于邻接矩阵)

邻接矩阵的广度优先递归算法,深度优先算法和广度优先算法(基于邻接矩阵)

互联网 2020-10-20 08:55:07
在线算命,八字测算命理
1.写在前面

图的存储结构有两种:一种是基于二维数组的邻接矩阵表示法。

另一种是基于链表的的邻接表。

在邻接矩阵中,可以如下表示顶点和边连接关系:

说明:

将顶点对应为下标,根据横纵坐标将矩阵中的某一位置值设为1,表示两个顶点向联接。

图示表示的是无向图的邻接矩阵,从中我们可以发现它们的分布关于斜对角线对称。

我们在下面将要讨论的是下图的两种遍历方法(基于矩阵的):

 

我们已经说明了我们要用到的是邻接矩阵表示法,那么我首先要来构造图:

矩阵图的数据结构如下表示:

复制代码#define MaxVnum 50typedef double AdjMatrix[MaxVnum][MaxVnum]; //表示一个矩阵,用来存储顶点和边连接关系typedef struct {int vexnum,arcnum; //顶点的个数,边的个数AdjMatrix arcs; //图的邻接矩阵}Graph;复制代码

这样我们可以首先来创建上述图,为了方便,我们直接在代码中书写矩阵,而不用每次调试手动输入了

复制代码void CreateGraph(Graph &G){G.vexnum=8;G.arcnum=9;G.arcs[0][1]=1;G.arcs[0][2]=1;G.arcs[1][3]=1;G.arcs[1][4]=1;G.arcs[2][5]=1;G.arcs[2][6]=1;G.arcs[3][1]=1;G.arcs[3][7]=1;G.arcs[3][6]=1;G.arcs[4][1]=1;G.arcs[4][7]=1;G.arcs[5][2]=1;G.arcs[5][6]=1;G.arcs[5][5]=1;G.arcs[6][2]=1;G.arcs[6][5]=1;G.arcs[7][3]=1;G.arcs[7][4]=1;}复制代码

这样我们就已经完成了准备工作,我们可以正式来学习我们的两种遍历方式了。

2.深度优先遍历算法分析深度优先遍历

从图的某个顶点出发,访问图中的所有顶点,且使每个顶点仅被访问一次。这一过程叫做图的遍历。

深度优先搜索的思想:

①访问顶点v;②依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;③若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

比如:

在这里为了区分已经访问过的节点和没有访问过的节点,我们引入一个一维数组boolvisited[MaxVnum]用来表示与下标对应的顶点是否被访问过,

流程:☐ 首先输出 V1,标记V1的flag=true;☐ 获得V1的邻接边 [V2 V3],取出V2,标记V2的flag=true;☐ 获得V2的邻接边[V1 V4 V5],过滤掉已经flag的,取出V4,标记V4的flag=true;☐ 获得V4的邻接边[V2 V8],过滤掉已经flag的,取出V8,标记V8的flag=true;☐ 获得V8的邻接边[V4 V5],过滤掉已经flag的,取出V5,标记V5的flag=true;☐ 此时发现V5的所有邻接边都已经被flag了,所以需要回溯。(左边黑色虚线,回溯到V1,回溯就是下层递归结束往回返)☐ ☐ 回溯到V1,在前面取出的是V2,现在取出V3,标记V3的flag=true;☐ 获得V3的邻接边[V1 V6 V7],过滤掉已经flag的,取出V6,标记V6的flag=true;☐ 获得V6的邻接边[V3 V7],过滤掉已经flag的,取出V7,标记V7的flag=true;☐ 此时发现V7的所有邻接边都已经被flag了,所以需要回溯。(右边黑色虚线,回溯到V1,回溯就是下层递归结束往回返)

深度优先搜索的代码复制代码bool visited[MaxVnum];void DFS(Graph G,int v){visited[v]= true; //从V开始访问,flag它printf("%d",v);//打印出Vfor(int j=0;j
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多