Python 实现无向图的深度优先搜索 (DFS) 和广度优先搜索 (BFS) 遍历

以下是使用 Python 代码实现无向图的深度优先搜索 (DFS) 和广度优先搜索 (BFS) 遍历算法。代码包含输入无向图的顶点数、边数和边信息，建立邻接矩阵表示的图，并提供 DFS 和 BFS 遍历选项，输出相应的遍历序列。

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj_matrix = [[0 for i in range(V)] for j in range(V)]
    
    def add_edge(self, u, v):
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1
    
    def dfs_util(self, v, visited, traversal):
        visited[v] = True
        traversal.append(v)
        for i in range(self.V):
            if self.adj_matrix[v][i] == 1 and not visited[i]:
                self.dfs_util(i, visited, traversal)
    
    def dfs(self, start):
        visited = [False for i in range(self.V)]
        traversal = []
        self.dfs_util(start, visited, traversal)
        return traversal
    
    def bfs(self, start):
        visited = [False for i in range(self.V)]
        queue = []
        traversal = []
        visited[start] = True
        queue.append(start)
        while queue:
            v = queue.pop(0)
            traversal.append(v)
            for i in range(self.V):
                if self.adj_matrix[v][i] == 1 and not visited[i]:
                    visited[i] = True
                    queue.append(i)
        return traversal


if __name__ == '__main__':
    V = int(input('Enter the number of vertices: '))
    E = int(input('Enter the number of edges: '))
    g = Graph(V)
    for i in range(E):
        u, v = map(int, input('Enter edge (u v): ').split())
        g.add_edge(u, v)
    print('Enter 1 for DFS or 2 for BFS:')
    choice = int(input())
    if choice == 1:
        print('DFS traversal:', g.dfs(0))
    elif choice == 2:
        print('BFS traversal:', g.bfs(0))
    else:
        print('Invalid choice')

示例输入和输出：

Enter the number of vertices: 4
Enter the number of edges: 4
Enter edge (u v): 0 1
Enter edge (u v): 0 2
Enter edge (u v): 1 3
Enter edge (u v): 2 3
Enter 1 for DFS or 2 for BFS:
1
DFS traversal: [0, 1, 3, 2]

Enter the number of vertices: 4
Enter the number of edges: 4
Enter edge (u v): 0 1
Enter edge (u v): 0 2
Enter edge (u v): 1 3
Enter edge (u v): 2 3
Enter 1 for DFS or 2 for BFS:
2
BFS traversal: [0, 1, 2, 3]