Python实现图(Graph)算法

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

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

    def dfs(self, node):
        visited = [False] * self.vertices
        self.dfs_util(node, visited)

    def dfs_util(self, node, visited):
        visited[node] = True
        print(node, end=" ")

        for i in range(self.vertices):
            if self.graph[node][i] == 1 and not visited[i]:
                self.dfs_util(i, visited)

    def bfs(self, node):
        visited = [False] * self.vertices
        queue = []

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

        while queue:
            node = queue.pop(0)
            print(node, end=" ")

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


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

print("Depth First Traversal")
g.dfs(0)

print("\nBreadth First Traversal")
g.bfs(0)

Depth First Traversal
0 1 2 3 4 
Breadth First Traversal
0 1 4 2 3