图的遍历操作实验报告

1、实验3:图的遍历操作一.目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表的存储结构，建立图形；掌握DFS和BFS在图形上的遍历操作；了解图形结构在人工智能、工程等领域的广泛应用。二、要求利用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS运算。第三，DFS和BFS的基本思想深度优先搜索法DFS的基本思想是：从图G中的一个顶点Vo开始，先访问Vo，然后选择一个与Vo相邻但未被访问过的顶点Vi，再选择一个与Vi相邻但未被Vi访问过的顶点Vj，依次继续。如果当前访问过的顶点的所有相邻顶点都已被访问过，则返回到访问过的顶点序列中拥有未被访问过的相邻顶点的最后一个顶点W，并以相

2、同的方式从W向前遍历。直到图中的所有顶点都被访问。广度优先搜索BFS的基本思想是：从图G中的一个顶点Vo开始，先访问Vo，然后访问与Vo相邻的所有未访问的顶点V1，V2，Vt；然后访问V2 V1附近的所有顶点，Vt和未依次访问。这种情况一直持续到访问了图中的所有顶点。四.示例程序1.作为存储结构邻接矩阵的程序实例#包括“stdio.h”#包括 stdlib.h #定义最大顶点数100 /定义最大顶点数typedef结构char vexsMaxVertexNum；/顶点表int边MaxVertexNumMaxVertexNum；/邻接矩阵，可视为边表int n，e；/图中顶点数n和边数e MGr

3、aph/由邻接矩阵表示的图的类型/=建立邻接矩阵=无效创建图形(图形*G)I，j，k；char a；printf(“输入顶点数(n)和边长(e):”)；扫描(“%d，%d”，G-n，G-e)；/输入顶点和边的数量scanf(“% c”，a)；printf(“输入顶点字符串：”)；对于(I=0；在；在(I)scanf(“% c”，a)；G-vexsi=a。/读入顶点信息并创建顶点表对于(I=0；在；在(I)对于(j=0；jn；j)g边Ij=0；/初始化邻接矩阵printf(“输入边，创建邻接矩阵 n”)；对于(k=0；ke；K) /读入E边并建立邻接矩阵scanf(“% d % d”，I，j)；

4、/输入边的顶点数(Vi，Vj)g边Ij=1；g边jI=1；/如果是无向图，矩阵是对称的；如果建立了有向图，请删除此语句/=定义标志向量，它是一个全局变量=typedef枚举FALSE，TRUE布尔值；布尔访问了MaxVertexNum；/=DFS:深度优先遍历的递归算法=无效DFSM(图形*G，国际)/对邻接矩阵表示的图g执行DFS搜索，邻接矩阵是0，1矩阵，从Vi开始int j；printf(“% c”，G-vexsI)；/访问vertex Vi已访问I=真；/设置访问标志对于(j=0；jn；J) /依次搜索Vi的相邻点如果(G-边ij=1！拜访j)DFSM(G，j)；/(Vi，Vj)E和V

5、j尚未被访问，因此Vj是一个新的起点无效DFS(图形*G)int I；对于(I=0；在；在(I)拜访I=FALSE；/标志向量初始化对于(I=0；在；在(I)如果(！已访问i) /Vi未访问DFSM(G，I)；/以Vi为源点开始DFS搜索/=BFS:广度优先遍历=空虚的BFS/以Vk为源点的邻接矩阵表示的图G的广度优先搜索int i，j，f=0，r=0；int CQMaxVertexNum；/定义队列对于(I=0；在；在(I)拜访I=FALSE；/标志向量初始化对于(I=0；在；在(I)CQI=-1；/队列初始化printf(“% c”，G-vexsk)；/访问源点Vk访问次数k=真；cqr=

6、k。/Vk已经访问并加入了团队。请注意，它实际上是在排队它的序列号同时(cqf!=-1) /如果团队不为空，则执行I=CQf；f=f1；/Vf离开团队对于(j=0；jn；J) /连续Vi的相邻点Vj如果(G-边ij=1！拜访j) /Vj未访问printf(% c ，G-vexsj)；/访问电视综艺节目主持人已访问j=真；r=R1；CQr=j；/访问过电视综艺节目主持人入队/=main=void main()国际；g；g=(MgRaph *)malloc(sizeof(MgRaph)；/为图G申请内存空间创建图表(G)；/建立邻接矩阵printf(打印图表外勤部：)；外勤部(G)；/深度优先遍历

7、printf( n )；printf(打印图表BFS :”)；BFS(G，3)；/以序号为3的顶点开始广度优先遍历printf( n )；执行顺序：V6V4V5V7V2V3第五颅神经的眼支V0Vo图G的示例输入顶点数(n)和边数(e): 8，9输入顶点字符串： 01234567输入边，创建邻接矩阵0 10 21 31 42 52 63 74 75 6打印图表DFS:01374256打印图表BFS:317042562.邻接链表作为存储结构程序示例#包括 stdio.h #包括stdlib.h #定义MaxVertexNum 50 /定义最大顶点数typedef结构节点 /边表结点int adjv

8、ex/邻接点域结构节点*下一步；/链域边缘节点；typedef结构vnode /顶点表结点茶顶点；/顶点域EdgeNode * firstedge/边表头指针顶点节点；typedef VertexNode AdjListMaxVertexNum；/AdjList是邻接表类型typedef结构AdjList adjlist ./邻接表int n，e；/图中当前顶点数和边数 ALGraph/图类型/=建立图的邻接表=空创建图(ALGraph *G)I，j，k；char a；边缘节点；/定义边表结点printf(输入顶点数(n)和边长(e):”)；扫描(%d，%d ，G-n，G-e)；/读入顶点数和

9、边数scanf(% c ，a)；printf(输入顶点字符串：”)；对于(1=0；在；在i ) /建立边表scanf(% c ，a)；G-adjlisti.顶点=a。/读入顶点信息G-adjlisti.firstedge=空；/边表置为空表printf(输入边，创建邻接列表 n )；对于(k=0；ke；k ) /建立边表扫描( % d % d ，I，j)；/读入边(Vi，Vj)的顶点对序号s=(EdgeNode *)malloc(大小为(EdgeNode)；/生成边表结点s-adj vex=j；/邻接点序号为js-next=G-adjlisti.firstedgeG-adjlisti.第一边=

10、s；/将新结点*S插入顶点视觉识别系统的边表头部s=(EdgeNode *)malloc(大小为(EdgeNode)；我；/邻接点序号为is-next=G-adjlistj.firstedgeG-adjlistj.第一边=s；/将新结点*S插入顶点电视综艺节目主持人的边表头部/=定义标志向量，为全局变量=typedef枚举假，真布尔值；布尔访问了MaxVertexNum；/=DFS:深度优先遍历的递归算法=无效DFSM /以视觉识别系统为出发点对邻接链表表示的图G进行深度优先搜索搜索边缘节点* p；printf(% c ，G-adjlisti).顶点)；/访问顶点视觉识别系统已访问一=真；/标记视觉识别系统已访问p=G-adjlisti.firstedge/取视觉识别系统边表的头指针而(p) /依次搜索视觉识别系统的邻接点Vj，这里j=p-adjvex如果(！已访问p-adjvex) /若电视综艺节目主持人尚未被访问DFSM；/则以电视综艺节目主持人为出发点向纵深搜索p=p-下一个；/找视觉识别系统的