无向图存储与深度优先遍历算法解析

本文主要介绍了无向图的边集数组存储算法和图的深度优先遍历，通过具体的实例展示了如何创建图的存储结构，并探讨了邻接矩阵和邻接表两种不同的图表示方法。 在图的存储方面，无向图的边集数组是一种常见的表示方法。文中定义了一个名为`node`的记录类型，包含了三个字段：`Fr`表示边的起点，`en`表示边的终点，`Wt`表示边的权重。变量`x`是一个数组，用于存储这些`node`类型的元素，从而构成边集数组。`creat3(GE)`过程用于创建边集数组，通过循环读取输入的顶点对和权重来填充数组。 接着，文章提到了图的深度优先遍历（DFS），这是一种探索图的方法，从一个给定的起点开始，沿着边向下深入，直到访问所有可达的顶点。在无向图中，从一个顶点出发，可以沿着边访问与其相邻的所有未访问过的顶点，然后继续这个过程，直到图中所有顶点都被访问。 接下来，文章回顾了图的基本知识，包括图的定义和两种常见存储方式：邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中的元素表示顶点之间的连接关系。对于无向图，如果两个顶点之间有一条边，矩阵中的对应元素为1；对于有向图，只有起点到终点的边存在时，元素为1。邻接矩阵适用于表示稠密图，即边的数量接近于顶点数量的平方。 邻接表则是另一种高效的表示方式，尤其适合稀疏图。每个顶点对应一个单链表，链表中的节点代表与该顶点相连的其他顶点。这样，每个顶点的邻接表仅包含与其相邻的顶点，节省了存储空间。邻接表结构可以更高效地进行深度优先遍历，因为只需遍历每个顶点的邻接表即可。 在邻接矩阵和邻接表的创建算法中，分别给出了示例代码。邻接矩阵的创建是通过初始化一个全零的矩阵，然后根据输入的边信息设置对应位置的元素为1。而邻接表的创建则是为每个顶点创建一个链表，并将与之相邻的顶点添加到对应的链表中。 这篇文章提供了无向图的存储方法以及图的深度优先遍历的理解，对于理解图论基础和图的算法实现具有重要意义。无论是邻接矩阵还是邻接表，都有其适用的场景，选择哪种存储方式取决于图的具体特性和问题的需求。深度优先遍历则是一种重要的图遍历策略，在许多算法中都有应用，如寻找连通分量、判断图的环路等。