图的深度优先遍历和宽度优先遍历

以下是图的深度优先遍历和宽度优先遍历的介绍：

深度优先遍历（DFS）：
深度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，尽可能深地搜索每个分支，直到到达最深的结点，然后回溯到前一个结点，继续搜索另一个分支，直到所有结点都被访问为止。深度优先遍历使用栈来实现，因此也称为“栈搜索”。

以下是深度优先遍历的Python代码示例：

# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict
 
# This class represents a directed graph using
# adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # default dictionary to store graph
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    # A function used by DFS
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited
        # and print it
        visited.add(v)
        print(v, end=' ')
 
        # Recur for all the vertices
        # adjacent to this vertex
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)
 
    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self, v):
 
        # Create a set to store visited vertices
        visited = set()
 
        # Call the recursive helper function
        # to print DFS traversal
        self.DFSUtil(v, visited)

宽度优先遍历（BFS）：
宽度优先遍历是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，逐层遍历每个结点的所有子结点，直到到达最深的结点。宽度优先遍历使用队列来实现。

以下是宽度优先遍历的Python代码示例：

# Python3 program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict
 
# This class represents a directed graph
# using adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # default dictionary to store graph
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    # Function to print a BFS of graph
    def BFS(self, s):
 
        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph) + 1)
 
        # Create a queue for BFS
        queue = []
 
        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited[s] = True
 
        while queue:
 
            # Dequeue a vertex from
            # queue and print it
            s = queue.pop(0)
            print(s, end=" ")
 
            # Get all adjacent vertices of the
            # dequeued vertex s. If a adjacent
            # has not been visited, then mark it
            # visited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True