1.图

1.3图的存储结构(python实现有向图)

1.3.1邻接矩阵

G=[
[0,1,0,0,0,1],
[0,0,1,1,0,0],
[0,0,0,1,0,0],
[0,0,0,0,1,1],
[0,0,0,0,1,1],
[0,0,0,0,0,0]
]

1.3.2邻接列表(字典)

G=[
[1,5],
[2,3,5],
[3],
[4,5],
[5],
[]
]

G={
'a':{'b','f'},
'b':{'c','d','f'},
'c':{'d'},
'd':{'e','f'},
'e':{'f'},
'f':{}
}

2.广度优先搜索

#迭代版bfs
import collections

def bfs(G,s):
#P为记录每一个节点的父节点的字典
P={s:None}
Q=collections.deque()
Q.append(s)
while Q:
u=Q.popleft()
for v in G[u]:
if v in P.keys():
continue
P[v]=P.get(v,u)
Q.append(v)
return P

#图的邻接字典
G={
'a':{'b','f'},
'b':{'c','d','f'},
'c':{'d'},
'd':{'e','f'},
'e':{'f'},
'f':{}
}

P=bfs(G,'a')
print(P)

#获取a至e的路径
u='e'
path=[u]
while P[u] is not None:
path.append(P[u])
u=P[u]
path.reverse()
print(path)

3.深度优先搜索

迭代版DFS
def dfs(G,s):
Q=[]
S=set()
Q.append(s)
while Q:
u=Q.pop()
if u in S:
continue
Q.extend(G[u])
yield u
#有向无环图的邻接字典
G={
'a':{'b','f'},
'b':{'c','d','f'},
'c':{'d'},
'd':{'e','f'},
'e':{'f'},
'f':{}
}

res=list(dfs(G,'a'))
print(res) 

0 条评论

相关文章

POJ 1659 Frogs' Neighborhood(可图性判定—Havel-Hakimi定理)【超详解】

Frogs' Neighborhood Time Limit: 5000MS Memory Limit: 10000K Total Submis...

2988

1714

3465

4347

3866

3224

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

1011

1573

2101

基础野：细说无符号整数

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

2056