clwn.net
当前位置:首页 >> 邻接矩阵深度优先遍历 >>

邻接矩阵深度优先遍历

//从第v个顶点出发递归的深度优先遍历图G int w; visited[v]=TURE; //#include<stdio.h> #define Max 20 #define True 1 #define False 0

你是要代码?先由邻接矩阵把图画出来呀.深度优先遍历使用递归,对于一个结点,递归访问他没有访问过的相邻节点.就像走迷宫一样,已知走到无路可走,然后回溯,找下一个路口.广度优先遍历使用队列,当一个节点出队的时候,把他的相邻未访问节点入队.就像重度近视的人眼镜掉了找眼镜,会先找自己最近的一圈,然后再一点点扩展.每种遍历使用vis数组标记,保证每个节点只访问一遍.

深度优先遍历,先访问第一行不为0的点为1,让后转至1行,找到第二个不为0 的点,3,转至3所在的行,同理找到4,再找到2 .2行中的3与前面重复,无其他不为0的点,剩下的点选5,再找到5行中不为0的点6.深度优先遍历的特点是遍历与这个点相邻的点,了解了邻接表的特点后就会觉得简单了.纯手打,.

程序如下,编译环境vs2005和dev-c++,将图中顶点数和边线数组改为实际值./* 图的深度优先遍历 */#include #include struct node /* 图顶点结构定义 */{ int vertex; /* 顶点数据信息 */ struct node *nextnode; /* 指下一顶点的指标 */};typedef

深度优先,找到与顶点0直接相连的结点,由邻接矩阵知道是顶点1(多个相邻节点取第一个找到的未遍历到的结点),然后再在邻接矩阵中找与顶点1直接相连的结点,得到顶点3.相

设有n个点,e条边 邻接矩阵:矩阵包含n^2个元素,在算法中,共n个顶点,对每个顶点都要遍历n次,所以时间复杂度为O(n^2) 邻接表:包含n个头结点和e个表结点,算法中对所有结点都要遍历一次,所以时间复杂度为 O(n+e) 顺便,对于广度优先算法的时间复杂度,也是这样

如果邻接矩阵的顶点与下标已经固定,起点也已经固定,则深度优先遍历唯一,因为这是程序的执行结果,不是人在上面看遍历的方法就是如同程序执行一样,在每个顶点的行上往后扫描,如果有一个没访问,就继续深度优先遍历就这个图的邻接矩阵珐粹溉诔防达狮惮饯而言,从B出发深度优先遍历的结果就是BECFDA

你能不能给贴上一个深度遍历错误的用例?你这个输入用例的结果就是1,2,3,4现在能看出来的就是这个了,int LocateVex (MGraph G,VertexType v){ int i; for(i = 0;i<G.vexnum;i++) if(G.vexs[i] == v){ //这里应该是等于v,而不是等于i return i; } return -1;}

深度优先就是顺着节点的孩子往下搜索,直到没有孩子节点时才搜索他的兄弟节点广度优先就是把该节点的兄弟先搜索完了再往孩子节点搜索

E.因为是深度优先,找到与顶点0直接相连的结点,由邻接矩阵知道是顶点1(多个相邻节点取第一个找到的未遍历到的结点),然后再在邻接矩阵中找与顶点1直接相连的结点,得到顶点3.相同方法找到后续结点为:顶点4,顶点2.因为顶点2的相连结点都已被遍历,所以退回到顶点4继续遍历,遍历到顶点5,然后是顶点6

网站首页 | 网站地图
All rights reserved Powered by www.clwn.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com