使用字典建立图形资料结构

字典键值对应串列如下，配合图表更容易理解。

• G[0]:[1,2,3]
• G[1]:[0,2,3,4]
• G[2]:[0,1]
• G[3]:[0,1]
• G[4]:[1]

import sys

#使用字典建立Graph
G={}
#不断输入一个数字到变数line
for line in sys.stdin:
    #将变数line转换成整数储存到变数n，表示有几个边要输入
    n = int(line)
    #使用回圈变数i，从0到n-1，每次递增1，回圈执行n次
    for i in range(n):
        #每次输入两个整数到变数a跟b，表示边的两个顶点
        a, b =input().split()
        a = int(a)
        b = int(b)
        # a在字典G内
        # 如果字典G包含键值a，则将b加入到G[a]的最後，表示点a可以到点b
        if a in G.keys():
            G[a].append(b)
        # 否则建立新的键值a对应到串列，该串列有一个元素b
        else:
            G[a]=[b]
        # 如果字典G包含键值b，将a加入到G[b]的最後，表示点b可以到点a
        if b in G.keys():
            G[b].append(a)
        # 否则建立新的键值b对应到串列，该串列有一个元素a，表示点b可以到点a
        else:
            G[b]=[a]

程序码参考资料：资料结构使用Python

深度优先搜寻(Depth-First Search(DFS))

深度优先搜寻具有深入单一路径往下探查的特徵，广度优先搜寻和深度优先搜寻的搜寻顺序大不相同，但过程的差异只有一个，也就是要从选项的顶点中选择哪个点。

顶点选项：「後进先出」(LIFO)的方式管理，可以用「堆叠」的资料结构

广度优先搜寻是选择最早被加入选项的顶点，因为先从距离起点较近的顶点开始搜寻，所以会从起点附近依序探查。
深度优先搜寻是选择最晚被加入的顶点，所以并不折返，而是一直深入新开发的路径

使用DFS找最长路径长度

# 使用字典将节点名称转换为节点编号，将边的节点编号加入图形资料结构中，以字典表示，最後使用DFS，找出最长边的个数

G = {}
City = {}
# 宣告阵列v为一维整数阵列，有210个元素，每个元素初始化为0
v = [0]*210
# 初始化md为0
md = 0
# 将节点名称转换为数字，使用字串p为输入，将节点名称p转换为节点编号
def getCityIndex(p):
    if p not in City.keys():
        City[p].len(City)
    return City[p]

# DFS找寻最深的深度
def DFS(x,level):
    # 存取第4行全域变数
    global md 
    # 使用回圈读取节点编号x的所有边可以连结出去的节点，回圈变数i由0到G[x]的长度减1
    for i in range(len(G[x])):
        # 若level > md，则md = level，md为最长路径边数
        if level > md:
            md = level
        # 设定变数target为G[x][i]，G[x][i]表示读取G[x]的第i个元素
        target = G[x][i]
        # 变数target设定为能由节点编号x连结出去的节点G[x][i]
        # 若v[target]等於1，表示已拜访过，使用continue跳到回圈开头
        if v[target] == 1:
            continue
        v[target] = 1
        DFS(target,level+1)
# m = 输入边的个数到
m = int(input())

# 回圈跑m次，每次输入两个节点a和b
for i in range(m):
    a, b = input().split()
    a = getCityIndex(a)
    b = getCityIndex(b)
    # a在字典G内
    # 如果字典G包含键值a，则将b加入到G[a]的最後，表示点a可以到点b
    if a in G.keys():
        G[a].append(b)
    else:
        G[a] = [b]
    # b在字典G内
    if b in G.keys():
        G[b].append(a)
    else:
        G[b] = [a]

# 输入字串到字典City查询节点编号
start = City[input()]
#使用DFS走访，输入start与0，表示从start开始，且阶层开始为0
DFS(start, 0)
print(md)

程序码参考资料：资料结构使用Python