图论算法详解：邻接矩阵与邻接表

"图的存储表示-etap学习资料" 在图论中，图是一种数学结构，用于表示对象之间的关系。图由顶点（Vertex）和边（Edge）组成，边可以是有向的（Directed）或无向的（Undirected）。有向图表示从一个顶点到另一个顶点的方向，而无向图则没有明确的方向。如果边带有与之相关的数值，这个数值被称为权值（Weight），这样的图被称为加权图或网络。权值可以代表距离、成本、时间等多种含义。 例如，图1.13(a)展示了一个无向网G1，其中包含了顶点集合V(G1)={1, 2, 3, 4, 5, 6, 7}和边的集合E(G1)，每个边都带有权值。无向网中，边是双向的，表示两个顶点间的相互连接。而图1.13(b)显示了一个有向网G2，其顶点集合相同，但边是有方向的，并且同样带有权值。 图的存储表示是图论算法的基础，常见的方法有三种：邻接矩阵、邻接表和邻接多重表。邻接矩阵使用一个二维数组来表示图，其中的元素表示顶点之间的连接关系，若存在边则为非零值，无边则为零。邻接表则是为每个顶点维护一个列表，列表中的元素代表与其相邻的顶点。这种方法在处理稀疏图（边的数量远小于顶点数量的平方）时更为高效，因为它只存储实际存在的边。 本书《图论算法理论、实现及应用》深入探讨了图论算法的理论、实现和应用。作者通过经典的ACM/ICPC竞赛题目来讲解图论算法思想，内容涵盖了图的遍历、活动网络、树与生成树问题、最短路径问题、可行遍性问题、网络流问题以及各种集合问题（如点支配集、点覆盖集、点独立集、边覆盖集、边独立集匹配）和图的连通性问题。此外，书中还讨论了平面图与图的着色问题。这本书适合高等院校计算机及相关专业的学生作为图论课程的教材，同时也适合作为ACM/ICPC竞赛的参考书。 图论源自18世纪莱昂哈德·欧拉解决的哥尼斯堡七桥问题，这是图论历史上的一个里程碑。欧拉通过将问题转化为图的模型，首次引入了图的概念，并提出了图的遍历法则，为后续的图论研究奠定了基础。图论在自然科学、社会科学等多个领域都有广泛的应用，是现代计算机科学中不可或缺的一部分。