图数据结构详解：顶点、边与连通性

"这份资源是长江大学数据结构课程的PPT讲义，专注于图这一重要的数据结构进行详细讲解，适合初学者理解学习。" 在计算机科学中，数据结构是存储和组织数据的一种方式，它对算法的设计和实现起着至关重要的作用。图是一种复杂的数据结构，用于表示对象之间的关系或连接。本讲义详细介绍了图的基本概念和术语。 首先，图（Graph）由两个集合构成，一个是顶点集V(G)，另一个是边集E(G)，记作G=(V,E)。顶点集是非空有限集，而边集可以包含无序对或有序对，取决于图是有向还是无向。 1. **有向图**：在有向图中，边是有方向的，表示为弧<v,w>，其中v是弧尾，w是弧头。例如，图G1中，边集E(G1)包含了若干个这样的有序对。 2. **无向图**：无向图的边是无序对，如(v,w)或(w,v)，意味着边没有方向。图G2是一个无向图的例子，边集E(G2)包含了多个无序对。 3. **有向完备图**：如果有n个顶点，那么有向完备图中的边数最多为n(n-1)，即每对不同的顶点之间都有一条有向边。 4. **无向完备图**：无向完备图的边数最多为n(n-1)/2，所有可能的顶点对之间都有一条无向边。 5. **权**：在图中，边或弧可能关联有一个数值，称为权，常用于表示某种属性或代价。 6. **网**：带权的图被称为网，权可以表示距离、成本、流量等。 7. **子图**：如果一个图G'的顶点集和边集分别是G的子集，则G'是G的子图。 8. **顶点的度**：无向图中，一个顶点的度是与其相连的边数。对于有向图，度分为入度（作为弧头的边数）和出度（作为弧尾的边数）。 9. **路径**：路径是一系列连续的顶点，每相邻两个顶点之间由一条边相连。路径可以是有向或无向的。 10. **路径长度**：路径的长度可以是边的数量，也可以是路径上所有边的权值之和。 11. **回路**：回路是起点和终点相同的路径，可以是有向或无向的。 12. **简单路径与简单回路**：简单路径不允许顶点重复出现，除了起点和终点；简单回路除了起点和终点外，其他顶点不重复。 13. **连通性**：如果图中任意两个顶点间存在路径，那么这两个顶点是连通的。如果图中所有顶点都是连通的，那么这个图被称为连通图。 14. **连通分量**：在一个非连通图中，每个能够互相到达的顶点集合称为连通分量。 15. **强连通图**：在有向图中，如果对任何两个不同的顶点Vi和Vj，都有从Vi到Vj的路径和从Vj到Vi的路径，则称此图是强连通的。 这份资源通过详细的解释和实例，有助于深入理解图的这些基本概念，对于学习数据结构和算法的初学者来说非常有价值。