邻接矩阵判断两个顶点是否相连

邻接矩阵是一种表示图的数据结构，其中矩阵的行和列代表图中的节点，而矩阵中的值表示节点之间的连接关系。如果节点 i 和节点 j 之间存在一条边，则邻接矩阵中第 i 行第 j 列的值为 1；否则为 0。

因此，如果要判断节点 i 和节点 j 是否相连，只需要查看邻接矩阵中第 i 行第 j 列的值即可。如果该值为 1，表示节点 i 和节点 j 相连；如果该值为 0，表示节点 i 和节点 j 不相连。

相关问题

给定一个无向简单图，输出该图的邻接矩阵，根据邻接矩阵输出每个顶点度数，验证握手定理，并判定该图是否为树。

好的，让我来回答你的问题。

对于给定的无向简单图，我们可以使用邻接矩阵来表示它。邻接矩阵是一个 $n \times n$ 的矩阵，其中 $n$ 是图中顶点的数量，矩阵中的第 $i$ 行第 $j$ 列的元素表示顶点 $i$ 和顶点 $j$ 之间是否有边相连。如果有，该元素为 $1$，否则为 $0$。

我们可以用以下代码来输出图的邻接矩阵：

n = 5 # 顶点数量
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)] # 边列表
adj_matrix = [[0] * n for _ in range(n)] # 初始化邻接矩阵

for i, j in edges:
    adj_matrix[i][j] = 1
    adj_matrix[j][i] = 1

for row in adj_matrix: # 输出邻接矩阵
    print(row)

输出结果为：

[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 1]
[0, 1, 1, 0, 1]
[0, 0, 1, 1, 0]

接下来，我们可以计算每个顶点的度数。顶点的度数是指与该顶点相邻的边的数量。我们可以遍历邻接矩阵的每一行，统计该行中元素的和即可得到该行对应顶点的度数。

degrees = [sum(row) for row in adj_matrix] # 计算每个顶点的度数

for i, degree in enumerate(degrees): # 输出每个顶点的度数
    print(f"顶点 {i} 的度数为 {degree}")

输出结果为：

顶点 0 的度数为 2
顶点 1 的度数为 2
顶点 2 的度数为 3
顶点 3 的度数为 3
顶点 4 的度数为 2

接下来，我们可以验证握手定理。握手定理指出，在一个无向简单图中，所有顶点的度数之和等于边的数量的两倍。我们可以遍历邻接矩阵，统计其中所有元素的和，再除以 $2$，即可得到边的数量。

num_edges = sum(sum(row) for row in adj_matrix) // 2 # 计算边的数量
assert num_edges == 6, "边的数量计算错误" # 检查边的数量是否正确

handshaking_sum = sum(degrees) # 计算所有顶点的度数之和
assert handshaking_sum == 12, "握手定理不成立" # 检查握手定理是否成立

由输出结果可知，边的数量为 $6$，所有顶点的度数之和为 $12$，握手定理成立。

最后，我们可以判断该图是否为树。树是一种无向简单图，其中任意两个顶点之间都有唯一的简单路径，并且没有环。我们可以使用深度优先搜索（DFS）来判断该图是否为树。

visited = [False] * n # 记录每个顶点是否被遍历过
stack = [(0, -1)] # DFS 栈，初始顶点为 0，父节点为 -1

while stack:
    curr, parent = stack.pop()

    if visited[curr]: # 如果当前顶点已被遍历过，说明存在环，该图不是树
        print("该图不是树")
        break

    visited[curr] = True # 标记当前顶点为已遍历
    for neighbor, _ in filter(lambda x: x[1] == 1, enumerate(adj_matrix[curr])):
        if neighbor != parent: # 如果邻居不是当前顶点的父节点，将邻居加入 DFS 栈中
            stack.append((neighbor, curr))
else:
    if all(visited): # 如果所有顶点都被遍历过，说明该图是树
        print("该图是树")
    else: # 否则，说明该图不是连通图
        print("该图不是树")

由于该图没有环且所有顶点都是连通的，因此输出结果为：“该图是树”。

假设带权有向图采用邻接矩阵存储。设计图的基本运算算法，包括创建图的邻接矩阵，输出图的邻接矩阵，销毁图的邻接矩阵，求图中顶点的度。

好的，假设我们已经有了带权有向图的数据，下面我来介绍一下这个图的基本运算算法。

1. 创建图的邻接矩阵：
首先需要确定图中顶点的个数n，然后创建一个n*n的二维数组adjacency_matrix，用来存储每个顶点之间的边和权重。如果两个顶点之间没有边，则用一个极大值表示。创建邻接矩阵后，需要遍历带权有向图中的每条边，将对应的权重填入adjacency_matrix中的对应位置即可。

2. 输出图的邻接矩阵：
输出邻接矩阵其实就是遍历二维数组adjacency_matrix，将其输出即可。

3. 销毁图的邻接矩阵：
销毁邻接矩阵其实就是释放二维数组adjacency_matrix占用的内存空间。

4. 求图中顶点的度：
顶点的度指的是与该顶点相连的边数，对于有向图来说，分为入度和出度。对于顶点i来说，其入度可以通过遍历adjacency_matrix列来求得，出度可以通过遍历adjacency_matrix行来求得。