图的创建和遍历代码

在计算机科学领域中，图是一种非常重要的数据结构，它可以用来表示现实世界中的各种复杂关系和问题。创建和遍历图是图论中的基本操作之一，也是许多算法和应用的基础。本文将从多个角度分析图的创建和遍历代码，并介绍几种常见的图遍历算法。

图的创建

在计算机科学中，图是由节点（vertex）和边（edge）组成的。我们可以使用邻接表（adjacency list）或邻接矩阵（adjacency matrix）来表示图。邻接表是以每个节点为起点的边列表，而邻接矩阵则是一个$n$x$n$的矩阵，其中第$i$行$j$列表示从节点$i$到节点$j$是否有一条边。

下面是使用邻接表创建无向图的代码示例：

```

class Graph:

def __init__(self, vertices):

self.V = vertices

self.adj = [[] for i in range(vertices)]

def add_edge(self, v, w):

self.adj[v].append(w)

self.adj[w].append(v)

if __name__ == '__main__':

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)

```

在上面的代码中，我们首先定义了一个类`Graph`来表示图，其中包括节点数和邻接表。在初始化函数`__init__`中，我们指定节点数并创建一个空的邻接表。在添加边的函数`add_edge`中，我们通过改变起始节点的邻接表来添加新边。注意，在无向图中，每条边都要添加两次（分别由两个端点加入它们对应的邻接表）。

我们还可以使用邻接矩阵来创建图：

```

class Graph:

def __init__(self, vertices):

self.V = vertices

self.adj = [[0] * vertices for i in range(vertices)]

def add_edge(self, v, w):

self.adj[v][w] = 1

self.adj[w][v] = 1

if __name__ == '__main__':

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)

```

在上面的代码中，我们定义了一个类`Graph`和两个函数`__init__`和`add_edge`，与邻接表的实现非常相似。不同之处在于，我们创建的是一个二维矩阵，每个元素表示边的存在（1）或不存在（0）。

图的遍历

图的遍历是指以某个节点为起点，访问图中所有其他节点的过程。常见的图遍历算法有广度优先搜索（BFS）和深度优先搜索（DFS）。

广度优先搜索（BFS）按层次遍历图，先访问距离起点节点一步的所有节点，然后访问距离起点节点两步的所有节点，以此类推。我们可以使用队列来实现BFS算法。下面是BFS的代码示例：

```

class Graph:

def __init__(self, vertices):

self.V = vertices

self.adj = [[] for i in range(vertices)]

def add_edge(self, v, w):

self.adj[v].append(w)

def bfs(self, s):

visited = [False] * self.V

queue = []

queue.append(s)

visited[s] = True

while queue:

s = queue.pop(0)

print(s, end=" ")

for i in self.adj[s]:

if not visited[i]:

queue.append(i)

visited[i] = True

if __name__ == '__main__':

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.bfs(2)

```

在上面的代码中，我们创建了一个新的函数`bfs`来实现广度优先搜索算法。我们使用了两个辅助变量，一个数组`visited`来标记是否访问过，一个队列`queue`来存储已经访问的节点。在BFS的过程中，我们首先将起点加入队列，并标记为已访问。然后我们从队列的头部取出一个节点并打印。接下来，我们将所有与该节点直接相连的且未访问过的节点加入队列，并标记为已访问。重复以上步骤，直到队列为空。

深度优先搜索（DFS）从起点节点开始，以某种顺序探索图的所有分支，直到找到所有的节点或者被遇到一个没有未被访问的相邻节点的节点为止。我们可以使用递归或栈来实现DFS算法。下面是DFS的代码示例：

```

class Graph:

def __init__(self, vertices):

self.V = vertices

self.adj = [[] for i in range(vertices)]

def add_edge(self, v, w):

self.adj[v].append(w)

def dfs_util(self, v, visited):

visited[v] = True

print(v, end=" ")

for i in self.adj[v]:

if not visited[i]:

self.dfs_util(i, visited)

def dfs(self, s):

visited = [False] * self.V

self.dfs_util(s, visited)

if __name__ == '__main__':

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(2)

```

在上面的代码中，我们创建了两个函数`dfs_util`和`dfs`来实现深度优先搜索算法。在`dfs_util`函数中，我们首先标记节点为已访问，并打印节点。然后我们递归访问这个节点的相邻节点，直到所有的节点都被访问过。`dfs`函数通过调用`dfs_util`函数来实现深度优先搜索。