图的邻接表表示法及遍历

邻接表是一种图的表示方法，它用链表来表示每个顶点相邻顶点的集合，具体来说，邻接表中每个顶点都对应一个链表，链表中存储该顶点与其它顶点相邻的边的信息，这种方法可以节省存储空间，适用于稀疏图。

以下是邻接表的示例图：

    1 -- 2 -- 3
    |         |
    4 -- 5 -- 6

对应的邻接表如下：

1 -> 2 -> 4
2 -> 1 -> 3 -> 5
3 -> 2 -> 6
4 -> 1 -> 5
5 -> 2 -> 4 -> 6
6 -> 3 -> 5

图的遍历是指按一定的规则依次访问图中的所有顶点，常用的有深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历的基本思想是从一个顶点开始，尽可能深地探索每个分支，直到到达最深处，然后回溯到前一个节点，再继续探索其他分支。具体实现可以使用递归或栈来实现。

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

def dfs(graph, start):
    visited = set()  # 记录已访问的节点
    stack = [start]  # 用栈来实现深度优先遍历
    while stack:
        node = stack.pop()  # 弹出栈顶节点
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            for neighbor in graph[node]:
                stack.append(neighbor)

对于上述示例图，从顶点1开始进行深度优先遍历，输出结果为：1 4 5 2 3 6。

广度优先遍历的基本思想是先访问起始顶点的所有邻接顶点，再逐层向外访问其它顶点，具体实现可以使用队列来实现。

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

from collections import deque

def bfs(graph, start):
    visited = set()  # 记录已访问的节点
    queue = deque([start])  # 用队列来实现广度优先遍历
    while queue:
        node = queue.popleft()  # 弹出队列头节点
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            for neighbor in graph[node]:
                queue.append(neighbor)

对于上述示例图，从顶点1开始进行广度优先遍历，输出结果为：1 2 4 3 5 6。