Python：利用邻接矩阵判断无向图的连通性

利用邻接矩阵判断无向图的连通性可以通过以下步骤实现：

1. 创建一个二维数组作为邻接矩阵，其中每个元素表示两个顶点之间是否存在边或弧的关系。如果存在边或弧，则对应位置的元素为1，否则为0。

2. 判断无向图的连通性可以通过检查邻接矩阵是否是对称矩阵来实现。对称矩阵是指矩阵的转置等于矩阵本身。

3. 遍历邻接矩阵的每个元素，检查对应位置的元素是否相等。如果存在不相等的元素，则说明图不连通；如果所有元素都相等，则说明图连通。

以下是一个使用Python实现的示例代码：

def is_connected(adj_matrix):
    # 检查邻接矩阵是否是对称矩阵
    for i in range(len(adj_matrix)):
        for j in range(i+1, len(adj_matrix)):
            if adj_matrix[i][j] != adj_matrix[j][i]:
                return False
    return True

# 示例邻接矩阵
adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]
]

if is_connected(adj_matrix):
    print("图是连通的")
else:
    print("图不连通")

输出结果为："图是连通的"，表示给定的邻接矩阵表示的图是连通的。

相关问题

利用邻接矩阵储存无向图

邻接矩阵是一种常见的储存无向图的方法。对于一个无向图G=(V,E)，设V中有n个顶点，邻接矩阵A是一个n*n的矩阵，其中A[i][j]表示顶点i和顶点j之间是否有边，如果有，则A[i][j]=1，否则A[i][j]=0。由于是无向图，因此A[i][j]=A[j][i]，即邻接矩阵是对称的。

邻接矩阵的优点是可以快速判断任意两个顶点之间是否有边，时间复杂度为O(1)，而且储存空间比较小，只需要n*n个空间。但是当图的边数比较稀疏时，也就是说E比较小，邻接矩阵会有很多空洞，浪费了储存空间，因此不适用于稀疏图。另外，对于大型图，邻接矩阵的储存空间也会非常大，导致效率下降。

利用邻接矩阵创建无向图实现DFS和BFS

好的，下面是利用邻接矩阵创建无向图实现DFS和BFS的 Python 代码：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj_matrix = [[0] * self.V for _ in range(self.V)]

    def add_edge(self, u, v):
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1

    def DFSUtil(self, v, visited):
        visited[v] = True
        print(v, end=' ')
        for i in range(self.V):
            if self.adj_matrix[v][i] == 1 and not visited[i]:
                self.DFSUtil(i, visited)

    def DFS(self, start):
        visited = [False] * self.V
        self.DFSUtil(start, visited)
        print()

    def BFS(self, start):
        visited = [False] * self.V
        queue = [start]
        visited[start] = True
        while queue:
            s = queue.pop(0)
            print(s, end=' ')
            for i in range(self.V):
                if self.adj_matrix[s][i] == 1 and not visited[i]:
                    queue.append(i)
                    visited[i] = True
        print()

其中，`Graph` 类表示一个图，`__init__` 方法初始化图的顶点数 `V` 和邻接矩阵 `adj_matrix`。`add_edge` 方法用来添加边。`DFSUtil` 方法表示 DFS 的递归实现。`DFS` 方法表示 DFS 的非递归实现。`BFS` 方法表示 BFS 的实现。其中，`visited` 数组用来记录顶点是否被访问过，`queue` 则用来实现 BFS 的队列。

你可以按照下面的步骤来测试代码：

g = Graph(4)

g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

print("DFS:")
g.DFS(0)
print("BFS:")
g.BFS(0)

输出结果为：

DFS:
0 1 2 3 
BFS:
0 1 2 3