用邻接矩阵或邻接表创建图然后进行DFS和BFS操作的一个程序

以下是使用邻接矩阵和邻接表实现DFS和BFS的示例代码：

使用邻接矩阵：

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

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

    def DFS(self, v, visited):
        visited[v] = True
        print(v, end=' ')

        for i in range(self.V):
            if self.graph[v][i] == 1 and not visited[i]:
                self.DFS(i, visited)

    def BFS(self, s):
        visited = [False]*self.V
        queue = []

        visited[s] = True
        queue.append(s)

        while queue:
            s = queue.pop(0)
            print(s, end=' ')

            for i in range(self.V):
                if self.graph[s][i] == 1 and not visited[i]:
                    visited[i] = True
                    queue.append(i)

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)

visited = [False]*g.V
print("DFS:")
g.DFS(0, visited)

print("\nBFS:")
g.BFS(0)

使用邻接表：

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def DFS_util(self, v, visited):
        visited[v] = True
        print(v, end=' ')

        for i in self.graph[v]:
            if not visited[i]:
                self.DFS_util(i, visited)

    def DFS(self, v):
        visited = [False]*len(self.graph)
        print("DFS:")
        self.DFS_util(v, visited)

    def BFS(self, s):
        visited = [False]*len(self.graph)
        queue = []

        visited[s] = True
        queue.append(s)

        print("\nBFS:")
        while queue:
            s = queue.pop(0)
            print(s, end=' ')

            for i in self.graph[s]:
                if not visited[i]:
                    visited[i] = True
                    queue.append(i)

g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)

g.DFS(0)
g.BFS(0)