图的广度优先搜索 实现一个函数 `dfs`,接受一个有向图和起始节点作为参数,并返回从起始节点开始的深度优先搜索遍历结果。 要求使用递归方式实现深度优先搜索算法。
时间: 2024-02-06 17:09:04 浏览: 27
抱歉,您提到的是广度优先搜索,而不是深度优先搜索。下面是广度优先搜索的实现,使用队列实现:
```python
from collections import deque
def bfs(graph, start):
visited = set() # 记录已经访问过的节点
queue = deque([start]) # 初始化队列,将起始节点加入队列
visited.add(start) # 将起始节点标记为已访问
result = [] # 记录遍历的结果
while queue: # 队列不为空
node = queue.popleft() # 取出队首节点
result.append(node) # 将节点加入遍历结果中
for neighbor in graph[node]: # 遍历当前节点的邻居节点
if neighbor not in visited: # 如果邻居节点没有被访问过
visited.add(neighbor) # 标记为已访问
queue.append(neighbor) # 将邻居节点加入队列
return result
```
其中,`graph` 表示有向图,使用字典表示。字典的键为节点,值为该节点的邻居节点列表。`start` 表示起始节点。函数返回从起始节点开始的广度优先搜索遍历结果。
相关问题
用python完成以下题目代码 题目一:链表实现 创建一个 `LinkedList` 实例,进行以下操作: - 在链表末尾添加节点值为 1。 - 在链表末尾添加节点值为 2。 - 在链表末尾添加节点值为 3。 - 打印链表中所有节点的值。 - 删除节点值为 2 的节点。 - 打印链表中所有节点的值。 题目二:二分查找: 实现一个函数 `binary_search`,接受一个已排序的整数列表 `nums` 和一个目标值 `target`,返回目标值在列表中的索引位置。如果目标值不存在于列表中,则返回 -1。 要求使用迭代方式实现二分查找算法。 题目三:选择排序 实现一个函数 `selection_sort`,接受一个整数列表作为参数,并返回排序后的列表。 要求使用选择排序算法对列表进行排序。 题目四:图的广度优先搜索 实现一个函数 `dfs`,接受一个有向图和起始节点作为参数,并返回从起始节点开始的深度优先搜索遍历结果。 要求使用递归方式实现深度优先搜索算法。
题目一:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def addNode(self, data):
newNode = Node(data)
if self.head is None:
self.head = newNode
else:
current = self.head
while current.next is not None:
current = current.next
current.next = newNode
def printList(self):
current = self.head
while current is not None:
print(current.data)
current = current.next
def deleteNode(self, data):
current = self.head
if current is not None and current.data == data:
self.head = current.next
current = None
return
else:
while current is not None:
if current.data == data:
break
prev = current
current = current.next
if current == None:
return
prev.next = current.next
current = None
# Create a linked list instance
linkedList = LinkedList()
# Add nodes to the linked list
linkedList.addNode(1)
linkedList.addNode(2)
linkedList.addNode(3)
# Print all nodes in the linked list
linkedList.printList()
# Delete the node with value 2
linkedList.deleteNode(2)
# Print all nodes in the linked list again
linkedList.printList()
```
题目二:
```python
def binary_search(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
# Example usage
nums = [1, 3, 5, 7, 9]
target = 5
result = binary_search(nums, target)
print(result)
```
题目三:
```python
def selection_sort(nums):
for i in range(len(nums)):
min_index = i
for j in range(i+1, len(nums)):
if nums[j] < nums[min_index]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
# Example usage
nums = [64, 25, 12, 22, 11]
sorted_nums = selection_sort(nums)
print(sorted_nums)
```
题目四:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
return visited
# Example usage
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
dfs(graph, 'A')
```
图的建立和广度优先搜索和深度优先搜素遍历完整代码
先来看看图的建立。以下是一个有向图的建立过程:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
```
这里使用了一个 defaultdict 来存储图的信息,每个节点对应一个列表,存储与该节点相邻的节点。
接下来是广度优先搜索的代码:
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex)
queue.extend(graph[vertex] - visited)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
bfs(g.graph, 2)
```
在广度优先搜索中,我们使用了一个队列来存储待处理的节点。我们从起始节点开始,将其加入队列中,然后遍历队列中的每个节点,将其相邻的节点加入队列中。在遍历过程中,我们还需要使用一个 visited 集合来记录已经遍历过的节点,避免重复遍历。
最后是深度优先搜索的代码:
```python
def dfs(graph, start):
visited = set()
def dfs_helper(vertex):
visited.add(vertex)
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_helper(neighbor)
dfs_helper(start)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
dfs(g.graph, 2)
```
在深度优先搜索中,我们使用了递归来遍历每个节点。我们从起始节点开始,遍历其相邻的节点,对于每个相邻的节点,如果它没有被访问过,就递归调用 dfs_helper 函数。在遍历过程中,我们同样需要使用一个 visited 集合来记录已经遍历过的节点,避免重复遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)