图的深度优先搜索、广度优先搜索知识点

以下是关于图的深度优先搜索和广度优先搜索的知识点：

1. 深度优先搜索（DFS）：从图的某个顶点开始遍历，沿着一条路径访问未被访问过的顶点，直到该路径最后一个顶点被访问完毕，然后回溯到前一个顶点，继续访问它的其他相邻顶点，直到所有顶点都被访问过为止。DFS通常使用栈来实现，每次访问一个顶点时，将其标记为已访问，并将其压入栈中，然后访问其相邻顶点，重复此过程直到栈为空。

2. 广度优先搜索（BFS）：从图的某个顶点开始遍历，先访问该顶点的所有相邻顶点，然后依次访问这些相邻顶点的相邻顶点，直到所有顶点都被访问过为止。BFS通常使用队列来实现，每次访问一个顶点时，将其标记为已访问，并将其加入队列中，然后访问队列中的下一个顶点，重复此过程直到队列为空。

下面是两个Python实现的例子：

1. 深度优先搜索

# 定义一个图类
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    # 添加顶点
    def add_vertex(self, vertex):
        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = []

    # 添加边
    def add_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.__graph_dict:
            self.__graph_dict[vertex1].append(vertex2)
        else:
            self.__graph_dict[vertex1] = [vertex2]

    # DFS遍历
    def dfs(self, start_vertex):
        visited = set()
        stack = [start_vertex]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(set(self.__graph_dict[vertex]) - visited)
        return visited

# 创建一个图实例
graph = Graph()

# 添加顶点和边
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_edge({'A', 'B'})
graph.add_edge({'B', 'C'})
graph.add_edge({'C', 'D'})
graph.add_edge({'D', 'A'})

# 执行DFS遍历
print(graph.dfs('A')) # 输出：{'A', 'B', 'C', 'D'}

2. 广度优先搜索

# 定义一个图类
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    # 添加顶点
    def add_vertex(self, vertex):
        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = []

    # 添加边
    def add_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.__graph_dict:
            self.__graph_dict[vertex1].append(vertex2)
        else:
            self.__graph_dict[vertex1] = [vertex2]

    # BFS遍历
    def bfs(self, start_vertex):
        visited = set()
        queue = [start_vertex]
        while queue:
            vertex = queue.pop(0)
            if vertex not in visited:
                visited.add(vertex)
                queue.extend(set(self.__graph_dict[vertex]) - visited)
        return visited

# 创建一个图实例
graph = Graph()

# 添加顶点和边
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_vertex('D')
graph.add_edge({'A', 'B'})
graph.add_edge({'B', 'C'})
graph.add_edge({'C', 'D'})
graph.add_edge({'D', 'A'})

# 执行BFS遍历
print(graph.bfs('A')) # 输出：{'A', 'B', 'C', 'D'}