图数据结构：顶点数组与边数组实现最小生成树

"用顶点数组和边数组存放顶点和边信息-数据结构课件" 在数据结构领域，图是一种非常重要的数据结构，用于表示对象之间的关系。在本课件中，主要讨论了如何用顶点数组和边数组来存储图的信息，并介绍了一种特定的算法来处理这些数据。 首先，图（Graph）由两个集合构成，一个是顶点集合（V(G)），另一个是边集合（E(G)）。顶点集合包含若干个顶点，而边集合则包含顶点之间的连接关系，可以是无序对或有序对，具体取决于图是有向还是无向。在有向图中，边是有方向的，表示从一个顶点（弧尾）指向另一个顶点（弧头），而在无向图中，边没有方向，两个顶点之间相互邻接。 在图的表示中，我们使用顶点结点（VEX）和边结点（EDGE）的数据结构。顶点结点包含两个字段，一个是顶点的信息（data），另一个是顶点的标记（jihe）。边结点包含四个字段，分别是边依附的两个顶点（vexh和vext），边的权值（weight），以及一个标志域（flag）。标志域在算法中用来标识边的状态，如是否已被选择等。 描述中的算法似乎是用于寻找图中的连通分量，例如构建最小生成树。初始时，每个顶点的标记（jihe）是唯一的，每条边的flag设为0。然后，选取权值最小且flag为0的边。如果这条边连接的两个顶点的标记不同，即它们不在同一个连通分量中，就将该边的flag设为1，将这两个顶点以及它们所在集合的所有顶点的标记设为相同，表明它们属于同一连通分量。如果两个顶点的标记相同，意味着它们已经在同一连通分量中，那么这条边被标记为2，即不再考虑。这个过程持续进行，直到选取了n-1条边，确保了图中的所有顶点都被连接起来。 无向图的边是无序对，例如（v, w）表示顶点v和w之间的边，而有向图的边是有序对，如<v, w>，表示从v到w的方向。有向完全图是指每个顶点与其他所有顶点之间都有两条方向相反的弧，而无向完全图则是每个顶点与其他所有顶点都直接相连，每对顶点之间只有一条边。 权（weight）是与图的边或弧相关的数值，它可以代表各种含义，如距离、时间、成本等，具体取决于应用情境。例如，在城市交通网络中，边的权值可以表示路线的长度或交通等级；在工程进度图中，权值可能表示项目之间的依赖关系，如时间间隔。 这个课件涵盖了图的基本概念、顶点和边的表示方法，以及处理图的一种特定算法。通过学习这部分内容，可以更好地理解和操作图数据结构，解决实际问题。