帮我创建一个图类,它的边应该带有权重,成员方法中应该包含创建图、添加节点、删除节点、展示图、寻找最短路径、深度优先搜索、广度优先搜索等方法
时间: 2023-09-28 11:03:21 浏览: 44
以下是一个基础的图类,包含了边带有权重、创建图、添加节点、删除节点、展示图、寻找最短路径、深度优先搜索、广度优先搜索等方法:
```
class Graph:
def __init__(self):
self.nodes = set()
self.edges = {}
self.weights = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, weight):
self._add_edge(from_node, to_node, weight)
self._add_edge(to_node, from_node, weight)
def _add_edge(self, from_node, to_node, weight):
if from_node not in self.edges:
self.edges[from_node] = []
self.edges[from_node].append(to_node)
self.weights[(from_node, to_node)] = weight
def remove_node(self, value):
self.nodes.discard(value)
for node, edges in self.edges.items():
try:
edges.remove(value)
del self.weights[(node, value)]
except ValueError:
pass
try:
del self.edges[value]
except KeyError:
pass
def remove_edge(self, from_node, to_node):
self.edges[from_node].remove(to_node)
del self.weights[(from_node, to_node)]
def show(self):
for node in self.nodes:
print(node, "->", self.edges[node])
def dijkstra(self, start, end):
shortest_distance = {}
predecessor = {}
unseen_nodes = self.nodes.copy()
infinity = 999999999
path = []
for node in unseen_nodes:
shortest_distance[node] = infinity
shortest_distance[start] = 0
while unseen_nodes:
current_node = None
for node in unseen_nodes:
if current_node is None:
current_node = node
elif shortest_distance[node] < shortest_distance[current_node]:
current_node = node
for neighbour, weight in self._get_neighbours(current_node):
if weight + shortest_distance[current_node] < shortest_distance[neighbour]:
shortest_distance[neighbour] = weight + shortest_distance[current_node]
predecessor[neighbour] = current_node
unseen_nodes.discard(current_node)
current_node = end
while current_node != start:
try:
path.insert(0, current_node)
current_node = predecessor[current_node]
except KeyError:
print("Path not reachable")
break
path.insert(0, start)
if shortest_distance[end] != infinity:
print("Shortest distance is", shortest_distance[end])
print("And the path is", path)
def _get_neighbours(self, node):
return [(n, self.weights[(node, n)]) for n in self.edges[node]]
def dfs(self, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for neighbour in self.edges[node]:
if neighbour not in visited:
self.dfs(neighbour, visited)
def bfs(self, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
current_node = queue.pop(0)
print(current_node)
for neighbour in self.edges[current_node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
```
其中,`nodes` 用于存储节点,`edges` 用于存储边,`weights` 用于存储边的权重。
`add_node` 方法用于添加节点,`add_edge` 方法用于添加带有权重的边,`remove_node` 方法用于删除节点,`remove_edge` 方法用于删除边,`show` 方法用于展示图。
`dijkstra` 方法用于寻找最短路径,`dfs` 方法用于深度优先搜索,`bfs` 方法用于广度优先搜索。
使用方法示例:
```
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_edge(1, 2, 10)
g.add_edge(2, 3, 20)
g.add_edge(1, 3, 30)
g.show()
g.dijkstra(1, 3)
g.dfs(1)
g.bfs(1)
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)