大二数据结构课程设计，老师要求做一个地图，能添加或删除地点和路径，能够输出最短路径（这里我用的是dijkstra），然后还能输出任意两点之间全部路径（这里我用的是递归），后面老师提要求还做了一个简易的可视化，因为一直在网上找不到参考，所以我做完之后留给后来人。
代码有点乱凑合着看下，提供一下思路。
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
plt.rc("font",family='YouYuan')
class Map():
def __init__(self, n=0):
'''
这里创建邻接矩阵
'''
self.n = n
self.edges = []
self.peak = []
self.name = 0
self.information = []
self.path = 0
def load_edges(self):
'''这里噢，有个大坑用loc'''
print("Loading data from excel...", end="")
vex_data = pd.read_excel(r'D:\pythonProject\Map_Sys\vexdata.xlsx', index_col=0)
for i in range(len(vex_data)):
for j in range(len(vex_data)):
if vex_data.loc[i,j] == 0:
vex_data.loc[i,j] = float('inf')
k = vex_data.values.tolist()
for a in k:
self.edges.append(a)
map_data = pd.read_excel(r'D:\pythonProject\Map_Sys\Mapdata.xlsx',index_col=0)
for i in map_data.values.tolist():
self.information.append(i)
self.peak = list(map_data.index)
self.n = len(self.peak)
print(self.peak)
print(self.information)
def Add_v(self,name,coordinate,reation):
'''
这里使用了解包，第一次使用解包，解包是将前一个和前面的变量来对应，后面与后一个对应
'''
self.n = len(self.edges)
self.edges.append(reation)
for i in range(self.n):
a = int(reation[i])
if a == 0:
a = float('inf')
self.edges[i].append(a)
self.n += 1
self.information.append(coordinate)
self.peak.append(name)
print(self.edges)
def Add_road(self,first,end,data):
'''添加路径'''
i = self.peak.index(first)
j = self.peak.index(end)
self.edges[i][j] = data
self.edges[j][i] = data
def del_v(self, place):
'''这里是删除节点'''
node1 = self.peak.index(place)
self.edges.pop(node1)
for i in range(self.n-1):
self.edges[i].pop(node1)
self.n = self.n - 1
self.information.pop(node1)
self.peak.pop(node1)
print(self.information)
print(self.edges)
print(self.peak)
def del_road(self,first,end):
'''删除路径'''
self.edges[first][end] = float('inf')
self.edges[end][first] = float('inf')
def connect_peak(self):
print(self.n)
for i in range(self.n):
for j in range(self.n):
if self.edges[i][j] != 0 and i != j and self.edges[i][j] != float('inf'):
weight = self.information[i][0]-self.information[j][0]
highter = self.information[i][1] - self.information[j][1]
distance = round((weight**2+highter**2)**0.5,2)
self.edges[i][j] = self.edges[j][i] = distance
else:
self.edges[i][j] == float('inf')
print(self.edges)
def display_edges(self):
'''这里展示邻接矩阵'''
print(self.n)
a = self.edges
for i in range(len(self.edges)):
for j in range(len(self.edges)):
if a[i][j] == 0:
a[i][j] = float('inf')
df = pd.DataFrame(a,index=self.peak,columns=self.peak)
print(df)
def dijkstra(self,begin,end):
self.n = len(self.edges)
S = [0]*self.n #存已经遍历过的节点
dist = [-1]*self.n #与其余点间最短距离,注意这里的距离是说初始点与该点的距离，而是不是上一个与下一个的距离
rear_road = [-1]*self.n #后置节点
for i in range(self.n):
dist[i] = self.edges[begin][i]
if self.edges[begin][i] < float('inf') :
rear_road[i] = begin
else:
rear_road[i] = -1
S[begin] = 1
u = -1#这个就是个工具变量 ，让它变成接下来有值的后置节点
for i in range(self.n-1):
mindis = float('inf')
for j in range(self.n):
#这里最主要是要判断顶点有没有被遍历过，然后是不是与出发点有路径
if S[j] == 0 and dist[j]<mindis:
u = j
mindis = dist[j]
S[u] = 1
for j in range(self.n):
#判断是否j有没有被遍历
if S[j] == 0:
#这里是在看这个后置节点与它的后置节点是否有路径，同时判断begin-->j 是否大于 begin-->u+u-->j,如果要是小于的话就应该替换了
if self.edges[u][j]<float('inf') and dist[u]+self.edges[u][j] <dist[j]:
dist[j] = dist[u]+self.edges[u][j]
rear_road[j] = u
self.display_min_road(dist,rear_road,S,begin,end)
#这里还要进行一个排序
def display_min_road(self,dist,rear_road,S,begin,end):
min_road = []
min_node = []
min_dist = dist[end]
if S[begin] == 1 and begin != end:
min_road.append(end)
end = rear_road[end]
if end == -1:
raise Exception('似乎没有这个点耶')
while end != begin :
min_road.append(end)
end = rear_road[end]
min_road.append(begin)
min_road.reverse()
for i in min_road:
min_node.append(self.peak[i])
self.path = min_node
print(min_dist)
print(min_node)
def all_road(self,begin,end,road=[]):
'''
这里我想写一个全部路径，想法是遍历过的节点不能再次遍历。
'''
self.n = len(self.edges)
new_road = []
new_nodes = []
road = road + [begin]#这里如果用append的话会一直存D
data_begin = self.peak.index(begin)
if begin == end:
return road
for node in self.peak:
data_node = self.peak.index(node)
if self.edges[data_begin][data_node] != float('inf'):
if node not in road:
new_nodes = self.all_road(node, end, road)
for new_node in new_nodes:
if new_node == end:
road.append(new_node)
new_road.append(road)
print(new_road)
return new_road
def save_map(self):
'''这里我在考虑是否用mysql还是单纯的excel来存，不用想了，用excel'''
for i in range(self.n):
for j in range(self.n):
if self.edges[i][j] == float('inf'):
print(self.edges[i][j])
self.edges[i][j] = self.edges[j][i] = 0
f = open('vexdata.xlsx', 'w')
d = open('Mapdata.xlsx', 'w')
print(self.edges)
df_save = pd.DataFrame(self.edges)
fd_save = pd.DataFrame(self.information,columns=['x','y'])
df_save.to_excel('vexdata.xlsx')
fd_save.to_excel('Mapdata.xlsx')
f.close()
d.close()
def visualizatiom(self):
graph = nx.Graph()
graph_edges = []
graph.add_nodes_from(self.peak)
for i in range(self.n):
print(1)
for j in range(i + 1, self.n):
print(1)
if self.edges[i][j] != float('inf') and self.edges[i][j] != 0:
graph_edges.append(
(self.peak[i], self.peak[j], self.edges[i][j]))
print(1)
print(graph_edges)
graph.add_weighted_edges_from(graph_edges)
pos = nx.circular_layout(graph)
weights = nx.get_edge_attributes(graph, "weight")
nx.draw(graph, pos, with_labels=True, font_weight='bold')
nx.draw_networkx_edge_labels(graph, pos, edge_labels=weights)
plt.title('无向图')
plt.show()
def main(self):
while True:
print("-------------------------")
print("| 1、添加地点 |")
print("| 2、添加路线 |")
print("| 3、查询最优路径 |")
print("| 4、删除地点 |")
print("| 5、删除路径 |")
print("| 6、展示邻接矩阵 |")
print("| 7、全部路径 |")
print("| 8、储存数据 |")
print("| 9、观看地图 |")
print("| 10、结束进程 |")
print("-------------------------")
a = int(input('请输入你要选择的操作：'))
if a == 1:
reation = []
name = input('请输入你要添加的点的名称')
coordianx = int(input('请输入你要添加的点的x坐标'))
coordiany = int(input('请输入你要添加的点的y坐标'))
coordian = [coordianx,coordiany]
for i in self.peak:
print(f'新的节点与{i}的关系'.format(i = i))
j = int(input('请输入:'))
reation.append(j)
reation.append(0)
self.Add_v(name,coordian,reation)
print(self.information)
self.connect_peak()
elif a == 2:
frist = input('请输入你要修改两点中的第一点')
end = input('请输入你要修改两点中的第二点')
data = int(input('请输入你要修改的值'))
self.Add_road(frist,end,data)
elif a == 3:
frist = input('请输入最短两点中的第一点')
end = input('请输入最短两点中的第二点')
i = self.peak.index(frist)
j = self.peak.index(end)
self.dijkstra(i,j)
elif a == 4:
place = input('请输入你要修改的点')
self.del_v(place)
elif a == 5:
frist = input('请输入删除路径两点中的第一点')
end = input('请输入删除路径两点中的第二点')
i = self.peak.index(frist)
j = self.peak.index(end)
self.del_road(i,j)
elif a == 6:
self.display_edges()
elif a == 7:
frist = input('请输入全部路径两点中的第一点')
end = input('请输入全部路径两点中的第二点')
self.all_road(frist,end)
elif a == 8:
self.save_map()
elif a == 9:
self.visualizatiom()
elif a == 10:
break
if __name__ == '__main__':
data = Map()
data.load_edges()
data.main()一个遗憾，没有用mysql，一直用pandas将数据存储在xlsx
同样，要运行本程序需要在同文件下创建一个vexdata.xlsx文件和Mapdata.xlsx文件，同时这里面需要数据
1.vexdata.xlsx需要邻接矩阵的数据，如下为参考
2.Mapdata.xlsx需要每个点的坐标，如下为参考
如果还有什么问题可以评论区提出来，本人基本上可以隔天回复
文章出处登录后可见！
已经登录？立即刷新
