项目目标:使用BFS查找出两站地铁间的最短路径

Git地址(包括BFS,UndirectedGraph的实现):https://github.com/Vacant2333/Python3-DataStruct-Algorithm/tree/master/Project/1.WuhanMetroRouteFinding

第一步:先把地铁线路+站点爬下来
数据来源: http://wh.bendibao.com/ditie/linemap.shtml

文件:line_data_spider.py

import requests
from bs4 import BeautifulSoup


def get_line_data():
    url = 'http://wh.bendibao.com/ditie/linemap.shtml'
    soup = BeautifulSoup(requests.get(url).text, 'html.parser')
    # Metro line data
    line_data = {}
    for line_div in soup.find_all("div", class_="line-list"):
        # Heading div
        heading_div = line_div.findChildren(class_="line-list-heading")
        wrap_div = heading_div[0].findChildren(class_="wrap")
        line_name = wrap_div[0].strong.a.contents[0][2:-3]
        all_station_div = line_div.findChildren(class_="line-list-station")[0].findChildren(class_="station")
        # Init the line
        line_data[line_name] = []
        # Add all station name to the line
        for station_div in all_station_div:
            # Get a label by condition (class = "link")
            real_station_div = station_div.findChildren(class_="link")[0]
            line_data[line_name].append(real_station_div.contents[0])
    return line_data

结果图:

第二步:将刚才拿到在数据转为Graph(node + edge)并显示
文件:get_line_graph.py

import Spider
import networkx as nx
import matplotlib.pyplot as plt

line_data = Spider.get_line_data()
nodes = {}
edges = {}
# Last station
last_station_name = ''
for line in line_data.values():
    for station in line:
        # Key: station name, value: node color
        nodes[station] = 'green'
        if last_station_name != '' and last_station_name != station:
            # Save edge(link station)
            edges[(last_station_name, station)] = 'black'
        last_station_name = station
    last_station_name = ''
graph = nx.Graph()
# Add nodes and graph to graph
graph.add_nodes_from(nodes)
graph.add_edges_from(edges.keys())
# For chinese
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
# Canvas size: 8000*4000
plt.figure(figsize=(80, 40))
nx.draw(graph, with_labels=True, node_size=[750], font_size=50, width=6, node_color=nodes.values(), edge_color=edges.values())
plt.show()

结果图(还是很不错的哈):

第三步:用广度优先搜索(BFS)寻找出两个车站的最短路径
import的两个类来自github中另外两个文件,详细可在文章开头git链接找到
文件:find_route.py

from Graph.DataStruct.UndirectedGraph import UndirectedGraph
from Graph.Algorithm.BreadthFirstSearch import BreadthFirstSearch2
import line_data_spider

line_data = line_data_spider.get_line_data()
nodes = []
edges = []
# Last station
last_station_name = ''
for line in line_data.values():
    for station in line:
        # Key: station name, value: node color
        nodes.append(station)
        if last_station_name != '' and last_station_name != station:
            # Save edge(link station)
            edges.append([station, last_station_name])
        last_station_name = station
    last_station_name = ''

# Remove duplicate
nodes = list(set(nodes))
# Dirty data
edges.remove(['中南路', '洪山广场'])

graph = UndirectedGraph()
graph.add_node(nodes)
graph.add_edge(edges)

print(BreadthFirstSearch2().run(graph, '天河机场', '佛祖岭'))
print(BreadthFirstSearch2().run(graph, '石桥', '中山公园'))

这里有个坑,2和4号线都会经过中南路和洪山广场 导致edge 重复了,所以要remove一下去掉脏数据
结果图:

附上一张官方的路线图: