python实现邻接表转邻接矩阵

具体实现邻接表转邻接矩阵的过程，可以分为以下几个步骤：

第一步，定义邻接表

首先需要定义一个邻接表，一般来说邻接表是一个字典类型，字典的每一个键表示图中的一个节点，而该键对应的值则是与该节点相邻的所有节点。

例如，我们可以使用如下的邻接表表示一个简单无向图：

adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

第二步，创建邻接矩阵

创建一个空的邻接矩阵，该矩阵的大小为图中节点的数量，如果某个节点与另一个节点相邻，则将邻接矩阵对应位置的值标记为 1，否则标记为 0。

例如上述邻接表所对应的邻接矩阵应该是：

	A	B	C	D
A	0	1	1	0
B	1	0	1	1
C	1	1	0	1
D	0	1	1	0

第三步，实现代码

最后是具体的实现代码，在 Python 中实现邻接表转换成邻接矩阵可以使用如下的代码：

def adj_list_to_matrix(adj_list):
    """
    将邻接表转换成邻接矩阵
    """
    nodes = sorted(adj_list.keys())
    n = len(nodes)
    node2index = { nodes[i]: i for i in range(n) }
    matrix = [[0] * n for i in range(n)]
    for i in range(n):
        node = nodes[i]
        neighbors = adj_list[node]
        for neighbor in neighbors:
            j = node2index[neighbor]
            matrix[i][j] = 1
    return matrix

该函数接受一个邻接表作为输入，返回一个相应的邻接矩阵。

示例说明

下面通过两个示例来演示邻接表转换成邻接矩阵的整个过程。

示例 1

假设我们有如下的无向图：

  +----B----+
  |         |
A |         | C
  |         |
  +----D----+

其邻接表为：

adj_list = {
    'A': ['B', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['B', 'D'],
    'D': ['A', 'B', 'C']
}

对应的邻接矩阵应该是：

	A	B	C	D
A	0	1	0	1
B	1	0	1	1
C	0	1	0	1
D	1	1	1	0

示例 2

假设我们有如下的有向图：

  +---->B---->D--->+
  |     / \        |
  |    /   \       |
  |   A     \      |
  |    \     v     |
  |     \>C------+ |
  +---------------+

其邻接表为：

adj_list = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['B', 'D'],
    'D': []
}

对应的邻接矩阵应该是：

	A	B	C	D
A	0	1	1	0
B	0	0	0	1
C	0	1	0	1
D	0	0	0	0

希望这个例子可以帮助你更好地了解如何使用 Python 实现邻接表转换成邻接矩阵。