邻接矩阵是一种表示图结构的数学工具，它以矩阵的形式展现了图中顶点之间的连接关系。对于无向图和有向图，邻接矩阵的计算方式略有不同。
基本概念
在开始计算之前，我们需要了解一些基本概念：
- 顶点：图中独立存在的对象。
- 边：连接两个顶点的线段。
- 邻接：如果两个顶点通过一条边相连，则称这两个顶点相邻。
计算步骤
无向图的邻接矩阵
- 确定顶点数量：首先确定图中的顶点数量，记为( V )。
- 创建邻接矩阵：创建一个( V \times V )的矩阵，所有元素初始化为0。
- 填充矩阵：对于每一条边( (u, v) )，在矩阵的( u )行( v )列和( v )行( u )列的元素处填入1，表示顶点( u )和顶点( v )相邻。
有向图的邻接矩阵
- 确定顶点数量：确定图中的顶点数量，记为( V )。
- 创建邻接矩阵：创建一个( V \times V )的矩阵，所有元素初始化为0。
- 填充矩阵：对于每一条有向边( (u, v) )，在矩阵的( u )行( v )列的元素处填入1，表示顶点( u )指向顶点( v )。
举例说明
无向图示例
假设有一个无向图，其顶点为A、B、C、D，边为AB、BC、CD、DA。
邻接矩阵如下：
A B C D
A [0 1 0 1]
B [1 0 1 0]
C [0 1 0 1]
D [1 0 1 0]
有向图示例
假设有一个有向图，其顶点为A、B、C、D，边为AB、AC、AD。
邻接矩阵如下：
A B C D
A [0 0 0 1]
B [1 0 0 0]
C [0 0 1 0]
D [0 0 0 0]
编程实现
下面是使用Python计算无向图邻接矩阵的代码示例：
def create_adjacency_matrix(undirected_graph):
vertices = list(undirected_graph.keys())
num_vertices = len(vertices)
adjacency_matrix = [[0] * num_vertices for _ in range(num_vertices)]
for u, v in undirected_graph.items():
adjacency_matrix[vertices.index(u)][vertices.index(v)] = 1
adjacency_matrix[vertices.index(v)][vertices.index(u)] = 1
return adjacency_matrix
# 使用示例
graph = {
'A': ['B', 'C', 'D'],
'B': ['A'],
'C': ['A', 'D'],
'D': ['A', 'C']
}
matrix = create_adjacency_matrix(graph)
for row in matrix:
print(row)
运行上述代码，将会得到一个无向图的邻接矩阵。
通过以上方法，您可以根据具体的图信息计算出相应的邻接矩阵。