如何从给定的弧集构建图的邻接矩阵和邻接表？

要从给定的弧集构建图的邻接矩阵和邻接表，首先需要明确图的类型（有向图或无向图）以及顶点和弧的定义。假设我们有一个图 ( G = (V, E) )，其中 ( V ) 是顶点集合，( E ) 是弧集合。

1. 构建邻接矩阵

邻接矩阵是一个 ( |V| \times |V| ) 的矩阵，其中 ( |V| ) 是顶点的数量。矩阵中的元素 ( A_{ij} ) 表示顶点 ( i ) 和顶点 ( j ) 之间是否存在弧。

步骤：

1. 初始化矩阵：创建一个大小为 ( |V| \times |V| ) 的矩阵，初始值为 0。
2. 填充矩阵：
   • 对于无向图，如果存在弧 ( (i, j) )，则 ( A_{ij} = 1 ) 且 ( A_{ji} = 1 )。
   • 对于有向图，如果存在弧 ( (i, j) )，则 ( A_{ij} = 1 )。

示例：

假设有一个无向图，顶点集合 ( V = {1, 2, 3, 4} )，弧集合 ( E = {(1, 2), (2, 3), (3, 4), (4, 1)} )。

邻接矩阵为： [ \begin{bmatrix} 0 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 \ 0 & 1 & 0 & 1 \ 1 & 0 & 1 & 0 \ \end{bmatrix} ]

2. 构建邻接表

邻接表是一种链表的数组，每个顶点对应一个链表，链表中存储与该顶点直接相连的顶点。

步骤：

1. 初始化邻接表：创建一个大小为 ( |V| ) 的数组，每个元素初始化为空链表。
2. 填充邻接表：
   • 对于无向图，如果存在弧 ( (i, j) )，则在顶点 ( i ) 的链表中添加 ( j )，并在顶点 ( j ) 的链表中添加 ( i )。
   • 对于有向图，如果存在弧 ( (i, j) )，则在顶点 ( i ) 的链表中添加 ( j )。

示例：

继续使用上面的无向图示例，邻接表为： [ \begin{align} 1 & \rightarrow 2 \rightarrow 4 \ 2 & \rightarrow 1 \rightarrow 3 \ 3 & \rightarrow 2 \rightarrow 4 \ 4 & \rightarrow 3 \rightarrow 1 \ \end{align} ]

代码示例（Python）

def build_adjacency_matrix(vertices, edges, directed=False):
    n = len(vertices)
    adj_matrix = [[0] * n for _ in range(n)]

    for (u, v) in edges:
        i = vertices.index(u)
        j = vertices.index(v)
        adj_matrix[i][j] = 1
        if not directed:
            adj_matrix[j][i] = 1

    return adj_matrix

def build_adjacency_list(vertices, edges, directed=False):
    adj_list = {v: [] for v in vertices}

    for (u, v) in edges:
        adj_list[u].append(v)
        if not directed:
            adj_list[v].append(u)

    return adj_list

# 示例
vertices = [1, 2, 3, 4]
edges = [(1, 2), (2, 3), (3, 4), (4, 1)]

adj_matrix = build_adjacency_matrix(vertices, edges)
adj_list = build_adjacency_list(vertices, edges)

print("邻接矩阵:")
for row in adj_matrix:
    print(row)

print("\n邻接表:")
for key, value in adj_list.items():
    print(f"{key} -> {value}")

输出：

邻接矩阵:
[0, 1, 0, 1]
[1, 0, 1, 0]
[0, 1, 0, 1]
[1, 0, 1, 0]

邻接表:
1 -> [2, 4]
2 -> [1, 3]
3 -> [2, 4]
4 -> [3, 1]

通过上述步骤和代码示例，你可以从给定的弧集构建图的邻接矩阵和邻接表。