#P3994. 图的读入与构建
-
ID: 2213
Tried: 115
Accepted: 42
Difficulty: 5
图的读入与构建
题目描述：
给定两张有向图 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≤n≤103
- 图 A 的邻接矩阵大小为 n×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"。
图论的存储
图的存储方式对于算法的效率和实现的简便性有着直接影响。本文介绍了两种常见的图的存储方法：邻接矩阵和邻接表，并提供了使用 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的邻接表，判断这两图是否完全相同，即每个顶点的邻居集合是否一致。
思路
为了判断两张图是否完全一样，我们需要比较它们的邻接表是否一致，具体步骤如下：
- 将图A的邻接矩阵转换为邻接表。
- 将图B的邻接表读入。
- 对每个顶点的邻接表排序。
- 比较两图的邻接表是否完全一致。
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");
}
}