图的邻接表表示法及遍历代码实现

邻接表是一种表示图的数据结构，它将每个顶点与其相邻的顶点列表联系起来。邻接表通常用于表示稀疏图，因为它可以节省存储空间。下面是邻接表的实现方式：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

在这个实现中，我们创建了一个大小为`num_vertices`的空列表，用于存储每个顶点的邻居。`add_edge`方法用于将两个顶点之间的边添加到邻接表中。

接下来，我们来看一下如何遍历一个图。遍历图有两种基本方法：深度优先搜索（DFS）和广度优先搜索（BFS）。这里我们提供DFS的实现方式：

def dfs(self, start):
    visited = [False] * self.num_vertices
    self._dfs(start, visited)

def _dfs(self, curr, visited):
    visited[curr] = True
    print(curr, end=' ')
    for neighbor in self.adj_list[curr]:
        if not visited[neighbor]:
            self._dfs(neighbor, visited)

在这个实现中，我们使用了一个辅助函数`_dfs`来进行递归调用。我们首先将当前顶点标记为已访问，并将其打印出来。然后，我们遍历该顶点的所有邻居，如果邻居未被访问，则递归调用`_dfs`函数。

以下是一个完整的示例：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)
    
    def dfs(self, start):
        visited = [False] * self.num_vertices
        self._dfs(start, visited)

    def _dfs(self, curr, visited):
        visited[curr] = True
        print(curr, end=' ')
        for neighbor in self.adj_list[curr]:
            if not visited[neighbor]:
                self._dfs(neighbor, visited)

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.dfs(0)  # 输出: 0 1 2 3 4

在这个例子中，我们创建了一个大小为5的图，并添加了一些边。然后我们从顶点0开始进行DFS遍历，输出结果为`0 1 2 3 4`。