有向图与无向图的算法实现：数据结构详解

本资源主要介绍了图在算法实现中的应用，涉及图的定义、术语和基本概念。首先，图被定义为由顶点集V(G)和边集E(G)构成的结构，可以是无向图或有向图。无向图的边是对称的，如例子G2所示，而有向图的边具有方向性，如例子G1中的弧<v,w>和<w,v>不同。图的大小可以通过顶点数和边数来衡量，有向完备图和无向完备图分别对应最大边数的计算。 在图中，权值与边或弧相关，赋予边或弧数值，使得图成为网络，这在实际应用中常用于衡量距离、成本等。子图的概念强调了包含关系，即一个图可以是另一个图的子集，如果子图的顶点和边都在原图中。 顶点的度在图论中至关重要，无向图中度是指与该顶点相连边的数量，而有向图中区分了入度（指向顶点的边数）和出度（从顶点出发的边数）。路径是图中的一系列顶点连接，包括简单路径和简单回路，前者不重复顶点，后者除首尾外其余顶点也不重复。连通性和连通图指的是任意两点间存在路径，而连通分量则是非连通图分解后的各个独立部分。最后，强连通图是指有向图中每个顶点都可以通过有向边到达其他任何顶点。 这部分内容涵盖了图的基本理论，对于理解和实现图算法，如最短路径算法（如Dijkstra算法或Floyd-Warshall算法），理解这些概念至关重要。在算法实现时，会用到邻接矩阵（ad[][]）来存储图的结构，同时利用数组dist[]和pre[]来跟踪最短路径的相关信息。这些数据结构和概念的深入理解是算法设计和分析的基础。