图的基本概念与存储结构：有向图、无向图与网络

"数据结构导论中第5章 图课件" 在数据结构的学习中，图是一种非常重要的数据结构，它用于表示对象之间的关系。第5章“图”涵盖了图的定义、术语、存储结构、遍历算法以及特定的应用，如最小生成树和拓扑排序。 首先，图是由顶点集V和边集E组成的，记为Graph=(V,E)。顶点可以是任何标识符，而边可以是有向或无向的。如果边具有方向，即从一个顶点指向另一个顶点，那么图被称为有向图，边称为弧，例如<v,w>。相反，如果边没有方向，那么图被称为无向图，边用(v,w)表示。如果边或弧带有数值，我们称之为权值，这样的图被称为带权图，有向的带权图称为有向网，无向的称为无向网。 图的子图是原图的一部分，包含在原图的顶点集中，并且只包含原图的部分边。例如，如果图G=(V,E)，而图G'=(V',E')，满足V'⊆V且E'⊆E，则G'是G的子图。 图中的度是与一个顶点相关的边的数量。在无向图中，每个边会为两个端点各增加1度。顶点v的度（Degree）等于与其相邻的边数。对于有向图，我们区分出度（Outdegree）和入度（Indegree），出度是作为弧尾的边数，入度是作为弧头的边数，总度是出度加上入度。 完全图是指所有顶点间都有边相连的无向图，它有e=n(n-1)/2条边，其中n是顶点的数量。而有向完全图则是每对顶点之间都有一条有向边，因此有e=n(n-1)条弧。 在实际应用中，图的遍历算法如深度优先搜索(DFS)和广度优先搜索(BFS)是非常关键的。它们用于访问图中的所有顶点，通常用于查找路径、检测环路等问题。此外，最小生成树算法（如Prim算法和Kruskal算法）用于找到带权无向图中权重最小的树形子图，覆盖所有顶点。拓扑排序则用于有向无环图(DAG)，它可以确定顶点的一种线性顺序，使得对于每条有向边<u,v>，u总是在v之前。 最后，如果图中的边或弧数量e小于顶点数量n的线性关系，即e<n(n-1)/2（无向图）或e<n(n-1)（有向图），那么图不是完全图，这可能是稀疏图，即边的数量相对较少。反之，如果边的数量接近于完全图的边数，那么图被称为稠密图。 通过理解和掌握这些基本概念，可以有效地解决各种图论问题，包括网络流、最短路径计算、旅行商问题等。在计算机科学中，图理论的应用无处不在，从社交网络到计算机网络，再到物流路线规划，都是图论模型的实际应用。