图
# 图的定义
图中的数据元素称之为顶点，顶点之间的逻辑关系用边来表示。
按方向分
- 有向图——边有方向
- A到D的有向边为弧，A为弧尾，D为弧头
<A,D>表示此弧- 如果任意两个顶点之间都存在方向相反的弧，则称为 有向完全图
- 无向图——边无方向
(A,D)或者(D,A)表示此边- 若任意两个顶点之间都存在边，则称为 无向完全图
- 有向图——边有方向
权与网
- 这种与图的边或弧相关的数字，叫做权
- 带权的图称为网
度
- 无向图任一顶点的度是与其相关联的边的数目，总边数为总度数的一半
- 有向图
- 以
v为头的弧称为v的入度——箭头指向v - 以
v为尾的弧称为v的出度——箭头从v指出
- 以
连通
- 若顶点间存在路径，则说明顶点间是连通的 。
- 如果路径最终回到起始点则称为环，顶点不出现重复的路径称为简单路径。
- 若任意两点都是连通的，则图就是连通图，有向则称为强连通图。
- 图中有子图，若子图极大连通，则称为连通分量，有向称为称为强连通分量
- 无向图连通，且n个顶点n-1条边叫做生成树。有向图中一顶点入度为0，其余顶点出度为1，则称为有向树。
- 图1为普通的连通图，图2和图3为图1的生成树，图4不是（不连通）。
# 图的存储结构
# 邻接矩阵
定义
邻接矩阵是一种顺序存储结构。
邻接矩阵存储方式，是用两个数组来表示图。一个一维数组存储图中的顶点信息，一个二维数组存储图中的边或弧的信息。
无向图
- 有边连通记为1，否则为0
- 无向图的连接矩阵为对称阵
- 有向图
- 横着看，行，表示指出（第一行，为v0指向v3），行和为出度
- 竖着看，列，表示指向(第一列，v1指向v0，v2指向v0)，列和为入度
- 网
- 原邻接矩阵为1的地方改为权
- 原邻接矩阵为0的地方,除了对角线保持不变，其他改为无穷大(int——>65536)
代码实现
- 构造无向网图
#实现无向网图 #定义邻接矩阵类 class adjacent_matrix: def __init__(self,peak,side): #初始化 self.peak=peak self.side=side def printPic(self): #输出 print(self.peak) print(self.side) #构建无向网图 def CreatPic(): str=input("请输入顶点(用空格分离)：") peak=str.split(' ')#用空格切片，存放顶点 n=len(peak) num=input("请输入边数") side=np.zeros([n,n]) for i in range(int(num)): str=input("请输入连通顶点，权") power=str.split(' ') x=peak.index(power[0]) y=peak.index(power[1]) side[x][y]=power[2] side[y][x] = power[2] #对称矩阵 pic=adjacent_matrix(peak,side) return pic if __name__=="__main__": pic=CreatPic() #构建无向网图 pic.printPic() #输出
# 邻接表
邻接表中的链表，可以换成别的数据结构
比如，更适合动态数据的动态数据结构 红黑树，跳表，散列表等等
- 区别
邻接矩阵对于边数较少的图来说，有些浪费存储空间，就像顺序存储一样。
链接表是一种数组+单链表的形式。
- 定义
图的顶点用一个一维数组存储，其中每个数据元素还需要存储指向第一个邻接点的指针。
图中每个顶点v的所有邻接点构成一个线性表，无向图称为顶点v的边表，有向图称为顶点v作为弧尾的出边表。
- 无向图
- 有向图
- 顶点v作为弧尾的出边表——邻接表
- 顶点v作为弧头的入边表——逆邻接表
- 网图
- 增加权值信息
- 代码实现
import numpy as np
from 链表.LinkedList_d import *
#定义邻接表
class adjacent_list:
#初始化
def __init__(self,allpeaks):
#allpeaks 为图的所有顶点
self.peaks=allpeaks #一维数组，存放所有顶点
self.node={}#一个字典，键为顶点，值为链表，链表的头为该顶点，其他结点为与其连通的结点
#创建每个顶点的出边表
def creat_outlist(self,peak0,peaks):
link=LinkedList()#初始化一个链表
link.add(peak0)
#传入顶点数组，第一个存放，出边表的主顶点；剩余存放其他顶点
if peaks!=['None']:
for peak in peaks:
link.add(peak)
# 顶点的一个单链表
self.node[peak0] = link # 新增一个键值对
#打印图
def printPic(self):
print(self.peaks)
#print(self.node)
for (k,v) in self.node.items(): #k是键(k是一个字符串)，v是值(v是一个单链表)
print("{}结点的边表为:".format(k))
v.printLinked()#输出链表
#构建图(有向图，无向图)
def CreatPic():
str=input("请输入顶点(用空格分离)：")
allpeaks=str.split(' ')#用空格切片，存放顶点
pic = adjacent_list(allpeaks)#创建邻接表
num=len(allpeaks)
for i in range(int(num)):
str=input("请输入与顶点{}连通(或者其指向)的顶点,若无输入None".format(allpeaks[i]))
peaks=str.split(' ')
pic.creat_outlist(allpeaks[i],peaks)
return pic
if __name__=="__main__":
pic=CreatPic() #构建无向网图
pic.printPic() #输出
# 十字链表
邻接表对于有向图来说，不是很友好，只能关心出度，而逆邻接表也只能关心入度，所以将二者结合，形成十字链表
- 数据结构
firstin为入边表头指针firstout为出边表头指针tailvex值弧起点在顶点表的下标headvex值弧终点在顶点表的下标headlink为入边表指针域，指向终点相同的下条边taillink为出边表指针域，指向起点相同的下条边
十字链表
- 虚线1，指的是边
v1—>v0 - 虚线2，指的是边
v2—>v0 - 虚线3，指的是边
v2—>v1 - 虚线4，指的是边
v1—>v2 - 虚线5，指的是边
v0—>v3
- 虚线1，指的是边
# 邻接多重表?
对于无向图的邻接表，更好的是关注顶点的操作；若要是关注边的操作，则可以使用邻接多重表
邻接表一条边，用两个结点表示；而邻接多重表的一条边，用一个结点表示
- 边表结点结构 *
- 邻接多重表
# 边集数组
边集数组由一个一维数组和一个二维数组组成，一维数组存放顶点，二维数组存放边的信息
# 图的遍历
从图中某一顶点出发仿遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程叫做图的遍历。
# 深度优先遍历
从上到下，先搜一侧的最深处，然后在返回搜索其他地方的最深处，直到遍历结束。
类似于树的中序遍历，是一个递归的过程。
代码
- 邻接矩阵
#深度优先递归算法-邻接矩阵 def DFS_matrix(pic,i): visited1[i]=True #访问过的结点置为 true print(pic.peak[i]) #打印结点 for j in range(length): if(pic.side[i][j]==1 and visited1[j]==False): DFS_matrix(pic,j) #邻接矩阵版深度优先遍历 def traverse_deep_matrix(pic): for i in range(length):#执行递归算法，如果图是连通的，则只执行一次 if not visited1[i]: print(111) DFS_matrix(pic,i)- 邻接表
#深度优先递归算法-邻接表 def DFS_list(pic,i): visited2[i]=True #访问过的结点置为 true peak=pic.peaks[i]#当前下标的结点 link=pic.node[peak]#找到以其作为下标的链表 print(link.head.data) # 打印头结点的数据 #print(2,peak) p=link.head.getNext() #首个结点 算是 边表的开头 #print(2223) #如果链表不空，一直遍历 while(p!=None): #print(333) #print(p.getData()) j = pic.peaks.index(p.getData()) # 获取结点数据在结点表的位置 #print(j) if(visited2[j]==False): #p不为空 或者 该节点没被访问 DFS_list(pic,j)#递归调用 p=p.getNext()#指针后移 #邻接表版深度优先遍历 def traverse_deep_list(pic): for i in range(length1):#执行递归算法，如果图是连通的，则只执行一次 if not visited2[i]: #print(222) DFS_list(pic,i)#传入链表 node是字典类型，键为peak，值为该点对应的边表
# 广度优先遍历
从上到下，从左到右，一层一层的搜索，直到遍历结束。
类似于树的层序遍历。
代码
- 邻接矩阵
# 广度优先递归算法-邻接矩阵 def BFS_matrix(pic): q=Queue() #初始化队列 length=len(pic.peak) vistied=[False]*length #初始化参观矩阵 for i in range(length): #如果是连通图，只循环一次即可 if(not vistied[i]): print(111) #如果没被访问过 vistied[i]=True peak=pic.peak[i] #得到顶点 print(peak) #打印连通图的起点 q.EnQueue(peak)#入队列 q.printQ()#打印队列 while(not q.IsEmpty()): peak=q.DnQueue() i=pic.peak.index(peak) for j in range(length): if (pic.side[i][j]==1 and vistied[j]==False): vistied[j]=True peak=pic.peak[j] print(peak) q.EnQueue(peak) q.printQ() # 打印队列- 邻接表
# 深度优先递归算法-邻接表 def BFS_list(pic): q=Queue() #初始化队列 length=len(pic.peaks) vistied=[False]*length #初始化参观矩阵 for i in range(length): #如果是连通图，只循环一次即可 if(not vistied[i]): print(111) #如果没被访问过 vistied[i]=True peak=pic.peaks[i] #得到顶点 print(peak) #打印连通图的起点 q.EnQueue(peak)#入队列 q.printQ()#打印队列 while(not q.IsEmpty()): peak=q.DnQueue() i=pic.peaks.index(peak) link=pic.node[peak] #得到对应结点的列表 p = link.head.getNext() # 首个结点 算是 边表的开头 # 如果链表不空，一直遍历 while (p != None): peak=p.getData() j=pic.peaks.index(peak) #得到结点对应的下标 if (vistied[j]==False): vistied[j]=True print(peak) q.EnQueue(peak) p=p.getNext() q.printQ() # 打印队列
# 最小生成树
把构造连通网的最小代价生成树称为最小生成树。
n个结点，n-1条边
Prim算法对于稠密图，边多的情况有优势。
Kruskal算法对于稀疏图，边少的情况有优势。（针对于边开展的）
# 普里姆(Prim)算法
设V为所有结点的合集，U为已加入最小生成树边所依附的结点的合集，TE为最小生成树的边的合集。
则在所有u属于U,v属于(V-U)，的边（u,v）中找到一个代价最小的边（u0，v0），加入TE，同时将v0加入U，直到V等于U为止。
def MinTree_prim(pic):
length=len(pic.peak)
peak=pic.peak[0]
U=[peak]#初始化 最小生成树结点--U
V=pic.peak.copy()
V.remove(peak)#剩余结点合集
while(V): #如果V不是空，就一直循环
min=65536
min_list = []#每次循环都重置
for u in U:
#print(u)
#print(pic.peak)
i=pic.peak.index(u)
for j in range(length):
peak=pic.side[i][j]
#print(peak)
if peak>0 and peak<min and (pic.peak[j] in V):
min=peak
min_list = [i, j, pic.side[i][j]]
# min_list=[begin,end,pic.side[i][j],j]
#min_side.append(list)#将所有的边存入
if(min_list):
jnum=min_list[1]
inum=min_list[0]
pic.side[inum][jnum]=0#将找出的最小的边权值设为0
begin=pic.peak[inum]
end=pic.peak[jnum]
print("({},{})-{}".format(begin,end,min_list[2])) #打印最小边
U.append(end)
V.remove(end)
# 克鲁斯卡尔(Kruskal)算法
将边集数组按照 权值排好序，优先选择权值小且不构成回路的边加入最小生成树，直到遍历结束。
#Kruskal算法 生成最小生成树
def MinTree_Kruskal(pic):
length=pic.getNodeNum()#结点个数
parents=[0]*length #初始化数组
for list in pic.elist:
n=Find(parents,list[0])#传入begin
m=Find(parents,list[1])#传入end
if(n!=m): #此边与现有树还没有生成环
parents[n]=m
print("({},{})-{}".format(list[0],list[1],list[-1]))
print(parents)
#查找连线顶点的尾端
def Find(parents,f):
while(parents[f]>0):
f=parents[f]
return f
if __name__=="__main__":
# 初始化边集数组
edges=[[4,7,7],[2,8,8],[0,1,10],[0,5,11],[1,8,12],[3,7,16],[1,6,16],[5,6,17],[1,2,18],[6,7,19],[3,4,20],[3,8,21],[2,3,22],[3,6,24],[4,5,26]]
pic=Edges()
for edge in edges:
#print(edge)
pic.add(edge[0],edge[1],edge[-1])
#print(e.elist)
MinTree_Kruskal(pic)
# 最短路径
对于网图，最短路径是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。
# 迪杰斯特拉(Dijkstra)算法
每次循环都找源点到下一个结点的最短距离，直到终点。
大循环中的两个小循环，第一个小循环找最小的D[j],第二个小循环修正D[j]，并给P[j]赋值
#最短路径问题
def ShortPath_Dijkstra(pic):
length=len(pic.peak)
final=[0]*length
k=length
final[0]=1 #初始化final 置1表示已经访问到，置0表示还没有访问
D=pic.side[0]#初始化 D 表示源点到任意点的距离，默认为0号到其他点的距离
P=[0]*length #初始化路径数组，表示源点到该点的最短路径的前驱结点
#主循环，每次求得v0到某个点的最短路径
for i in range(1,length):
min=65535
#寻找距离v0最近的点-D最小的
for j in range(length):
if final[j]==0 and D[j]<min and D[j]!=0:
k=j
min=D[j]
final[k]=1 #表示第k个结点已经被寻得
#修正当前最短路径及距离-找到最小值所在点k点与其相邻的点j的和 与D[j]做比较
for j in range(length):
if final[j]==0 and (min+pic.side[k][j]<D[j] or D[j]==0) and pic.side[k][j]!=0:
D[j]=min+pic.side[k][j] #修改当前路径长度
P[j]=k #修改访问前驱
return P,D
# 弗洛伊德(Floyd)算法
寻找v到w的最小距离，比较原始距离和经过k点中转的距离，哪个小取哪个
D[v][w]=min{D[v][w],D[v][k]+D[k][w]}
可以取得所有点到其他点的最短路径，O(n^3)
#最短路径问题
def ShortPath_Floyd(pic):
#初始化 P D
length=len(pic.peak)
D=pic.side.copy()
P=[]
for i in range(length):
p = []
for j in range(length):
p.append(j)
if D[i][j]==0 and i!=j:
D[i][j]=65536
P.append(p)
#寻找最小D[v][w]
for k in range(length):#k为中转点
for v in range(length):
for w in range(length):
if(D[v][w]>D[v][k]+D[k][w]):
D[v][w]=D[v][k]+D[k][w] #修正最小路径
P[v][w]=P[v][k] #修正路径前驱结点
return P,D
# 拓扑排序
AOV网
在一个表示工程的有向图中，我们用顶点表示活动，用弧表示活动之间的关系，这样的有向图为顶点表示活动的网，称为AOV网，AOV网中不能存在回路。
拓扑排序
所谓拓扑排序，就是对一个有向图构造拓扑序列的过程。拓扑序列不唯一。
如果网的结点全部被输出，即是一个拓扑序列，即此网不存在回路，是AOV网。
如果有结点没有被输出，则这个网存在回路，不是AOV网。
排序算法
基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删除此结点，并删除以该结点为尾的弧，重复此步骤，直到不存在入度为0的点或者所有结点全部输出为止。
算法关键：
1. 使用邻接表和栈实现
2. 用栈来存储入度为0的结点，在原邻接表的基础上增加一个入度统计表。
def topo(pic): stack=Stack()#创建一个栈，用来存储入度为0的点 length=len(pic.peaks) count=0 #出栈的顶点个数 peaklist=[] # #找入度值，构造入度数组---复杂 #法1-O(n^2) #in_du = [] # for peak in pic.peaks: # num = 0 # 用来统计入度数 # for v in pic.node.values(): # if v.search(int(peak)): # num=num+1 # in_du.append(num-1) #法2-O(n) in_du = [-1]*length for v in pic.node.values(): current=v.head while current: data=current.getData() index=pic.peaks.index(data) in_du[index]=in_du[index]+1 current=current.getNext() #对每个结点进行遍历，将度为0的点入栈 for i in range(length): if in_du[i]==0: stack.push(pic.peaks[i]) #如果栈不空 while(not stack.isEmpty()): peak=stack.pop() peaklist.append(peak) #将入度为0的点存储，最后一起输出 count+=1#个数加一 link=pic.node[peak]#弹出结点的边表 current=link.head.getNext() while(current): data=current.getData() #print(data) index=pic.peaks.index(data) #print(index) in_du[index]-=1 if(in_du[index]==0): stack.push(data) current=current.getNext() print(peaklist) if count<length: return False else: return True
# 关键路径
AOE网
用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网。
与AOV网对比,AOE网侧重工程需要的时间。
- 关键路径
路径上各个活动所持续的时间之和称为路径长度。从源点到终点具有最大长度的路径叫做关键路径，在关键路径上的活动叫做关键活动。
如果要提高效率，则需要改善关键路径上的关键活动。
算法
- etv——正拓扑序列，取大路径
- ltv——反拓扑序列，取小路径
- ete——<vk,vj>--etv[k]--最早不能早过k
- 只有事件k发生了，ete活动才开始
ete=etv[k]
- lte——<vk,vj>--最晚不能晚过j，而且还有留出工作时间
- lte=ltv[j]-len<vk,vj>
- 程序
#求拓扑序列及 etv-各个结点的最早发生时间
def topo_key(pic):
stack=Stack()#创建一个栈，用来存储入度为0的点
stack2=Stack()#这个栈用来存储从上个栈中弹出的结点
length=len(pic.peaks)
count=0 #出栈的顶点个数
peaklist=[]
etv=[0]*length #事件最早发生时间
#法2-O(n)
in_du = [-1]*length
for v in pic.node.values():
current=v.head
while current:
data=current.getData()
peak=data.split(',')[0]#第一个是数据结点
index=pic.peaks.index(peak)
in_du[index]=in_du[index]+1
current=current.getNext()
#对每个结点进行遍历，将度为0的点入栈
for i in range(length):
if in_du[i]==0:
stack.push(i)
#如果栈不空
while(not stack.isEmpty()):
peak_index=stack.pop() #将入度为0的点的下标出栈
peak=pic.peaks[peak_index]#下标对应的结点
stack2.push(peak_index)#将上一个栈出的点入栈
peaklist.append(peak) #将入度为0的点存储，最后一起输出
count+=1#个数加一
link=pic.node[peak]#弹出结点的边表
current=link.head.getNext()
while(current):
data=current.getData()
peak = data.split(',')[0] # 第一个是数据结点
weight=int(data.split(',')[1]) # 第二个是权重
#print(peak)
index=pic.peaks.index(peak)
#print(index)
in_du[index]-=1
if(in_du[index]==0):#如果该结点入度为0，则入栈
stack.push(index)
if(etv[index]<etv[peak_index]+weight):#取大值
etv[index]=etv[peak_index]+weight
current=current.getNext()
print("拓扑序列为： ",peaklist)
print("拓扑序列各顶点对应最早时间为: ",etv)
if count<length:
return False
else:
return etv,stack2
#打印关键路径
def key_path(pic):
#调用拓扑排序，得到输出结果
s=topo_key(pic)
if(s):
etv=s[0]
stank=s[1]
else:
print("拓扑序列错误！")
return False
length=len(etv)
ltv=[etv[length-1]]*length#初始化ltv 全为etv的最后一个值
#出栈，计算ltv
while(not stank.isEmpty()):
peak_index=stank.pop()# 将入度为0的点的下标出栈
peak = pic.peaks[peak_index] # 下标对应的结点
link = pic.node[peak] # 弹出结点的边表
current = link.head.getNext()
while (current): #如果链表不为空
data = current.getData()
peak = data.split(',')[0] # 第一个是数据结点
weight = int(data.split(',')[1]) # 第二个是权重
# print(peak)
index = pic.peaks.index(peak)#栈中弹出结点指向的结点的下标
if (ltv[peak_index] > ltv[index] - weight): # 取小值
ltv[peak_index] = ltv[index] - weight
current = current.getNext()
#计算关键路径
key_list=[] #存放关键路径
for i in range(length): #遍历每个结点
peak=pic.peaks[i]
link=pic.node[peak]
current=link.head.getNext()
while(current):#遍历每个结点指向的边，即结点的边表
data = current.getData()
peak = data.split(',')[0] # 第一个是数据结点
weight = int(data.split(',')[1]) # 第二个是权重
index = pic.peaks.index(peak) # 指向结点的下标
ete=etv[i] #活动最早开始时间不能早过 其弧尾的时间
lte=ltv[index]-weight#活动最晚开始的时间不能晚过其弧头的时间，其中还要预留出活动的时间
if(ete==lte): #如果两者相等，则说明是关键路径
path="<{},{}>-{}".format(pic.peaks[i],peak,weight)
key_list.append(path)
current=current.getNext()
print("关键路径为： ",key_list)
上次更新: 2023 07 3
