编程完成基于邻接表的图的非递归深度遍历和广度遍历
时间: 2024-02-13 15:02:01 浏览: 17
好的,下面是基于邻接表的图的非递归深度遍历和广度遍历的 Python 代码实现。
首先,我们需要定义一个邻接表的类 Graph,用于表示图结构。在这个类中,我们需要实现添加节点、添加边、深度遍历和广度遍历等方法。
```
class Graph:
def __init__(self):
self.adj_list = {}
def add_node(self, node):
if node not in self.adj_list:
self.adj_list[node] = []
def add_edge(self, node1, node2):
if node1 not in self.adj_list:
self.adj_list[node1] = []
if node2 not in self.adj_list:
self.adj_list[node2] = []
self.adj_list[node1].append(node2)
self.adj_list[node2].append(node1)
```
接下来,我们实现非递归深度遍历方法 dfs。这个方法需要使用一个栈来存储待访问的节点。我们从起始节点开始访问,将其入栈,然后不断从栈中弹出节点,访问其邻居节点,并将其邻居节点入栈。直到栈为空时,遍历结束。
```
def dfs(self, start):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in self.adj_list[node]:
stack.append(neighbor)
```
最后,我们实现广度遍历方法 bfs。这个方法需要使用一个队列来存储待访问的节点。我们从起始节点开始访问,将其入队,然后不断从队列中弹出节点,访问其邻居节点,并将其邻居节点入队。直到队列为空时,遍历结束。
```
def bfs(self, start):
queue = [start]
visited = set()
while queue:
node = queue.pop(0)
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in self.adj_list[node]:
queue.append(neighbor)
```
完整代码如下:
```
class Graph:
def __init__(self):
self.adj_list = {}
def add_node(self, node):
if node not in self.adj_list:
self.adj_list[node] = []
def add_edge(self, node1, node2):
if node1 not in self.adj_list:
self.adj_list[node1] = []
if node2 not in self.adj_list:
self.adj_list[node2] = []
self.adj_list[node1].append(node2)
self.adj_list[node2].append(node1)
def dfs(self, start):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in self.adj_list[node]:
stack.append(neighbor)
def bfs(self, start):
queue = [start]
visited = set()
while queue:
node = queue.pop(0)
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in self.adj_list[node]:
queue.append(neighbor)
# example
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
print("DFS:")
g.dfs(1)
print()
print("BFS:")
g.bfs(1)
print()
```