图的抽象数据结构
图：表示多对多的关系，包含一组顶点，采用V表示顶点集合，以及一组边，采用E表示边集合，边为顶点对；
无向图：所以边均为无向
有向图：存在边为有向
抽象数据类型:
图的表示形式：
邻接矩阵 ：G[i][j]=1 (i,j存在一条边，其余为0)，直观、容易理解，亦寻找其所有顶点的领接点，缺点为浪费一半的物理空间；
邻接表： [Gij...] Gij的下标为 i*(i+1)/2+j ,判断是否为1即可
图的遍历
图的查找：
def Find_path(graph,start,end,path=''):
path=path+start
if start==end:
return path
elif start not in graph.keys():
return None
for node in graph[start]:
if node not in path:
newpath=Find_path(graph,node,end,path)
if newpath:
return newpath
return None
def FindPaths(graph,start,end,path=''):
path=path+start
if start==end:
return path
elif start not in graph.keys():
return ''
paths=[]
for node in graph[start]:
newpaths=FindPaths(graph,node,end,path)
paths.append(newpaths)
return paths
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph[start]:
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
paths.append(newpaths)
return paths
def findshort(graph,start,end,path=''):
path=path+start
if start==end:
return path
elif not graph[start]:
return ''
short=None
for node in graph[start]:
if node not in path:
newpath=findshort(graph,node,end,path)
if newpath:
if not short or len(newpath)<len(short):
short=newpath
return short
graph = {'A': ['B', 'C','F'], #采用字典及列表模拟图（邻接矩阵）
'B': ['C', 'D'],
'C': ['D'],
'D': ['C','A'],
'E': ['F'],
'F': ['C','D']}
print(findshort(graph,'F','C'))
深度优先算法：
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。
广度优先算法：
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
算法实现为：
class Queue(object): # 队列结构
def __init__(self): # 使用list模拟队列
self.items = []
def isEmpty(self):
return len(self.items) == 0
def Enqueue(self, item): # 入队
self.items.append(item)
def Dequeue(self): # 出队
return self.items.pop(0)
def Getlength(self): # 获取队列长度
return len(self.items)
def printQue(self):
for item in self.items:
print(item)
class Graph(object): #定义图结构
def __init__(self):
self.items = {}
self.visited = {}
def add_node(self, node): # 增加单个顶点
if node not in self.items.keys():
self.items[node] = []
def add_nodes(self, nodelist): # 增加顶点集
for node in nodelist:
self.add_node(node)
def add_edge(self, edge): # 增加一条边,无向图
u, v = edge
if (v not in self.items[u]) and (u not in self.items[v]):
self.items[u].append(v)
if (u != v):
self.items[v].append(u)
def Dfs(self, root=None): #深度优先搜索
order = []
def dfs(node):
self.visited[node] = True
order.append(node)
for n in self.items[node]:
if n not in self.visited.keys():
dfs(n)
if root not in self.items.keys():
return None
elif root:
dfs(root)
else:
for node in self.items.keys():
if node not in self.visited.keys():
dfs(node)
print(order)
return order
def Bfs(self,root): #广度优先搜索
order = []
q = Queue()
node=root
self.visited[node] = True
q.Enqueue(node)
while (q.isEmpty() == False):
V = q.Dequeue()
order.append(V)
for n in self.items[V]:
if n not in self.visited.keys():
self.visited[n] = True
q.Enqueue(n)
print(order)
return order
def listfs(self): #图不连通，将所有的顶点遍历一遍
for v in self.items.keys():
if v not in self.items.keys():
self.Dfs(v) #or selif.Bfs(V)
g=Graph() #建立一个图的过程
g.add_nodes([i+1 for i in range(8)])
g.add_edge((1, 2))
g.add_edge((1, 3))
g.add_edge((2, 4))
g.add_edge((2, 5))
g.add_edge((4, 8))
g.add_edge((5, 8))
g.add_edge((3, 6))
g.add_edge((3, 7))
g.add_edge((6, 7))
图的应用
a、最短路径问题
单源最短路径问题，单个顶点到其它全部顶点之间的距离
网络之中，任意两个顶点之间的 最短距离：多源最短路距离
无权图的最短路径：
按照递增或者递减顺序找出最短距离
网友评论