图论的存储

图的存储方式对于算法的效率和实现的简便性有着直接影响。本文介绍了两种常见的图的存储方法：邻接矩阵和邻接表，并提供了使用 Python 实现这两种方法的详细步骤。

前置知识

• 稀疏图：边数远小于顶点数的平方的图。
• 稠密图：边数接近顶点数的平方的图。
• 有向图与无向图：有向图的边具有方向性，无向图的边可视为双向的。
• 有权图与无权图：有权图的边具有权重，无权图的边没有权重。

1. 邻接矩阵

邻接矩阵通过一个二维数组表示图，其中 matrix[i][j] 表示从顶点 i 到顶点 j 的边的存在与否（例如 1 表示有边，0 表示无边）。这种方法对稠密图较为合适，但对于稀疏图会导致空间浪费。

建图操作

def create_adj_matrix(n): # 建立一张具有n个节点的图，此时这张图没有任何一条边
    return [[0] * (n + 1) for _ in range(n + 1)]

加边操作

在平时的笔试题中，一张图的读入通常以给定若干条边u v w 的形式给出，其中u代表这条边的起点,v代表这条边的终点,w代表这条边的权值。如果不含w，则读入的是无权图。

对于邻接矩阵而言，我们就需要了解如何对一张图进行加边操作

def add_edge(adj_matrix, u, v):
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1  # 对于无向图，需要添加双向边

打印矩阵

def print_adj_matrix(adj_matrix, n):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if adj_matrix[i][j] == 0:
                print(f"{i} 到 {j} 不存在边")
            else:
                print(f"{i} 到 {j} 存在边")
        print()

2. 邻接表

邻接表通过一个列表存储每个顶点的邻居。这种方法对稀疏图更节省空间，因为它只存储实际存在的边。

建表操作

adj_list = {i: [] for i in range(MAX)}

加边操作

def add_edge(adj_list, u, v):
    adj_list[u].append(v)
    adj_list[v].append(u)  # 对于无向图，需要添加双向边

遍历图

可以通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历图：

需要详细了解这两个遍历方法，可见后续课程。本处仅作简单介绍，读不懂的同学可以先跳过下面这段代码。

def dfs(adj_list, u, visited):
    visited[u] = True
    print(u, end=" ")
    for v in adj_list[u]:
        if not visited[v]:
            dfs(adj_list, v, visited)

            
#-----------------------------------

from collections import deque
def bfs(adj_list, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        u = queue.popleft()
        print(u, end=" ")
        for v in adj_list[u]:
            if not visited[v]:
                visited[v] = True
                queue.append(v)

题解

给定图A的邻接矩阵和图B的邻接表，判断这两图是否完全相同，即每个顶点的邻居集合是否一致。

思路

为了判断两张图是否完全一样，我们需要比较它们的邻接表是否一致，具体步骤如下：

1. 将图A的邻接矩阵转换为邻接表。
2. 将图B的邻接表读入。
3. 对每个顶点的邻接表排序。
4. 比较两图的邻接表是否完全一致。

Python实现

# 读取结点数
n = int(input())

# 读取图 A 的邻接矩阵并转换为邻接表
adj_a = {i: [] for i in range(n+1)}
for i in range(1, n + 1):
    row = list(map(int, input().split()))  # 一次读取一行矩阵数据
    for j in range(1, n + 1):
        if row[j - 1] == 1:  # 矩阵从 0 索引开始
            adj_a[i].append(j)

# 读取图 B 的邻接表
adj_b = [[] for _ in range(n + 1)]
for _ in range(n):
    data = list(map(int, input().split()))
    node = data[0]  # 第一个数是节点
    k = data[1]  # 第二个数是该节点的邻居数量
    neighbors = data[2:]  # 后续的 k 个数是邻居
    adj_b[node].extend(neighbors)

# 对每个节点的邻接表进行排序
for i in range(1, n + 1):
    adj_a[i].sort()
    adj_b[i].sort()

# 比较两张图的邻接表是否一致
same = True
for i in range(1, n + 1):
    if adj_a[i] != adj_b[i]:
        same = False
        break

print("YES" if same else "NO")

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; // 顶点数
    cin >> n;
    vector<vector<int>> adjA(n + 1), adjB(n + 1);
    
    // 读取并转换图 A
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int val;
            cin >> val;
            if (val == 1) adjA[i].push_back(j);
        }
    }
    
    // 读取图 B
    for (int i = 0; i < n; i++) {
        int node, k;
        cin >> node >> k;
        adjB[node].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> adjB[node][j];
        }
    }
    
    // 对邻接表排序
    for (int i = 1; i <= n; i++) {
        sort(adjA[i].begin(), adjA[i].end());
        sort(adjB[i].begin(), adjB[i].end());
    }
    
    // 比较邻接表
    bool same = true;
    for (int i = 1; i <= n; i++) {
        if (adjA[i] != adjB[i]) {
            same = false;
            break;
        }
    }
    
    cout << (same ? "YES" : "NO") << endl;
    return 0;
}

Java实现

import java.util.*;

public class GraphComparison {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 初始化和读取邻接矩阵
        int[][] matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 转换为邻接表
        List<List<Integer>> adjFromMatrix = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjFromMatrix.add(new ArrayList<>());
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i][j] == 1) {
                    adjFromMatrix.get(i).add(j);
                }
            }
        }

        // 读取并初始化邻接表
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int i = 1; i <= n; i++) {
            int node = scanner.nextInt();
            int k = scanner.nextInt();
            for (int j = 0; j < k; j++) {
                int neighbor = scanner.nextInt();
                adjList.get(node).add(neighbor);
            }
        }

        // 排序邻接表，以便比较
        for (int i = 1; i <= n; i++) {
            Collections.sort(adjFromMatrix.get(i));
            Collections.sort(adjList.get(i));
        }

        // 比较两张图的邻接表是否一致
        boolean identical = true;
        for (int i = 1; i <= n; i++) {
            if (!adjFromMatrix.get(i).equals(adjList.get(i))) {
                identical = false;
                break;
            }
        }

        System.out.println(identical ? "YES" : "NO");
    }
}

题目描述：

给定两张有向图 $A$ 和 $B$，其中图 $A$ 以邻接矩阵形式给出，图 $B$ 以邻接表形式给出。请判断这两张图是否完全一样。我们将“完全一样”的定义为：每个节点的邻居集合完全一致。

输入

输入的第一行包含两个整数 $n$，表示图的节点数。

接下来的$n$行，给出图 $A$ 的邻接矩阵。该矩阵的第 $i$ 行第 $j$ 列表示节点 $i$ 和节点 $j$ 之间是否有边。如果存在边，则该位置的值为 1，否则为 0。

接下来的$n$行，给出图 $B$ 的邻接表。每行第一个数$node$,后面跟的第一个数$k$表示接下来输入$k$个数$val$表示节点$node$向这些节点$val$连一条边

输出

如果图 $A$ 和图 $B$ 完全一样，则输出 "YES"；否则输出 "NO"。

注意

• 图 $A$ 和图 $B$ 是有向图，即如果 $A[i][j] = 1$，那么 $i$ 到 $j$ 有条有向边。
• 节点编号从 1 到 $n$。
• 图 $A$ 和图 $B$ 的节点数相同。
• 数据范围：
  • $1 \leq n \leq 10^3$
  • 图 $A$ 的邻接矩阵大小为 $n \times n$，其中每个元素为 0 或 1。
  • 图 $B$ 的邻接表中每个节点的邻居数量不超过 $n-1$。

样例输入 1

3
0 1 1
1 0 1
1 1 0
1 2 2 3
2 2 1 3
3 2 1 2

样例输出 1

YES

样例输入 2

3
0 1 1
1 0 1
1 1 0
1 2 2 3
2 2 1 3
3 1 1 

样例输出 2

NO

样例2提示

图 $A$ 的邻接矩阵为：

0 1 1
1 0 1
1 1 0

表示图 $A$ 中，节点 $1$ 与节点 $2$ 和节点 $3$ 相连，节点 $2$ 与节点 $1$ 和节点 $3$ 相连，节点 $3$ 与节点 $1$ 和节点 $2$ 相连。

图 $B$ 的邻接表为：

1 2 2 3
2 2 1 3
3 1 1

表示图 $B$ 中，节点 $1$ 与节点 $2$ 和节点 $3$ 相连，节点 $2$ 与节点 $1$ 和节点 $3$ 相连，节点 $3$ 与节点 $1$ 相连。

对比可以发现，在图 $B$ 中，节点 $3$ 不连向 节点 $2$。因此，图 $A$ 和图 $B$ 不完全一样，输出 "NO"。