数据结构实现图的遍历算法(图的遍历的实现数据结构课程设计)

导语：「数据结构」 图的表示及遍历方式

图的定义

图由一些节点构成的集合，其中节点之间使用边进行连接，如果边是有方向的称为有向图，否则称为无向图。

图的表示方式邻接表

1. 数组存储图的结点；

2. 数组中的每个元素引出一个单链表，表示与此结点相连的结点。

邻接矩阵

1. 二维矩阵中的行和列代表图中的结点；

2. 矩阵中的元素代表两个结点是否相连：假如A[i,j]为1，表示第结点i与结点j是相连的，否则结点i与结点j是不相连的。

图的遍历深度优先（DFS）

基本思路：

1. 创建已访问结点数组E；

2. 选择一个结点N，访问该结点，并将其加入到数组E；

3. 访问与其相连的第一个未被访问过的结点；如果相连的结点全部已访问过，则退回到上一个结点，并重复步骤3，直到所有的结点都被访问过。

广度优先（BFS）

基本思路：

1. 创建已访问结点数组E；

2. 选择一个结点N，访问该结点，并将其加入到数组E；

3. 顺序访问与其相连的所有的结点；访问完毕后从相连的结点中选择一个并开始访问与其相连的所有结点，重复步骤3，直到所有的结点都被访问过。

本文内容由快快网络小碧创作整理编辑！