图的数据结构：数组与链表表示及转换

本文主要介绍了图的两种常见数据结构表示：数组表示和链表表示，并提供了在C++中实现这两种表示法以及它们之间转换的方法。此外，还涉及到图的最短路径问题。 在计算机科学中，图是一种重要的数据结构，用于表示对象之间的关系。图由顶点（vertices）和边（edges）组成，可以用来模拟各种复杂的关系，如网络、交通路线等。在实际应用中，图通常有以下两种常见的存储方式： 1. **数组表示法（Adjacency Matrix）**： 在数组表示法中，我们使用一个二维数组来存储图中的边。数组的行和列对应图中的顶点，数组的每个元素表示对应两个顶点之间是否存在边以及边的权重。如果顶点i和j之间存在边，那么`arcs[i][j].adj`将存储边的权重；若不存在边，则通常设置为一个特殊的值，如本文中的`$2000000000`表示无边。 2. **链表表示法（Adjacency List）**： 链表表示法更加节省空间，特别是当图稀疏时（边的数量远小于顶点数量的平方）。每个顶点都有一个链表，链表中的节点代表与该顶点相连的所有边及其权重。这种表示法不需要为不存在的边分配存储空间。 在上述代码中，`MGraph`结构体定义了图的数组表示，包含顶点数组`vexs`和邻接矩阵`arcs`，以及顶点数`vexnum`和边数`arcnum`。`locateVexMGraph`函数用于查找顶点在数组中的位置。`createMGraph`函数读取文本文件中的数据，构建图的数组表示。 为了从数组表示法转换为链表表示法，我们需要为每个顶点创建一个链表，并将邻接矩阵中的非空元素（表示有边的元素）添加到相应的链表中。相反，从链表表示法转换为数组表示法，需要遍历所有顶点的链表，根据链表中的边填充邻接矩阵。 最短路径问题在图中非常重要，解决这个问题的算法包括Dijkstra算法和Bellman-Ford算法等。这些算法可以找到从一个源顶点到其他所有顶点的最短路径，通常在数组表示法或链表表示法中都能实现。 理解并能灵活运用图的数组表示和链表表示对于解决图论问题至关重要。它们各有优缺点，选择哪种表示法取决于具体问题的需求，如空间效率、查找速度等。熟练掌握这两种表示法的创建、转换和操作，对于处理图相关的算法和问题具有极大的帮助。