解释self.Graph = defaultdict(set)

在 Python 中，defaultdict 是一种字典类型，它为字典中的每个键提供了默认值。如果访问字典中不存在的键，则会自动创建该键并将其值设置为默认值。

在这个例子中，我们创建了一个 defaultdict 类型的字典 self.Graph，它的每个键都是一个集合（set）。这个字典被用来表示一个无向图的邻接表，其中每个节点的邻居节点被存储在一个 set 中。

如果我们想要添加一个新的边 (u, v) 到这个无向图中，我们可以执行以下操作：

self.Graph[u].add(v)
self.Graph[v].add(u)

这将在 u 的邻居列表中添加 v，并在 v 的邻居列表中添加 u。由于这是一个无向图，所以每个边都需要在两个节点之间添加。由于我们使用了 defaultdict，即使某个节点的邻居列表为空，我们也可以直接添加新的邻居节点，而不需要进行额外的检查。

相关问题

数据结构无向图的dfs算法代码

以下是数据结构无向图的DFS算法代码示例：

# 定义一个Graph类
class Graph:
    # 初始化方法
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = defaultdict(list)  # 用字典表示图

    # 添加边的方法
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    # DFS遍历方法
    def DFS(self, v, visited):
        visited.add(v)  # 将当前节点标记为已访问
        print(v, end=' ')

        # 递归访问邻接节点
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFS(neighbour, visited)

    # DFS遍历入口方法
    def DFS_traversal(self):
        visited = set()  # 初始化已访问节点集合

        # 遍历所有未访问的节点
        for vertex in list(self.graph):
            if vertex not in visited:
                self.DFS(vertex, visited)

采用图的邻接表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

以下是基于邻接表的有向图和无向图的DFS和BFS操作的Python实现：

from collections import defaultdict, deque

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

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

    def dfs(self, start):
        visited = set()
        self.dfs_util(start, visited)

    def dfs_util(self, vertex, visited):
        visited.add(vertex)
        print(vertex, end=' ')

        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self.dfs_util(neighbor, visited)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=' ')

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

# 示例
g = Graph(directed=True)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("DFS traversal:")
g.dfs(2)

print("\nBFS traversal:")
g.bfs(2)

输出结果为：

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

可以看到，DFS和BFS分别从节点2开始遍历了整个有向图。同样的代码也适用于无向图，只需要将`Graph`构造函数中的`directed`参数设置为`False`即可。