图的遍历算法数据结构

图的遍历算法是指从图的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有结点访问一次且仅一次的算法。常见的图的遍历算法有深度优先搜索和广度优先搜索两种。

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后递归地访问每个子节点。具体来说，DFS从根节点开始，访问一个未被访问过的节点，然后继续访问该节点的未被访问过的邻居节点，直到所有节点都被访问过为止。

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。在这个算法中，首先访问根节点，然后访问根节点的所有邻居节点，然后访问邻居节点的所有未被访问过的邻居节点，以此类推，直到所有节点都被访问过为止。

在实现图的遍历算法时，常用的数据结构有邻接表和邻接矩阵。邻接表是一种链式存储结构，用于表示图中的每个节点及其邻居节点。邻接矩阵是一种二维数组，用于表示图中每个节点之间的关系。

下面是一个使用邻接表实现的深度优先搜索的Python代码示例：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for i in range(vertices)]

    def addEdge(self, u, v):
        self.adj[u].append(v)

    def DFSUtil(self, v, visited):
        visited[v] = True
        print(v, end=' ')
        for i in self.adj[v]:
            if not visited[i]:
                self.DFSUtil(i, visited)

    def DFS(self, v):
        visited = [False] * self.V
        self.DFSUtil(v, visited)

下面是一个使用邻接表实现的广度优先搜索的Python代码示例：

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for i in range(vertices)]

    def addEdge(self, u, v):
        self.adj[u].append(v)

    def BFS(self, s):
        visited = [False] * self.V
        queue = deque()
        queue.append(s)
        visited[s] = True
        while queue:
            s = queue.popleft()
            print(s, end=' ')
            for i in self.adj[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True