给定两张图 A 和 B,其中图 A 以邻接矩阵形式给出,图 B 以邻接表形式给出。请判断这两张图是否完全一样。我们将“完全一样”的定义为:每个节点的邻居集合完全一致。
输入的第一行包含两个整数 n 和 m,表示图的节点数和边数。
接下来,给出图 A 的邻接矩阵。该矩阵的第 i 行第 j 列表示节点 i 和节点 j 之间是否有边。如果存在边,则该位置的值为 1,否则为 0。
介绍两种建图的方法:
在图论的应用中,图的表示方式对算法的效率和实现的简便性有着重要影响。对于稀疏图(即边数远少于顶点数平方的图),邻接表(Adjacency List)是一种高效的表示方法。接下来将详细介绍如何使用 Python 中的 list
来实现邻接表,并讨论其优化方法,特别适用于笔试编程和高效算法实现。