《数据结构Python 语言描述》 第7章

第7章图签到扫码下载文旌课堂APP扫码签到（202X.X.XXXX:00至202X.X.XXXX:10）签到方式教师通过“文旌课堂APP”生成签到二维码，并设置签到时间，学生通过“文旌课堂APP”扫描“签到二维码”进行签到。。图本章导读图形结构简称图，是一种比树型结构更复杂的非线性数据结构，它可以用于描述各种复杂的数据对象，在系统工程、计算机科学、数学等多个领域都有着广泛的应用。本章首先介绍图的定义及基本术语，然后介绍图的基本操作、存储结构及遍历方法，最后介绍图的应用，包括最小生成树、最短路径、拓扑排序和关键路径。

第7章图知识目标

第7章 理解图的定义、基本术语和基本操作。 掌握图的两种存储结构，包括邻接矩阵和邻接表。 掌握图的深度优先遍历和广度优先遍历方法。 掌握图的应用，包括最小生成树、最短路径、拓扑排序和关键路径。图技能目标

第7章 能利用图解决实际应用中的最短路径问题。 能利用AOE网预估一个工程的完工时间。图素质目标

第7章 强化学习意识，努力提高应用理论知识解决实际问题的能力。 树立全局意识，学会抓住关键，并利用关键环节掌控全局进展。Content第7章图的存储结构图概述图的遍历最小生成树最短路径拓扑排序关键路径7.1图概述第7章图7.1图概述图（graph）由顶点及描述顶点之间关系的边的有限集合组成，其形式化定义为G=(V,E)。其中，V是图G中顶点的有限集合（顶点集），记为V(G)；E是连接V中两个不同顶点的边的有限集合（边集），记为E(G)。E(G)可以为空集，当E(G)为空集时，图G只有顶点而没有边。对于图G，如果其中的边为无向边，即两个顶点之间的边没有方向，则称图G为无向图；如果其中的边为有向边，即两个顶点之间的边有方向，则称图G为有向图。7.1.1图的定义7.1图概述在无向图中，顶点对通常用圆括号“()”括起来，以表示一条无向边。例如，<v0,v1>表示与顶点v0和顶点v1相关联的一条无向边。由此可见，<v0,v1>和(v1,v0)是同一条边。而在有向图中，顶点对通常用尖括号“<>”括起来，以表示一条有向边。例如，<v0,v1>表示从顶点v0到顶点v1的一条有向边，<v1,v0>表示从顶点v1到顶点v0的一条有向边。由此可见，<v0,v1>和<v1,v0>是两条不同的边。例如，无向图G1顶点集V(G1)={A,B,C,D}，边集E(G1)={(A,B),(A,C),(B,C),(C,D)}；有向图G2顶点集V(G2)={A,B,C,D}，边集E(G2)={<A,B>,<A,C>,<B,C>,<C,D>}。7.1图概述提示在有向图中，<v0,v1>又称为弧，其中v0是弧尾，v1是弧头。7.1图概述7.1.2图的基本术语1．无向完全图和有向完全图对于一个无向图，如果图中任意两个顶点之间都存在一条边，则称该无向图为无向完全图。对于一个有向图，如果图中任意两个顶点之间都存在两条方向相反的边，则称该有向图为有向完全图。例如，下图为无向完全图和有向完全图。7.1图概述2．子图对于两个图G=(V,E)和G‘=(V’,E‘)，如果V’是V的子集，E‘是E的子集，则称图G’是图G的子图。例如，下图为上图无向完全图和有向完全图的子图。7.1图概述3．稀疏图和稠密图有较少条边的图称为稀疏图，反之称为稠密图。4．邻接点对于无向图G=(V,E)，如果边(v0,v1)∈E，则称顶点v0与顶点v1互为邻接点，即顶点v0与顶点v1相邻接；同时称边(v0,v1)依附于顶点v0和顶点v1，或者说边(v0,v1)与顶点v0和顶点v1相关联。对于有向图G=(V,E)，如果边<v0,v1>∈E，则称顶点v0邻接到顶点v1，顶点v1邻接自顶点v0；同时称边<v0,v1>依附于顶点v0和顶点v1，或者说边<v0,v1>与顶点v0和顶点v1相关联。7.1图概述5．顶点的度、入度和出度对于无向图，顶点v的度是指与顶点v相关联的边的数目，记作TD(v)。对于有向图，顶点v的度分为入度和出度。其中，入度是以顶点v为弧头的弧的数目，记作ID(v)；出度是以顶点v为弧尾的弧的数目，记作OD(v)，因此，顶点v的度TD(v)=ID(v)+OD(v)。7.1图概述6．权和网在实际应用中，图的边往往具有一定意义且会被赋予相应的数值，该数值称为该边的权（也称为权值）。这种带权的图称为网。例如，在交通网中用顶点表示城市时，边的权可以表示两个城市之间的距离，如下图所示。7.1图概述7．路径和路径长度8．回路或环若一条路径中的开始顶点和结束顶点相同，则称该路径为回路或环。对于图G=(V,E)，从顶点v出发到达顶点v'的一条路径是一个顶点序列(v,v0,v1,…,vm,v')。其中，若G为无向图，则边(v,v0)、(v0,v1)、…、(vm,v')∈E；若G为有向图，则边<v,v0>、<v0,v1>、…、<vm,v'

>∈E。一条路径中经过的边的数目称为路径长度。7.1图概述9．简单路径、简单回路或简单环顶点序列中顶点不重复出现的路径称为简单路径。除了开始顶点和结束顶点外，其余顶点不重复出现的回路称为简单回路或简单环。10．连通、连通图和连通分量对于无向图G=(V,E)，如果从顶点v0到顶点v1有路径，则称顶点v0和顶点v1是连通的。如果图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为无向图的连通分量。7.1图概述提示在无向图中，若某一个连通子图不包含在其他连通子图内，则称该连通子图为极大连通子图。也就是说，与该连通子图中某顶点连通的所有顶点必包含在该连通子图中。显然，连通图的极大连通子图只有其自身一个，而非连通图的极大连通子图有多个。7.1图概述11．强连通图和强连通分量对于有向图G=(V,E)，如果从顶点v0到顶点v1、从顶点v1到顶点v0都有路径，则称图G为强连通图，否则称为非强连通图。有向图中的极大强连通子图称为有向图的强连通分量。7.1图概述12．连通图的生成树一个连通图的生成树是指该连通图的一个极小连通子图，它含有图中的全部顶点（顶点个数为n），但只有足以构成一棵树的n-1条边。7.1图概述提示极小连通子图既要保证图的流畅，又要使图的边数最少。如果一个无向图有n个顶点和少于n-1条边，则该图是非连通图；如果一个无向图有n个顶点和多于n-1条边，则该图中一定有回路。值得注意的是，有n个顶点和n-1条边的图不一定是生成树。图基本操作的定义如表7-1所示。7.1.3图的基本操作7.1图概述基本操作说明createGraph()构造图locateVex(v)已知图存在，若图中存在顶点v，则返回顶点v在图中的位置；否则返回0getVex(v)已知图存在，v是图中的某个顶点，返回v的值putVex(v,value)已知图存在，v是图中的某个顶点，将value值赋给vfirstAdjVex(v)已知图存在，v是图中的某个顶点，返回v的第一个邻接点；若v无邻接点，则返回NonenextAdjVex(v,w)已知图存在，v是图中的某个顶点，w是v的邻接点，返回v的相对于w的下一个邻接点；若w是v的最后一个邻接点，则返回NoneinsertVex(v)已知图存在，在图中插入一个新顶点vdeleteVex(v)已知图存在，v是图中的某个顶点，删除顶点v及与其相关联的边insertArc(v,w)已知图存在，v和w是图中的两个顶点，在图中增加一条从顶点v到顶点w的边deleteArc(v,w)已知图存在，v和w是图中的两个顶点，删除图中从顶点v到顶点w的边dfsTraverse()已知图存在，对图进行深度优先遍历bfsTraverse()已知图存在，对图进行广度优先遍历表7-1图基本操作的定义7.2图的存储结构第7章图7.2图的存储结构7.2.1邻接矩阵1．邻接矩阵表示法邻接矩阵表示法也称数组表示法，通常采用二维数组存储图中各顶点之间的邻接关系。（1）假设G=(V,E)是具有n个顶点的图，则它的邻接矩阵是一个n×n的方阵，定义如下。7.2图的存储结构例如，邻接矩阵如下图所示。（2）假设G=(V,E)是具有n个顶点的网，则它的邻接矩阵是一个n×n的方阵，定义如下。7.2图的存储结构其中，表示顶点i和顶点j之间边的权值。图的邻接矩阵类的定义如下。classALGraph: #图的邻接矩阵类

GRAPHKIND_UDG='UDG' #无向图7.2图的存储结构GRAPHKIND_DG='DG' #有向图

GRAPHKIND_UDN='UDN' #无向网

GRAPHKIND_DN='DN' #有向网

def__init__(self,kind=None,vNum=0,eNum=0,v=None,e=None):self.kind=kind #图的类别

self.vNum=vNum #图的顶点数

self.eNum=eNum #图的边数

self.v=v #顶点列表

self.e=e #邻接矩阵7.2图的存储结构邻接矩阵表示法的特点如下。（1）图的邻接矩阵是唯一的。（2）根据邻接矩阵很容易判断任意两个顶点之间是否有边，且时间复杂度为O(1)。（3）对于无向图，邻接矩阵第i（0≤i≤n-1）行非零元素（或非∞元素）的个数是顶点vi的度；对于有向图，第i（0≤i≤n-1）行非零元素（或非∞元素）的个数是顶点vi的出度，第i（0≤i≤n-1）列非零元素（或非∞元素）的个数是顶点vi的入度。7.2图的存储结构（4）邻接矩阵中增加和删除顶点的操作不易实现。（5）要统计图中边的总数，需要扫描邻接矩阵中的所有元素，其时间复杂度为O(n2)。（6）如果是有向图，n个顶点需要n2个存储单元存储边；如果是无向图，因其邻接矩阵是一个对称矩阵，因此在顶点数n很大时，可以采用对称矩阵的压缩存储方法，仅存储下三角（或上三角）的元素［需要n(n-1)/2个存储单元］，从而减小存储空间。但无论以什么方式存储，邻接矩阵表示法的空间复杂度均为O(n2)，因此更适合存储稠密图。7.2图的存储结构2．邻接矩阵中基本操作的实现1）返回顶点在图中的位置该算法是根据顶点的值获取其在顶点集中的位置，若顶点不存在，则返回-1。deflocateVex(self,x):foriinrange(self.vNum): #查找顶点信息

ifself.v[i]==x: #如果顶点的值为x，返回其位置

returnireturn-1 #否则返回-1【算法描述】7.2图的存储结构2）创建图下面以创建无向网为例，介绍创建图的方法，其具体步骤如下。（1）输入图的顶点数和边数。（2）依次输入顶点信息并将其存入顶点集中。（3）初始化邻接矩阵，将每条边的权值初始化为极大值（∞）。（4）构造邻接矩阵。依次输入每条边依附的顶点及边的权值，确定两个顶点在图中的位置后，为边赋相应的权值，同时为其对称边也赋相同的权值。importsys #sys模块提供了与python解释器紧密相关的一些变量和函数defcreateUDN(self,vNum,eNum,v,e): #创建无向网

self.vNum=vNum #图的顶点数【算法描述】7.2图的存储结构self.eNum=eNum #图的边数

self.v=[None]*vNum #构造顶点集

foriinrange(vNum): #输入顶点信息

self.v[i]=v[i] self.e=[[sys.maxsize]*vNum]*vNum #初始化邻接矩阵

foriinrange(eNum): #构造邻接矩阵

a,b,w=e[i] #输入每条边依附的顶点及权值

#返回顶点在图中的位置

m,n=self.locateVex(a),self.locateVex(b) #为边(a,b)及边(b,a)赋权值

self.e[m][n]=self.e[n][m]=w若要建立无向图，只需对上述算法进行如下两处修改。（1）初始化邻接矩阵时，将每条边的权值初始化为0。（2）构造邻接矩阵时，将每条边的权值赋值为1。同样，创建有向网或有向图时，也可通过对上述算法进行简单修改实现，感兴趣的读者可自行完成。高手点拨7.2图的存储结构7.2图的存储结构3）输出图该算法是输出图的邻接矩阵。defdisGraph(self):foriinrange(self.vNum): forjinrange(self.vNum):ifself.e[i][j]==sys.maxsize: #如果权值为极大值

print('%4s'%('∞'),end='') #输出∞

else: #输出权值

print('%5d'%(self.e[i][j]),end='')print() #换行【算法描述】7.2图的存储结构7.2.2邻接表1．邻接表表示法邻接表表示法是图的一种链式存储结构。在邻接表中，对图中的每个顶点建立一个单链表，将与该顶点相邻的顶点链接到该单链表中。也就是说，具有n个顶点的图，顶点间的邻接关系可构成n个单链表，其中第i（0≤i≤n-1）个单链表由所有邻接于顶点vi的顶点链接而成。邻接表中每个单链表的第一个结点（表头结点）存放有关顶点的信息，以便于随机访问任一顶点的单链表，其余结点存放有关边的信息。7.2图的存储结构（1）表头结点的结构如下图所示。其中，data域用于存储顶点vi的名称或其他信息，firstarc域用于指向单链表中除表头结点外的第一个结点（即与顶点vi相邻接的第一个顶点）。在邻接表中，假设表头结点为HNode类对象，则表头结点的定义如下。classHNode:def__init__(self,data):self.data=data #顶点的名称或其他信息

self.firstarc=None#指向单链表中除表头结点外的第一个结点7.2图的存储结构（2）边结点的结构如下图所示。无权图的边结点包括两部分。其中，adjvex域用于存储与顶点vi相邻接的顶点在顶点数组中的下标，nextarc域用于指向与顶点vi相邻接的下一个顶点。相较于无权图，有权图的边结点需要额外增加一个info域存储边相关的信息，如权值。假设边结点为ArcNode类对象，则边结点的定义如下。classArcNode:def__init__(self,adjVex,info):self.adjVex=adjVex #顶点的邻接点在顶点数组中的下标

=info #边的权值

self.nextarc=None #与顶点相邻接的下一个顶点7.2图的存储结构为此，可以对每个顶点vi建立一个逆邻接表，即对每个顶点vi建立一个以顶点vi为弧头的单链表。这样，在逆邻接表中第i（0≤i≤n-1）个单链表中边结点的个数就是顶点vi的入度。对于无向图，邻接表中第i（0≤i≤n-1）个单链表中边结点的个数是顶点vi的度。对于有向图，邻接表中第i（0≤i≤n-1）个单链表中边结点的个数是顶点vi的出度，但要求顶点vi的入度必须遍历整个邻接表。7.2图的存储结构邻接表表示法的特点如下。（1）图的邻接表是不唯一的。（2）在邻接表中，无法很快判断任意两个顶点之间是否有边，且最坏时间复杂度为O(n)。（3）邻接表中增加和删除顶点的操作很容易实现。（4）要统计图中边的总数，按单链表顺序扫描所有边即可，其时间复杂度为O(n+e)。（5）对n个顶点e条边的图，若该图为无向图，则在其邻接表表示中有n个表头结点和2e个边结点；若该图为有向图，则在其邻接表表示中有n个表头结点和e个边结点。因此，邻接表表示法的空间复杂度为O(n+e)，更适合存储稀疏图。7.2图的存储结构2．邻接表中基本操作的实现1）返回顶点在图中的位置该算法是根据顶点的值获取其在顶点集中的位置，若顶点不存在，则返回-1。deflocateVex(self,x):foriinrange(self.vNum): #查找顶点信息

ifself.v[i].data==x: #如果顶点的值为x，返回其位置

returnireturn-1 #否则返回-1【算法描述】7.2图的存储结构2）创建图下面以创建无向图为例，介绍创建图的方法，其具体步骤如下。（1）构造表头结点，初始化表头结点的指针域为None。（2）创建邻接表。依次输入每条边依附的两个顶点，并确认顶点在图中的位置，然后插入边结点。defcreateUDG(self): #创建无向图

v=self.vself.v=[None]*self.vNum #构造表头结点

foriinrange(self.vNum):self.v[i]=HNode(v[i]) #生成一个新的结点表7.2图的存储结构foriinrange(self.eNum):a,b=self.e[i] #输入每条边依附的两个顶点

#返回顶点在图中的位置

u,v=self.locateVex(a),self.locateVex(b)self.addArc(u,v,1) #插入边结点

self.addArc(v,u,1) #插入另一个对称的边结点若要创建有向图，只需对上述算法进行简单修改，即仅需生成一个边结点，并将其插入表头结点后面。高手点拨7.2图的存储结构3）插入边结点该算法是指在单链表中插入一个顶点i指向顶点j的权值为e的边结点。采用头插法插入边结点的算法如下。defaddArc(self,i,j,e):arc=ArcNode(j,e) #生成新结点

'''头插法插入边结点'''arc.nextarc=self.v[i].firstarc self.v[i].firstarc=arc7.3图的遍历第7章图7.3图的遍历7.3.1深度优先遍历图的深度优先遍历类似于树的先根遍历，其步骤如下。（1）从图中某个顶点v出发，访问该顶点。（2）找出刚访问过的顶点的第一个未被访问的邻接点，访问该邻接点。以该邻接点为新顶点，重复步骤（2），直到刚访问过的顶点没有未被访问的邻接点。（3）退回到上一个访问过且还有未被访问的邻接点的顶点，继续访问该顶点的下一个未被访问的邻接点。（4）重复步骤（2）和步骤（3），直到图中所有顶点均被访问。提示上述深度优先遍历步骤是针对连通图的。若是非连通图，执行上述遍历步骤后，图中一定还有未访问过的顶点，此时，需要从图中选择一个未访问过的顶点作为起始点，重复上述深度优先遍历步骤，直到图中所有顶点均被访问。7.3图的遍历defdfsTraverse(g): globalvisited #定义全局变量

visited=[False]*g.getVNum() #创建访问标记数组，并赋初值False'''以每个顶点作为开始顶点进行深度优先遍历'''foriinrange(g.getVNum()): ifnotvisited[i]: #如果顶点未被访问

dFS(g,i) #访问顶点并进行遍历

defdFS(g,i):

visited[i]=True #对访问过的顶点进行标记

print(g.getVex(i),end='') #打印访问过的顶点【算法描述】7.3图的遍历v=g.firstAdj(i) #访问顶点的第一个邻接点

whilev!=-1: ifnotvisited[v]: #如果该邻接点没有被访问

dFS(g,v) #重复执行深度优先遍历算法

v=g.nextAdj(i,v) #否则访问顶点的下一个邻接点提示为了在遍历过程中区分顶点是否已经被访问，可设置一个访问标志数组visited且为其赋初值False，当顶点被访问过后，将其赋值为True。如果给定的图是无向连通图或有向强连通图，则遍历一次就能访问图中所有顶点，从而得到图的深度优先遍历序列。7.3图的遍历下面具体分析深度优先遍历无向图的过程。（1）从顶点A出发，首先访问顶点A。顶点A的邻接点有顶点B和顶点F，选择未被访问过的邻接点B，从顶点B继续遍历。（2）访问顶点B。顶点B的邻接点有顶点A、顶点C、顶点D和顶点G，选择未被访问过的邻接点C，从顶点C继续遍历。（3）访问顶点C。由于顶点C的邻接点只有已被访问过的顶点B，故退回到顶点B，从顶点B的另一个未被访问过的邻接点D继续遍历。（4）访问顶点D。顶点D的邻接点有顶点B、顶点G和顶点E，选择未被访问过的邻接点E，从顶点E继续遍历。（5）访问顶点E。由于顶点E的邻接点只有已被访问过的顶点D，故退回到顶点D，从顶点D的另一个未被访问过的邻接点G继续遍历。（6）访问顶点G。顶点G的邻接点有顶点B、顶点D和顶点F，选择未被访问过的邻接点F，从顶点F继续遍历。（7）访问顶点F。由于顶点F的邻接点A和G均已被访问过，故该无向图遍历结束，得到的深度优先遍历序列为A、B、C、D、E、G、F。7.3图的遍历提示当进行深度优先遍历时，如果一个顶点有多个邻接点，可以任选其一，故图的深度优先遍历序列不是唯一的。也就是说，对于如图7-18所示的无向图，其深度优先遍历序列也可以为A、B、C、D、G、F、E。7.3图的遍历7.3.2广度优先遍历图的广度优先遍历类似于二叉树的层次遍历，其步骤如下。（1）从图中的某个顶点v出发，访问该顶点。（2）依次访问顶点v的所有未被访问过的邻接点。（3）分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。（4）重复步骤（3），直到图中所有顶点均被访问。defbfsTraverse(g):globalvisited #定义全局变量

visited=[False]*g.getVNum()#创建访问标记数组，并赋初值Fasle'''以每个顶点作为开始顶点进行广度优先遍历'''【算法描述】7.3图的遍历foriinrange(g.getVNum()):ifnotvisited[i]: #如果顶点未被访问

bFS(g,i) #访问顶点并进行遍历defbFS(g,i):q=LinkQueue() #创建辅助队列

q.inQueue(i) #将开始顶点插入队尾

whilenotq.queueEmpty(): #如果队列不为空

u=q.deQueue() #删除队头元素

visited[u]=True #对访问过的顶点进行标记

print(g.getVex(u),end='') #打印访问过的顶点

v=g.firstAdj(u) #访问顶点的第一个邻接点7.3图的遍历

whilev!=-1:ifnotvisited[v]: #如果该邻接点没有被访问

q.inQueue(v) #将顶点插入队尾

v=g.nextAdj(u,v) #否则访问顶点的下一个邻接点提示上述广度优先遍历步骤是针对连通图的。若是非连通图，执行上述遍历步骤后，图中一定还有未访问过的顶点，此时，需要从图中选择一个未访问过的顶点作为起始点，重复上述广度优先遍历步骤，直到图中所有顶点均被访问。在广度优先遍历中，先被访问的顶点的邻接点也先被访问，因此，在算法中需记录顶点的访问顺序，以便后续按此顺序访问各顶点的邻接点。为此，可以利用一个队列来记录顶点的访问顺序，即将访问的每个顶点进队后再依次出队，利用队列“先进先出”的特点按顺序访问它们的邻接点。高手点拨7.3图的遍历7.3图的遍历下面具体分析广度优先遍历无向图的过程。（1）从顶点A出发，首先访问顶点A。顶点A的邻接点有顶点B和顶点F。（2）访问顶点B和顶点F。（3）按照顶点A访问其邻接点的顺序，首先访问顶点B未被访问过的邻接点C、D、G，然后访问顶点F未被访问过的邻接点（无符合条件的邻接点）。（4）按照顶点B访问其邻接点的顺序，首先访问顶点C未被访问过的邻接点（无符合条件的邻接点），然后访问顶点D未被访问过的邻接点E，最后访问顶点G未被访问过的邻接点（无符合条件的邻接点）。（5）至此，该无向图遍历结束，得到的广度优先遍历序列为A、B、F、C、D、G、E。7.3图的遍历在对无向连通图进行遍历时，由深度优先遍历得到的生成树称为深度优先生成树，由广度优先遍历得到的生成树称为广度优先生成树。无论是哪种生成树，都是由相应遍历中经过的边构成的。例如，无向图的深度优先生成树和广度优先生成树如下图所示。需要注意的是，由于图的深度优先遍历序列和广度优先遍历序列不是唯一的，故其对应的深度优先生成树和广度优先生成树也不是唯一的。7.4最小生成树第7章图7.4最小生成树在一个无向连通网的所有生成树中，各条边权值之和最小的生成树称为该无向连通网的最小生成树。构造最小生成树时，需要遵循如下3条原则。常用的构造最小生成树的算法有Prim算法和Kruskal算法。（1）尽可能选取权值最小的边，但不能构成回路。（2）最小生成树应具有n个顶点和n-1条边。（3）最小生成树一定是连通的。7.4最小生成树7.4.1Prim算法假设N=(V,E)是一个无向连通网，其中V为顶点集，E为边集。另设置两个集合U和TE，令U为最小生成树的顶点集，TE为最小生成树的边集，则使用Prim算法求最小生成树T的步骤如下。（1）令U的初始值为U={u0}（u0∈V），TE的初始值为TE={}。（2）在所有u∈U，v∈V-U的边(u,v)∈E中选择一条权值最小的边(u0,v0)，并将其加入TE中，同时将顶点v0加入U中。（3）重复步骤（2），直到U=V。此时，TE中必含有n-1条边，T=(U,TE)即为N的最小生成树。7.4最小生成树classCloseEdge:def__init__(self,adjVex,lowCost):self.adjVex=adjVex #U中的顶点值

self.lowCost=lowCost #到U中各顶点边的权值的最小值

classMiniSpanTree:

'''从值为u的顶点出发构造最小生成树，返回由最小生成树的边组成的二维数组'''defprim(g,u): #存放最小生成树边的顶点

tree=[[None,None]foriinrange(g.getVNum()-1)]count=0【算法描述】7.4最小生成树#构造辅助数组closEdge，用于存储从U到V-U具有最小权值的边，初值为NonecloseEdge=[None]*g.getVNum() k=g.locateVex(u) #记录初始顶点的位置

forjinrange(g.getVNum()): ifk!=j: #如果不是初始顶点

#将边加入最小生成树的边集TE中

closeEdge[j]=CloseEdge(u,g.getArcs(k,j)) #将顶点加入最小生成树的顶点集U中

closeEdge[k]=CloseEdge(u,0) foriinrange(1,g.getVNum()): #找出具有到U中最短距离的顶点的序号7.4最小生成树k=MiniSpanTree.getMinMum(closeEdge)tree[count][0]=closeEdge[k].adjVex #U中的顶点

tree[count][1]=g.getVex(k) #V-U中的顶点

count+=1 #更新辅助数组closeEdgecloseEdge[k].lowCost=0 forjinrange(g.getVNum()):

#判断权值的大小，将权值最小的边加入最小生成树

ifg.getArcs(k,j)<closeEdge[j].lowCost:closeEdge[j]=CloseEdge(g.getVex(k),g.getArcs(k,j))returntree7.4最小生成树 '''选出lowCost最小的顶点'''defgetMinMum(closeEdge):minvalue=sys.maxsizev=-1foriinrange(len(closeEdge)):ifcloseEdge[i].lowCost!=0andcloseEdge[i].lowCost<minvalue:minvalue=closeEdge[i].lowCostv=ireturnv7.4最小生成树7.4.2Kruskal算法假设N=(V,E)是一个无向连通网，其中V为顶点集，E为边集，则使用Kruskal算法求最小生成树T的步骤如下。（1）令N的最小生成树T的初始状态为T=(V,{})，即T由V中的n个顶点构成，顶点之间不存在边。（2）在E中选择权值最小的边(u,v)，若该条边未使最小生成树T形成回路，则将其加入T中，否则舍去该条边。（3）重复步骤（2），直到T中所有顶点构成一个连通分量（或者包含n-1条边）。Kruskal算法的关键是判断选择一条权值最小的边后最小生成树是否会形成回路，这可以通过判断该条边的两个顶点所在的连通分量是否相同来解决。7.4最小生成树defKruskal(g):

vset=[-1]*100#构造辅助数组vset，用于存储顶点所属的连通分量的编号

E=[] #建立存放所有边的数组E

foriinrange(g.n):

forjinrange(i+1,g.n): #无向图的上三角部分的边【算法描述】判断规则为，每个连通分量用其中一个顶点的编号来标识（称为连通分量编号），同一个连通分量中所有顶点的连通分量编号相同，不同连通分量中两个顶点的连通分量编号不相同。如果选择的边的两个顶点的连通分量编号相同，则一定会形成回路，此时，须舍弃该条边。7.4最小生成树ifg.e[i][j]!=0andg.e[i][j]!=sys.maxsize:E.append([i,j,g.e[i][j]]) #添加[i,j,w]元素

E.sort(key=itemgetter(2)) #按权值递增排序所有边

foriinrange(g.n):vset[i]=i #初始化数组vsetcnt=1 #初值为最小生成树的第1条边

j=0 #E中边的下标

whilecnt<g.n: #生成的边数小于nu1,v1=E[j][0],E[j][1] #边的起点和终点

#两个顶点所属连通分量的编号7.4最小生成树sn1=vset[u1]sn2=vset[v1]ifsn1!=sn2:#两个顶点属于不同连通分量时，加入不会构成回路

print('(%d,%d):%d'%(u1,v1,E[j][2]),end='')#加入该条边

cnt+=1 #最小生成树的边数加1

'''将加入最小生成树的边的两个顶点所属的连通分量编号改为一致'''foriinrange(g.n):ifvset[i]==sn2:vset[i]=sn1j+=1 #否则继续取下一条权值最小的边7.5最短路径第7章图7.5最短路径7.5.1Dijkstra算法Dijkstra算法可解决有向网中从源点v0到其他顶点的最短路径问题。假设G=(V,E)是一个有向网，其中，V为顶点集，E为边集。如果用S表示已求得最短路径的顶点集，用U表示尚未求得最短路径的顶点集，则使用Dijkstra算法求最短路径的步骤如下。（1）初始时，S中只有源点v0，U中是除源点v0之外的其他顶点。（2）从U中找出源点v0到U中最短路径长度最小的顶点u，并将其加入S中。（3）以顶点u为中间点，此时从源点v0到某个顶点（假设为顶点v1）的最短路径有两条，一条经过顶点u；另一条不经过顶点u。（4）重复步骤（2）和步骤（3），直到所有顶点均加入S中。7.5最短路径classShortestPath:defdjikstra(g,v0):#存储最短路径，p[v][k]表示从v0到v的最短路径中经过的第k个顶点

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存储当前所找到的从源点到终点的最短路径长度

D=[sys.maxsize]*g.getVNum()#设置finish标志，初值为False。若已找到最短路径，则修改为Truefinish=[False]*g.getVNum()v0=g.locateVex(v0) #顶点的位置【算法描述】7.5最短路径forvinrange(g.getVNum()):D[v]=g.getArcs(v0,v) #获取权值

ifD[v]<sys.maxsize: #若两个顶点之间存在边

p[v][0]=v0p[v][1]=vp[v0][0]=v0 #v0本身可以直接到达v0D[v0]=0finish[v0]=True #更新finish的值

v=-1 #若两个顶点之间不存在边，初值为-1foriinrange(1,g.getVNum()):minvalue=sys.maxsize7.5最短路径forwinrange(g.getVNum()):'''找出所有最短路径中的最小值'''ifnotfinish[w]:ifD[w]<minvalue:v=wminvalue=D[w]finish[v]=True #更新finish的值

forwinrange(g.getVNum()):

'''如果经过顶点v后的路径小于不经过顶点v的路径，则经过顶点v的路径的权值之和为最短路径长度'''7.5最短路径ifnotfinish[w]andg.getArcs(v,w)<sys.maxsizeand(minvalue+g.getArcs(v,w)<D[w]): D[w]=minvalue+g.getArcs(v,w) '''更新最短路径信息'''forkinrange(g.getVNum()):p[w][k]=p[v][k]ifp[w][k]==-1:p[w][k]=wbreakdis={g.getVex(i):D[i]foriinrange(g.getVNum())}returndis,p #返回源点到其他顶点的最短路径长度与路径矩阵7.5最短路径

'''输出源点到其他顶点的最短路径'''defprintDjikstraPath(g,v0,p):u=v0v0=g.locateVex(v0) #返回源点v0的位置

foriinrange(g.getVNum()):v=g.getVex(i) #返回顶点的值

print('%s->%s的最短路径为:'%(u,v),end='') '''输出最短路径中经过的各顶点'''ifp[i][0]!=-1:print(g.getVex(p[v0][0]),end='')7.5最短路径forkinrange(1,g.getVNum()):ifp[i][k]==-1:breakprint('->%s'%g.getVex(p[i][k]),end='')print()7.5.2Floyd算法Floyd算法可解决有向网中任意两个顶点之间的最短路径问题。Floyd算法可以使用n阶方阵来描述，其中D-1[i][j]表示从顶点i出发不经过其他顶点直接到达顶点j的路径长度，D(k)[i][j]表示从顶点i到顶点j的中间可能经过顶点0、1、…、k，但不经过顶点k+1、k+2、…、n-1的最短路径长度。7.5最短路径所以，Floyd算法的求解过程是按照图中顶点的顺序依次计算D(k)（0≤k≤n-1），最终得到的D(n-1)[i][j]就是从顶点i到顶点j的最短路径长度。classShortestPath:deffloyd(g):vNum=g.getVNum() #返回顶点数

#存储最短路径长度

D=[[sys.maxsize]*vNumforiinrange(vNum)] #存储最短路径

p=[[-1]*vNumforiinrange(vNum)]foruinrange(vNum):forvinrange(vNum):7.5最短路径

#如果u不等于v，D[u][v]等于边<u,v>的权值，否则为0D[u][v]=g.getArcs(u,v)ifu!=velse0ifu!=vandD[u][v]<sys.maxsize:p[u][v]=u #顶点v的前驱为uforkinrange(vNum):foriinrange(vNum):forjinrange(vNum)'''若利用中转点后路径变短，则修改最短路径及其长度'''ifD[i][j]>D[i][k]+D[k][j]:D[i][j]=D[i][k]+D[k][j]p[i][j]=p[k][j]7.5最短路径dis={(g.getVex(u),g.getVex(v)):D[u][v]foruinrange(vNum)forvinrange(vNum)}returndis,p #返回两个顶点之间的最短路径长度与路径矩阵

'''输出任意两个顶点之间的最短路径'''defprintFloydPath(g,p):vNum=g.getVNum() #获取顶点数

foruinrange(vNum):forvinrange(vNum):ifu==v: #同一个顶点的最短路径为本身print('%s->%s的最短路径为:%s'%(g.getVex(u),g.getVex(v),g.getVex(u)))7.5最短路径continue '''两个不同顶点之间的最短路径'''flag=True path=[v]t=p[u][path[0]]whilet!=u:ift==-1:flag=False

break7.5最短路径path=[t]+patht=p[u][t]

print('%s->%s的最短路径为:'%(g.getVex(u),g.getVex(v)),end='')ifflag:print(g.getVex(u),end='')fornodeinpath:print('->%s'%g.getVex(node),end='')print()同步训练求城市之间交通费用最少的路线【问题描述】已知下图为一个城市交通网，其中各顶点表示城市，边的权值表示从一个城市到另一个城市的交通费用。现有一位旅客要从城市A到其他城市，设计算法找出一条路线，使得这位旅客从城市A到其他城市所花费的交通费用最少。同步训练求城市之间交通费用最少的路线【问题分析】该问题反映在图上就是要找从顶点A到其他顶点的最短路径，因此可以使用Dijkstra算法求解该问题，并用从顶点A到其他顶点的最短路径及最短路径长度表示从城市A到其他城市在交通费用最少情况下的路线及花销。【代码实现】importsysclassHNode: #表头结点类

def__init__(self,data=None):self.data=data #顶点的名称或其他信息

self.firstarc=None #指向单链表中除表头结点外的第一个结点classArcNode: #边结点类同步训练求城市之间交通费用最少的路线def__init__(self,adjVex,weight):self.adjVex=adjVex #顶点的邻接点在顶点数组中的下标

self.weight=weight #边的权值

self.nextarc=None #与顶点相邻接的下一个顶点classALGraph: #图的邻接表类

GRAPHKIND_UDG='UDG'GRAPHKIND_DG='DG'GRAPHKIND_UDN='UDN'GRAPHKIND_DN='DN'def__init__(self,kind=None,vNum=0,eNum=0,v=None,e=None):同步训练求城市之间交通费用最少的路线self.kind=kindself.vNum=vNumself.eNum=eNumself.v=vself.e=edefcreateDN(self): #创建有向网

v=self.vself.v=[None]*self.vNumforiinrange(self.vNum):self.v[i]=HNode(v[i])同步训练求城市之间交通费用最少的路线foriinrange(self.eNum):a,b,w=self.e[i]u,v=self.locateVex(a),self.locateVex(b)self.addArc(u,v,w)defaddArc(self,i,j,weight): #插入边结点

arc=ArcNode(j,weight)arc.nextarc=self.v[i].firstarcself.v[i].firstarc=arcdefgetVNum(self): #返回顶点数

returnself.vNum同步训练求城市之间交通费用最少的路线defgetVex(self,i): #返回顶点的值

ifi<0ori>=self.vNum:raiseException('第%s个结点不存在'%i)returnself.v[i].datadeflocateVex(self,x): #返回值为x的顶点的位置

foriinrange(self.vNum):ifself.v[i].data==x:returnireturn-1defgetArcs(self,u,v): #返回顶点u到顶点v的权值同步训练求城市之间交通费用最少的路线ifu<0oru>=self.vNum:raiseException('第%s个结点不存在'%u)ifv<0orv>=self.vNum:raiseException('第%s个结点不存在'%v)p=self.v[u].firstarcwhilepisnotNone:ifp.adjVex==v:returnp.weightp=p.nextarcreturnsys.maxsize同步训练求城市之间交通费用最少的路线classShortestPath:defdjikstra(g,v0):

#存储最短路径，p[v][k]表示从v0到v的最短路径中经过的第k个顶点

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存储当前所找到的从源点到终点的最短路径长度

D=[sys.maxsize]*g.getVNum()

#设置finish标志，初值为False。若已找到最短路径，则修改为Truefinish=[False]*g.getVNum()v0=g.locateVex(v0) #顶点的位置

forvinrange(g.getVNum()):同步训练求城市之间交通费用最少的路线D[v]=g.getArcs(v0,v) #获取权值

ifD[v]<sys.maxsize: #若两个顶点之间存在边

p[v][0]=v0p[v][1]=vp[v0][0]=v0 #v0本身可以直接到达v0D[v0]=0finish[v0]=True #更新finish的值

v=-1 #若两个顶点之间不存在边，初值为-1foriinrange(1,g.getVNum()):minvalue=sys.maxsize同步训练求城市之间交通费用最少的路线forwinrange(g.getVNum()):'''找出所有最短路径中的最小值'''ifnotfinish[w]:ifD[w]<minvalue:v=wminvalue=D[w]finish[v]=True #更新finish的值

forwinrange(g.getVNum()):

'''如果经过顶点v后的路径小于不经过顶点v的路径，则经过顶点v的路径的权值之和为最短路径长度'''同步训练求城市之间交通费用最少的路线ifnotfinish[w]andg.getArcs(v,w)<sys.maxsizeand(minvalue+g.getArcs(v,w)<D[w]):D[w]=minvalue+g.getArcs(v,w)'''更新最短路径信息'''forkinrange(g.getVNum()):p[w][k]=p[v][k]ifp[w][k]==-1:p[w][k]=wbreakdis={g.getVex(i):D[i]foriinrange(1,g.getVNum())}returndis,p #返回源点到其他顶点的最短路径长度与路径矩阵同步训练求城市之间交通费用最少的路线'''输出源点到其他顶点的最短路径'''defprintDjikstraPath(g,v0,p):u=v0v0=g.locateVex(v0) #返回源点的位置

foriinrange(1,g.getVNum()):v=g.getVex(i) #返回顶点的值

print('城市%s->城市%s:'%(u,v),end='')'''输出最短路径中经过的各顶点'''ifp[i][0]!=-1:print(g.getVex(p[v0][0]),end='')同步训练求城市之间交通费用最少的路线forkinrange(1,g.getVNum()):ifp[i][k]==-1:breakprint('->%s'%g.getVex(p[i][k]),end='')print()v=['A','B','C','D','E','F'] #顶点集e=[('A','B',500),('A','C',300),('A','D',380),('A','E',380),('B','D',100),('C','E',50),('D','B',100),('D','F',170),('E','C',50),('E','F',100),('F','D',170)] #边集g=ALGraph(ALGraph.GRAPHKIND_DN,