如何用C语言实现图的深度优先遍历和广度优先遍历算法？

本文共计1972个文字，预计阅读时间需要8分钟。

目录+图的定义+图的相关术语+图的创建（邻接矩阵）—结构体+图的创建（邻接矩阵）—邻接矩阵的创建+图的创建（邻接表）—结构体+图的创建（邻接表）—邻接表的创建+对邻接矩阵进行深度优先遍历

目录

• 图的定义
• 图的相关术语
• 图的创建(邻接矩阵)---结构体
• 图的创建(邻接矩阵)---邻接矩阵的创建
• 图的创建(邻接表)---结构体
• 图的创建(邻接表)---邻接表的创建
• 对邻接矩阵进行深度优先遍历
• 对邻接矩阵进行广度优先遍历
• 对邻接表进行深度优先遍历
• 对邻接表进行广度优先遍历
• 整体代码
• 结果展示

图的定义

图由顶点集V(G)和边集E(G)组成，记为G=(V,E)。其中E(G)是边的有限集合，边是顶点的无序对（无向图）或有序对（有向图）。对于有向图来说，E(G)是有向边（也称弧(Arc)）的有限集合，弧是顶点的有序对，记为<v,w>，v、w是顶点，v为弧尾（箭头根部），w为弧头（箭头处）。对于无向图来说，E(G)是边的有限集合，边是顶点的无序对，记为(v, w)或者(w, v)，并且(v, w)=(w,v)。

图的相关术语

①顶点(Vertex)：图中的数据元素。

②顶点v的度：与v相关联的边的数目；

③顶点v的出度：以v为起点有向边数；

④顶点v的入度：以v为终点有向边数。

⑤边：顶点之间的逻辑关系用边来表示，边集可以是空的。