数据结构浙大讲义图论之什么是图

### 数据结构浙大讲义图论之什么是图 #### 六度空间理论与图的应用背景 在浙江大学的数据结构课程中，陈越教授介绍了图的概念及其应用。本讲以六度空间理论作为引子，探讨了图论在实际生活中的应用。六度空间理论指出，在人际交往中，任何两个人之间最多通过六个人就能建立起联系。这一理论不仅适用于人际关系网络的研究，也广泛应用于社交网络分析、市场推广等领域。在全球互联网用户数量达到约30亿的情况下，如何理解和利用这种复杂的网络关系变得尤为重要。 #### 图的基本概念 图是一种强大的数学模型，用于描述对象之间的关系。它由顶点集合`V`和边集合`E`组成，其中边集合`E`是一组顶点对，表示顶点间的连接关系。具体来说： - **顶点**：通常用`V`表示，是一组表示对象的节点。 - **边**：通常用`E`表示，是一组表示顶点之间连接关系的元素。 - **边是顶点对**：表示两个顶点之间的连接关系，如`(v, w)`，其中`v, w ∈ V`。 - **有向边**：表示从一个顶点指向另一个顶点的单向连接，通常表示为`<v, w>`。 #### 抽象数据类型定义 图作为一种抽象数据类型，具有以下特征： - **数据对象集**：`G(V, E)`由一个非空的有限顶点集合`V`和一个有限边集合`E`组成。 - **操作集**：针对任意图`G ∈ Graph`，以及`v ∈ V, e ∈ E`，提供了一系列操作，包括但不限于： - `GraphCreate()`：建立并返回一个空图。 - `GraphInsertVertex(Graph G, Vertex v)`：将顶点`v`插入图`G`中。 - `GraphInsertEdge(Graph G, Edge e)`：将边`e`插入图`G`中。 - `void DFS(Graph G, Vertex v)`：从顶点`v`出发进行深度优先搜索遍历图`G`。 - `void BFS(Graph G, Vertex v)`：从顶点`v`出发进行宽度优先搜索遍历图`G`。 - `void ShortestPath(Graph G, Vertex v, int Dist[])`：计算图`G`中从顶点`v`到所有其他顶点的最短路径。 - `void MST(Graph G)`：计算图`G`的最小生成树。 #### 常见术语 - **无向图**：所有边都是无方向的图。 - **有向图**：所有边都有明确方向的图。 - **网**：带有权重的图，通常用来表示成本或距离等信息。 #### 图的表示方法 图在程序中的表示方法主要有两种：邻接矩阵和邻接表。 - **邻接矩阵**：通过一个二维数组`G[N][N]`来表示图，其中`N`为顶点的数量。对于无向图，矩阵是对称的，可以通过只存储下半部分来节省空间。对于有向图或带权图，可以根据需要存储不同的信息。邻接矩阵的优点在于能够直观地展示图的结构，并且方便检查任意两点之间是否存在边以及计算顶点的度。 - **邻接表**：通过一个数组加上链表的方式来表示图。每个顶点对应一个链表，链表中存储了与其相邻的顶点。邻接表特别适合表示稀疏图，因为它只需要存储存在的边，从而节省了大量的存储空间。同时，在查询某个顶点的邻接点时也非常高效。 通过以上介绍，我们可以看出图论不仅在理论上有深厚的数学基础，而且在实际应用中也极其广泛，无论是从理论研究还是从实际编程的角度来看，掌握图的相关知识都是非常重要的。