图的数组表示法：邻接矩阵-数据结构基础

"数组表示法(邻接矩阵)-数据结构（清华大学版）——图" 图是一种数据结构，由顶点集V和边或弧的关系集合VR组成，通常表示为Graph=(V,{VR})。在图中，任意两个顶点之间可能存在关系，这使得图成为线性表和树之外更复杂的数据结构。在各种科学和工程领域，如人工智能、计算机科学等，图都有着广泛的应用。 本章主要探讨图的存储结构和操作实现，包括图的定义、存储表示、遍历、最小生成树和最短路径。图的存储方式之一是数组表示法，即邻接矩阵。邻接矩阵是一个二维数组，用于表示图中每个顶点之间的关系。如果图是有向的，邻接矩阵是对称的；如果是无向的，则矩阵是对称的。 在邻接矩阵中，行和列代表图中的顶点，矩阵中的每个元素表示对应顶点之间是否存在边或弧，以及它们的权重（如果有的话）。例如，如果矩阵中的元素a[i][j]为非零值，表示从顶点i到顶点j有一条边；如果为零，表示没有直接连接。对于无权图，通常用1表示存在边，0表示不存在；对于有权图，边的权重会存储在这个位置。 在C语言中，邻接矩阵可以定义为一个整型二维数组，如`int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM]`，其中`MAX_VERTEX_NUM`是预定义的最大顶点数量。为了表示无穷大（如在寻找最短路径时），可以定义一个常量`INFINITY`，通常设置为`INT_MAX`。 图的基本操作包括创建、销毁、查找顶点位置、获取和设置顶点值、遍历邻接顶点、添加和删除顶点，以及添加和删除边。例如，`CreateGraph()`函数根据给定的顶点集V和边集VR构造一个图，`DestroyGraph()`函数则销毁一个已存在的图。`LocateVex()`用于找到图中特定特征的顶点，`GetVex()`和`PutVex()`分别用于获取和修改顶点的值。`FirstAdjVex()`和`NextAdjVex()`帮助遍历与给定顶点相邻的顶点，而`InsertVex()`和`DeleteVex()`分别用于增加和移除顶点。插入或删除边的操作通常涉及更新邻接矩阵的相应元素。 图的遍历方法主要包括深度优先搜索(DFS)和广度优先搜索(BFS)，这些方法在寻找最小生成树或计算最短路径时非常关键。最小生成树算法如Prim's算法或Kruskal's算法用于找到图中连接所有顶点的边集合，使得这些边的总权重最小。最短路径问题可以通过Dijkstra算法或Floyd-Warshall算法来解决。 图的数组表示法（邻接矩阵）是图论和数据结构中的基础概念，它提供了高效地存储和操作图的方法，对于理解和实现各种图算法至关重要。