图数据结构：遍历、最小生成树与最短路径

"本资源主要探讨了图的建立和销毁，包括图的定义、存储表示、遍历、最小生成树、最短路径问题、拓扑排序以及关键路径等核心概念。" 在计算机科学中，图是一种重要的数据结构，用于表示对象之间的关系。它由一个顶点集V和一个弧集R组成，形式化表示为Graph=(V,R)，其中R包含所有从顶点v到顶点w的弧，v称为弧尾，w称为弧头。如果弧是双向的，即每条弧<v,w>都有对应的<w,v>，则图被称为无向图；反之，如果弧具有方向性，即仅有一方向，那么就是有向图。 图的存储表示通常有两种主要方法：邻接矩阵和邻接表。邻接矩阵是一个二维数组，用于存储图中每个顶点之间的连接信息，而邻接表则是以链表或数组的形式存储每个顶点的邻接点。这两种方法各有优缺点，邻接矩阵适用于表示稠密图（边数量接近于顶点数量的平方），邻接表则更适合稀疏图（边数量远小于顶点数量的平方）。 图的遍历是图算法中的基础操作，包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS通过递归或栈来探索尽可能深的路径，而BFS则使用队列来确保先访问离起点近的顶点。这两种方法在寻找图的最小生成树、最短路径等问题中扮演着关键角色。 最小生成树是无向图的一个子集，包含了所有顶点且边的权重之和最小。常用的算法有Prim's算法和Kruskal's算法。拓扑排序应用于有向无环图(DAG)，它能将顶点排成线性顺序，使得对于每条有向边<v,w>，顶点v总是在顶点w之前。 两点之间的最短路径问题可以使用Dijkstra算法或Bellman-Ford算法解决，它们寻找的是两个顶点之间路径的最小权重。关键路径是项目管理中的一个重要概念，它标识了决定项目最早完成时间的最长路径。 顶点的度是与之关联的边的数量，分为出度（作为弧尾的边数）和入度（作为弧头的边数）。在无向图中，顶点的度等于其出度加上入度。完全图是指所有顶点间都有边相连的图，有向完全图则是每对顶点间都有两条相反方向的弧。 子图是原图的一部分，包含原图的部分顶点和边。带权的图（或网）是指边或弧上附带有数值的图，这些数值通常代表某种成本或距离。 理解并掌握图的这些基本概念对于学习和应用图论、网络流、最优化问题等领域的算法至关重要。