数据结构——图

1、第七章第七章 图图多对多的关系多对多的关系学习要点：学习要点：v图的基本概念与相关有向图、无向图、网和连通图概念。图的基本概念与相关有向图、无向图、网和连通图概念。v图的邻接矩阵与邻接表存储结构及其特性。图的邻接矩阵与邻接表存储结构及其特性。v图的深度优先和广度优先遍历方法及其在邻接表存储结构中的图的深度优先和广度优先遍历方法及其在邻接表存储结构中的实现算法。实现算法。v图与树的联系与区别，图的生成树与最小生成树。图与树的联系与区别，图的生成树与最小生成树。v图的最短路径。图的最短路径。v图的应用：最短路径、拓扑排序与关键路径。图的应用：最短路径、拓扑排序与关键路径。27.1 基本概念与相关描

2、述基本概念与相关描述7.1.1 图的基本概念图的基本概念v“图图”（Graph）也称为网状结构，它由一个非空的也称为网状结构，它由一个非空的顶点（顶点（vertex）集合）集合V和一个描述顶点之间邻接关系的和一个描述顶点之间邻接关系的边（边（edge）集合集合E组成，而组成，而E中每条边连接的两个顶点都属于集合中每条边连接的两个顶点都属于集合V。一。一个图个图G可以记为：可以记为：G =（V，E）。v多对多的关系，非线性结构多对多的关系，非线性结构vV(G)：顶点的非空有限集合：顶点的非空有限集合vE(G)：图中边的有限集合：图中边的有限集合37.1.1 图的基本概念图的基本概念2v有向图：弧

3、（有向边），有向图：弧（有向边），v :xy,x邻接到邻接到y，y邻接自邻接自xv 与与x、y相关联相关联v 4v无向图：边（无向边），无向图：边（无向边），v (x,y):xy,x与与y相邻接相邻接v (x,y) 与与x、y相关联相关联v (x,y) = (y,x)7.1.1 图的基本概念图的基本概念3子图子图：V(B)V(B)属于属于V(A)V(A)，且，且E(B)E(B)属于属于E(A)E(A)，则则B B是是A A的子图。的子图。 （B B是是A A中的一部分）中的一部分）57.1.2 图的相关概念图的相关概念1.顶点邻接与顶点的度顶点邻接与顶点的度 顶点的度顶点的度 相邻接顶点的个数

4、，相邻接顶点的个数，顶点顶点vi的度记的度记为为D(vi)。 有向图顶点的度有向图顶点的度 v出度出度：以顶点以顶点vi为弧尾的弧的个数，记为为弧尾的弧的个数，记为OD(vi)；v入度入度：以顶点以顶点vi为弧头的弧的个数，记为为弧头的弧的个数，记为ID(vi)。D(vi)=ID(vi)+OD(vi) 边数与顶点度关系边数与顶点度关系 在图的顶点数在图的顶点数n、边数、边数e以及各顶点的度以及各顶点的度D(vi)（1in）三者之间存在如下关系：）三者之间存在如下关系：62e= D(vi)ni 17.1.2 图的相关概念图的相关概念21.路径与路径长度路径与路径长度7 无向图的路径无向图的路径

5、在顶点在顶点vi与顶点与顶点vj之间存在一个边的序列：（之间存在一个边的序列：（vi, vi1），），（vi1, vi2），），（，（vim, vj）。）。 有向图的路径有向图的路径 顶点顶点vi与顶点与顶点vj之间存在一个弧的序列：之间存在一个弧的序列：， 。 路径长度路径长度 由顶点由顶点vi到顶点到顶点vj路径上拥有的边的个数。路径上拥有的边的个数。 简单路径与回路简单路径与回路 若在一条路径上出现的顶点都不同，则称其为若在一条路径上出现的顶点都不同，则称其为“简单路径简单路径”或或“简单回路简单回路（环环cycle）”。7.1.2 图的相关概念图的相关概念33.无向完全图与有向完全图无

6、向完全图与有向完全图v有向完全图有向完全图：每个顶点都与其它任意顶点有弧。：每个顶点都与其它任意顶点有弧。v 共共 条边。条边。n*(n-1)n*(n-1)/28v无向完全图无向完全图：每个顶点都与其它任意顶点有边。：每个顶点都与其它任意顶点有边。v 共共 条边。条边。7.1.2 图的相关概念图的相关概念44.连通图与连通分量连通图与连通分量 连通分量连通分量 在无向图在无向图G中，尽可能多地从集合中，尽可能多地从集合V及及E里收集顶点里收集顶点和边，使它们成为该图的一个和边，使它们成为该图的一个极大的连通子图极大的连通子图，这个子图就被，这个子图就被称为是无向图称为是无向图G的一个的一个“连

7、通分量连通分量”。9 连通图连通图 在无向图在无向图G中，任意一对顶点之间都是连通的。中，任意一对顶点之间都是连通的。7.1.2 图的相关概念图的相关概念44.连通图与连通分量连通图与连通分量210 强连通图和弱连通图强连通图和弱连通图 在有向图在有向图G中，若对其中任意两个顶点中，若对其中任意两个顶点vi和和vj互有互有路径路径可达可达，则称，则称G强连通图；如果任意两个顶点都至少存在强连通图；如果任意两个顶点都至少存在单向路径，则称单向路径，则称G是弱连通图。是弱连通图。n个顶点的强连通图应当个顶点的强连通图应当至少有至少有n条弧条弧。 强连通分量和弱连通分量强连通分量和弱连通分量 有向图

8、有向图G中的极大强连通子图称为中的极大强连通子图称为G的的强连通分量，而其中的极大弱连通子图称为强连通分量，而其中的极大弱连通子图称为G的弱连通分量。的弱连通分量。7.1.2 图的相关概念图的相关概念55.边的权值与网络边的权值与网络11 边的权值边的权值 图的边或弧依附上图的边或弧依附上的的某种数值称为某种数值称为“权值权值”或或“权（权（weight）”。例如地图上连接两个城市的铁路线在其例如地图上连接两个城市的铁路线在其上附有该铁路线的里程数等。上附有该铁路线的里程数等。 网络网络 边或弧上带有权的图称为边或弧上带有权的图称为“网络网络”或或“网图网图”。7.2 图的存储图的存储7.2.

9、1基于邻接矩阵存储基于邻接矩阵存储v用二维数组表示顶点的邻接关系用二维数组表示顶点的邻接关系 1、图的邻接矩阵（、图的邻接矩阵（n顶点用顶点用n阶方阵）阶方阵）12A = 0011010010101100111000010110001011001、图的邻接矩阵、图的邻接矩阵2邻接矩阵特点：邻接矩阵特点： 无向图邻接矩阵无向图邻接矩阵对称对称，有向图不对称，有向图不对称 无向图第无向图第i行行(列列)非零元素个数非零元素个数即为结点即为结点i的的度度 有向图第有向图第i行行(列列)非零元素个数即为结点非零元素个数即为结点i的出的出(入入)度度 容易确认任两点之间是否有边，但扫描边数代价大容易确认

10、任两点之间是否有边，但扫描边数代价大 （对每个结点进行检测）（对每个结点进行检测）132、网络的邻接矩阵、网络的邻接矩阵143、邻接矩阵存储算法、邻接矩阵存储算法算法算法7-1 有向图有向图G邻接矩阵算法。邻接矩阵算法。设置一个一维数组设置一个一维数组Gv，用于存放，用于存放G的顶点数据信息；设置一个二维数组的顶点数据信息；设置一个二维数组Ge，用于存放，用于存放G中有关弧的信息；设置变量中有关弧的信息；设置变量n和和e，记录图的顶点个，记录图的顶点个数和弧的个数信息。数和弧的个数信息。1500 Create_Gm(MGraph *Gm)01 02 scanf(%d,%d, &Gm-n

11、, &Gm-e); /* 输入顶点和弧的个数信息输入顶点和弧的个数信息 */03 for (i=1; in; i+)04 scanf(%d, Gm-Gvi);05 for (i=1; in; i+) /* 邻接矩阵初始化邻接矩阵初始化 */06 for (j=1; jn; j+)07 if (i = j)08 Gm-Geij = 0;09 else10 Gm-Geij = ;11 for (k=1; ke; k+) /* 输入输入e条弧条弧 */12 13 scanf (%d%d, &i, &j);14 Gm-Geij = 1;15 16 7.2.2 基于邻接表存储基于

12、邻接表存储00 struct enode /* 定义边结点结构定义边结点结构 */01 02 int adjvex;03 struct enode *next;04 ;16 vertex fadj （a）单链表单链表头（顶点）头（顶点）结点结点 （b）单链表单链表边边结点结点 adjvex next 05 struct vnode /* 定义顶点结点结构定义顶点结点结构 */06 07 vertextype vertex; /* 顶点类型为顶点类型为vertextype */08 struct enode *fadj;09 ;10 typedef struct /* 定义一个图邻接表类型定义一

13、个图邻接表类型 */11 12 struct vnode GvMAX; /* 图的邻接表图的邻接表 */13 int n, e; /* 图的顶点数、边数信息图的顶点数、边数信息 */14 RGraph;7.2.2 基于邻接表存储基于邻接表存储217 1 3 2 3 4 5 4 1 1 2 4 5 vertex next fadj adjvex 6 1 6 2 4 3 5 6 4 6 图图7-12 图图7-5（5）所示无向图邻接表存储结构）所示无向图邻接表存储结构7.2.2 基于邻接表存储基于邻接表存储3网络的邻接表：网络的邻接表：18单链表单链表边边结点结构结点结构 adjvex next v

14、ertex fadj 单链表单链表头头结点结构结点结构 weight 1 2 3 4 1 1 76 3 53 3 23 weight fadj adjvex 23 2 34 3 23 4 53 next 2 76 vertex 7.2.2 基于邻接表存储基于邻接表存储4算法算法7-2 有向图邻接表存储算法。有向图邻接表存储算法。设置由单链表表头结点组成的一维数组设置由单链表表头结点组成的一维数组Gv，用于存放图的顶点序号（，用于存放图的顶点序号（vertex）以及指向顶点单链表的指针（）以及指向顶点单链表的指针（fadj）；设置变量）；设置变量n和和e，记录，记录图的顶点个数和弧的个数信息。图

15、的顶点个数和弧的个数信息。1900 Create_Gr(RGraph *Gr)01 02 struct enode *ptr;03 scanf(%d,%d, &Gr-n, &Gr-e);/* 输入顶点和弧的个数信息输入顶点和弧的个数信息 */04 for (i=1; in; i+) /* 对一维数组对一维数组Gv进行初始化进行初始化 */05 06 Gr-Gvi.vertex = i;07 Gr-Gvi.fadj = NULL;08 09 for (k=1; ke; k+) /* 构造各顶点的单链表构造各顶点的单链表 */10 11 scanf (%d,%d, &i,

16、&j);12 ptr = (struct enode *)malloc(sizeof(enode); /* 申请新结点申请新结点 */13 ptr-adjvex = j;14 ptr-next = Gr-Gvi.fadj; /* 新结点链入邻接表新结点链入邻接表 */15 Gr-Gvi.fadj = ptr;16 17 问题：如何求有向图顶点的入度？问题：如何求有向图顶点的入度？v解：可建立有向图的逆邻接表解：可建立有向图的逆邻接表20 正正邻接表：方便求顶点的邻接表：方便求顶点的出出度度 逆逆邻接表：方便求顶点的邻接表：方便求顶点的入入度度7.3 图的遍历图的遍历从图的某一个顶点出发

17、访问图中的所有顶点，且每个顶点从图的某一个顶点出发访问图中的所有顶点，且每个顶点只被访问一次的过程。只被访问一次的过程。21步骤如下：步骤如下：v 在图在图G中指定一个顶点中指定一个顶点v0作为遍历开始顶点，先访问作为遍历开始顶点，先访问v0并将其并将其进行适当标记表明已被访问。进行适当标记表明已被访问。v 依次从依次从v0的还未被访问的各个邻接顶点的还未被访问的各个邻接顶点w出发递归地进行深度出发递归地进行深度优先搜索优先搜索。v 如果图中还存在未访问过的顶点，则选其中之一由其出发重复如果图中还存在未访问过的顶点，则选其中之一由其出发重复上述步骤上述步骤“”“”“”，直到图中所有顶点都被访问

18、。，直到图中所有顶点都被访问。7.3.1 深度优先遍历深度优先遍历过程（利用栈结构）：过程（利用栈结构）：v 指定起点指定起点qv 访问访问qv q进栈进栈v 栈空否？栈空否？v a：不空，转：不空，转 v b：空，转：空，转 找栈顶元素未访问邻接点找栈顶元素未访问邻接点q a：找到，转：找到，转 b：找不到，出栈，转：找不到，出栈，转 结束结束遍历结果遍历结果：n结点，（结点，（n1）条边，无回路）条边，无回路按遍历过程经过的边为一棵深度优先生成树。按遍历过程经过的边为一棵深度优先生成树。22例子：例子：求下图从顶点求下图从顶点v0出发的深度遍历序列。出发的深度遍历序列。23解：解： v v

19、0 0 v v1 1 v v3 3 v v4 4 v v5 5 v v2 2算法算法7-3 基于邻接表的无向图深度优先搜索算法基于邻接表的无向图深度优先搜索算法 00 Depth_Gr(RGraph *Gr, int n)01 02 for (i=1; i=n; i+) /* 记录顶点是否被访问的一维数组记录顶点是否被访问的一维数组flag初始化初始化 */03 flagi = 0;04 for (i=1; inext) /* 沿着沿着vi的链表前进的链表前进 */15 16 k = ptr-adjvex;17 if (flagk = 0)/* 对未访问的顶点继续深度优先搜索对未访问的顶点继续

20、深度优先搜索 */18 DFS(Gr, k, flag);19 20 25上机：上机： 使用邻接表存储图，编写其深度优先遍历的非递归算法。使用邻接表存储图，编写其深度优先遍历的非递归算法。26 过程：过程：v 访问地点；起点进栈；访问地点；起点进栈；v while （栈不空）（栈不空）v 找栈顶未访问邻接点找栈顶未访问邻接点p；v if 找到找到v 访问；进栈；访问；进栈；v elsev 出栈；出栈； 7.3.2 广度优先遍历广度优先遍历步骤如下：步骤如下：v 在图中指定一个顶点在图中指定一个顶点v0为遍历起始点，访问顶点为遍历起始点，访问顶点v0并将其进行并将其进行标记以表明被访问；标记以表

21、明被访问；v 依次访问依次访问 v0 的所有相邻顶点的所有相邻顶点 w1, w2, , wx ，此时需要为，此时需要为 v 的的邻接顶点规定一种顺序，然后依次访问与邻接顶点规定一种顺序，然后依次访问与 w1, w2, , wx 邻接的邻接的所有未访问顶点直到所有已访问顶点的相邻顶点都已访问。所有未访问顶点直到所有已访问顶点的相邻顶点都已访问。v 如果图中还有未访问顶点，则选择其中之一作为新的遍历起始如果图中还有未访问顶点，则选择其中之一作为新的遍历起始顶点，由其出发进行广度优先搜索直到所有顶点都已访问。顶点，由其出发进行广度优先搜索直到所有顶点都已访问。27算法算法7-4 基于邻接表的无向图广

22、度优先搜索算法基于邻接表的无向图广度优先搜索算法00 Breadth_Gr(RGraph *Gr, int n)01 02 for (i=0; in; i+) /* 记录顶点是否被访问的一维数组记录顶点是否被访问的一维数组flag初始化初始化 */03 flagi = 0;04 for (i=0; in; i+) /* 对整个图进行广度优先搜索遍历对整个图进行广度优先搜索遍历 */05 if (flagi = 0) 06 BFS(Gr, i, flag); /* 从顶点从顶点vi开始对图进行广度优先遍历开始对图进行广度优先遍历 */07 28算法算法7-4 基于邻接表的无向图广度优先搜索算法基

23、于邻接表的无向图广度优先搜索算法2 08 BFS(RGraph *Gr, int i, int flag )09 10 Qs_front=0; /* 队首、队尾指针初始化队首、队尾指针初始化 */11 Qs_rear=0;12 Qs_rear + ;13 QsQs_rear = i ;/* 让顶点让顶点vi的序号进队列的序号进队列 */14 flagi = 1;15 printf (%d, i);/* 访问顶点访问顶点vi */16 while (front adjvex;24 if (flagk = 0)25 26 flagk = 1;27 pringf (%d, k);28 Qs_rear

24、 + ;29 QsQs_rear = k ; 30 31 ptr = ptr-next;32 33 34 30过程（利用队列结构）：过程（利用队列结构）：v 访问指定起点访问指定起点qv q所有未访问邻接点依次访问、入队列所有未访问邻接点依次访问、入队列v 队列空否：队列空否：v a：不空，出队列赋为：不空，出队列赋为q，转，转 v b：空，转：空，转v 结束结束遍历结果：遍历结果：n结点，（结点，（n1）条边，无回路）条边，无回路按遍历过程经过的边为一棵广度优先生成树。按遍历过程经过的边为一棵广度优先生成树。31例子：例子：求下图从顶点求下图从顶点v0出发的广度遍历序列。出发的广度遍历序列。

25、32解：解： v v0 0 v v1 1 v v2 2 v v3 3 v v4 4 v v5 5注意：注意：v深度优先遍历或者广度优先遍历能遍历到指深度优先遍历或者广度优先遍历能遍历到指定起点所在的连通分量中的所有顶点。定起点所在的连通分量中的所有顶点。337.3.3简单路径与路径长度最小路径简单路径与路径长度最小路径 给定一个图给定一个图G和其中两个顶点和其中两个顶点vi和和vj，通常存在着，通常存在着vi和和vj连接多连接多条简单路径，其中必有一条路径长度最短的路径。条简单路径，其中必有一条路径长度最短的路径。具体做法具体做法如下：如下：34v1) 将链队列结点改为将链队列结点改为“双链双

26、链”结点结点 即结点中包含即结点中包含next 和和prior两两个指针；个指针；v2) 修改进入队列操作修改进入队列操作 插入新的队尾结点时，令其插入新的队尾结点时，令其prior域的指针域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；指向刚刚出队列的结点，即当前的队头指针所指结点；v3) 修改出队列的操作修改出队列的操作 出队列时，仅移动队头指针，而不将队头结出队列时，仅移动队头指针，而不将队头结点从链表中删除。点从链表中删除。7.3.3简单路径与路径长度最小路径简单路径与路径长度最小路径算法算法7-5 路径长度最短路径算法路径长度最短路径算法3500 typedef DuLink

27、List QueuePtr; 01 void InitQueue(LinkQueue& Q) 02 03 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);04 Q.front-next = Q.rear-next = NULL05 06 void EnQueue( LinkQueue& Q, QelemType e )07 08 p = (QueuePtr) malloc (sizeof(QNode);09 p-data = e; p-next = NULL;10 p-priou = Q.front11 Q.rear-next = p

28、; Q.rear = p;12 15 void DeQueue( LinkQueue& Q, QelemType& e )16 17 Q.front = Q.front-next; e = Q.front-data18 例子：例子：设有如图所示无向图，需要计算出从设有如图所示无向图，需要计算出从v0到到v5的路的路径长度最短的路径。径长度最短的路径。36解：链队列结构：解：链队列结构： 3 0 2 4 1 5 例子（续）：例子（续）：计算过程：计算过程：37状状 态态 Qs Flag 访问顶点访问顶点 入队顶点入队顶点 出队顶点出队顶点 初始初始 v0 flag0=1 v0 v

29、0 01 v0 v0 02 v0,v1 flag1=1 v1 v1 03 v0,v1,v2 flag2=1 v2 v2 04 v0,v1,v2 v1 05 v0,v1,v2 v2 06 v0,v1,v2, v3 flag3=1 v3 v3 07 v0,v1,v2, v3, v4 flag4=1 v4 v4 08 v0,v1,v2, v3, v4 v3 09 v0,v1,v2, v3, v4 , v5 flag5=1 v5 v5 10 v0,v1,v2, v3, v4, v5 v4 7.4 生成树与最小生成树生成树与最小生成树7.4.1 图的生成树图的生成树v 生成树极小连通子图（生成树极小连通

30、子图（n-1）条边）条边“极小极小”的含义包括两个方面含义：的含义包括两个方面含义： 如果在生成树中去掉任何一条边，生成树将会不再连通；如果在生成树中去掉任何一条边，生成树将会不再连通； 如果在生成树中添加任何一条边，生成树将会出现回路。如果在生成树中添加任何一条边，生成树将会出现回路。387.4.1 图的生成树图的生成树21、深度和广度优先生成树、深度和广度优先生成树v从从连通图连通图G任一顶点出发对任一顶点出发对G进行遍历可访问进行遍历可访问G的所有顶点。遍历的所有顶点。遍历时经过的边加上所有顶点就构成时经过的边加上所有顶点就构成G的一个连通子图，这样的连通的一个连通子图，这样的连通子图就

31、是子图就是G的一棵生成树。的一棵生成树。 生成树不唯一生成树不唯一：深度优先生成树（：深度优先生成树（DFS） 广度优先生成树（广度优先生成树（BFS） 39例子：例子：设有如图所示无向设有如图所示无向图，画出其深度优先和图，画出其深度优先和广度优先生成树。广度优先生成树。40解：解：例子：例子：设有如图所示有向设有如图所示有向图，画出其深度优先和图，画出其深度优先和广度优先生成树。广度优先生成树。41解：解：7.4.2 最小生成树最小生成树1、图的最小生成树、图的最小生成树v 网络中所有生成树中代价最小的树。网络中所有生成树中代价最小的树。复习：网络的邻接矩阵：复习：网络的邻接矩阵：427.

32、4.2 最小生成树最小生成树22、普里姆、普里姆(Prim)算法算法原理：原理：选取一个顶点作为起点，每次通过代价最小的边选择一个顶选取一个顶点作为起点，每次通过代价最小的边选择一个顶点并入生成树中，直到包含所有顶点。点并入生成树中，直到包含所有顶点。建立无向网络并基于建立无向网络并基于prim算法求最小生成树算法详见算法求最小生成树算法详见7.4.2节算法节算法7-6。 基本思想：基本思想： 将把图将把图G中的顶点分成两部分：已在中的顶点分成两部分：已在MST中的顶点集合中的顶点集合U，还未，还未在在MST的顶点集合的顶点集合VU。 在在VU里挑选出与里挑选出与U中某个顶点相距最近（即权值最

33、小）的那个中某个顶点相距最近（即权值最小）的那个顶点，把这个顶点从顶点，把这个顶点从VU移到移到U中。由此使得集合中。由此使得集合U不断扩大，不断扩大，VU不断缩小，当不断缩小，当U=V，VU=时，算法结束。时，算法结束。432、普里姆、普里姆(Prim)算法算法算法算法7-6 建立无向网络并基于建立无向网络并基于prim算法求最小生成树。算法求最小生成树。00 #include 01 #define MAX_INT 10000 /* 正无穷正无穷 */02 #define M MAX_INT 03 #define N 4 /* 顶点数顶点数 */04 void print(int treeN

34、N-1) 05 06 int i; 07 for(i=0;i N;i+) 08 printf( %-8d%-8d%-8dn,treei0,treei1,treei2);09 getchar(); 10 442、普里姆、普里姆(Prim)算法算法算法算法7-6 建立无向网络并基于建立无向网络并基于prim算法求最小生成树。算法求最小生成树。11 int prim(int wNN,int v,int treeNN-1)12 13 int i,j,k,p,min,c;14 int lowcostN,closetN;15 for(i=0;i N;i+)16 17 closeti=v;18 lowcos

35、ti=wvi;19 20 c=0;21 p=0;452、普里姆、普里姆(Prim)算法算法算法算法7-6 建立无向网络并基于建立无向网络并基于prim算法求最小生成树。算法求最小生成树。22 for(c=i=0;i N-1;i+)23 24 min=MAX_INT;25 for(j=0;j N;j+) /* 找连接生成树所有边的代价最小值找连接生成树所有边的代价最小值min */26 if(lowcostj!=0)&(lowcostj min)27 28 min=lowcostj;29 k=j;30 31 treep0=closetk; /* 对新加入生成树的边进行赋值对新加入生成树的

36、边进行赋值 */32 treep1=k;33 treep2=min;34 p+;35 c=c+min; /* 更新最小生成树的代价更新最小生成树的代价 */36 lowcostk=0;37 wkclosetk=0;462、普里姆、普里姆(Prim)算法算法算法算法7-6 建立无向网络并基于建立无向网络并基于prim算法求最小生成树。算法求最小生成树。38 for(j=0;j N;j+) /* 更新新加入生成树顶点到生成树外顶点的权值更新新加入生成树顶点到生成树外顶点的权值 */39 if(wkj!=0&wkj lowcostj)40 41 lowcostj=wkj;42 closetj

37、=k;43 44 print(tree);45 46 return c; 47 472、普里姆、普里姆(Prim)算法算法算法算法7-6 建立无向网络并基于建立无向网络并基于prim算法求最小生成树。算法求最小生成树。48 main()49 50 int M1NN=M,3,5,6, /* 4顶点的图邻接矩阵顶点的图邻接矩阵 */51 3,M,M,4, 52 5,M,M,7, 53 6,4,7,M; 54 int v=0,treeNN-1,weighttree,i; 55 for(i=0;iN;i+) 56 treei0=treei1=treei2=0; 57 weighttree=prim(M

38、1,v,tree); 58 printf( nweighttree result = %dn,weighttree);59 print(tree);60 return;61 48练习：练习：v用普里姆算法（用普里姆算法（Prim）的思想，画出该图生成最小生成树的过程。）的思想，画出该图生成最小生成树的过程。49v适合：与顶点数有关，适合边稠密的网络。适合：与顶点数有关，适合边稠密的网络。v总的总的时间复杂度：时间复杂度：O(n2)7.4.2 最小生成树最小生成树33、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法原理：原理：所有边按权排序，每次取最短边，如不构成回路，则并入生所有边按权排序，

39、每次取最短边，如不构成回路，则并入生成树中，否则舍弃。直到并入了（成树中，否则舍弃。直到并入了（n-1）条边。）条边。具体步骤：具体步骤： 以图以图G的的E为基础，按照各边的权值，由小到大对它们进行挑选；为基础，按照各边的权值，由小到大对它们进行挑选； 如果挑选出来的边的两个顶点分属如果挑选出来的边的两个顶点分属S中的两个不同的连通分量，中的两个不同的连通分量，那么就将此边从那么就将此边从E中去除，并用此边将中去除，并用此边将S中的那两个连通分量连接中的那两个连通分量连接成一个连通分量，成为最小生成树成一个连通分量，成为最小生成树S中的一个新连通分量；中的一个新连通分量； 如果挑选出来的边的两

40、个顶点属于如果挑选出来的边的两个顶点属于S中的同一个连通分量，那么中的同一个连通分量，那么就将其从就将其从E中舍弃，重新再挑选中舍弃，重新再挑选； 不断地实行（不断地实行（1）（）（3）步，当）步，当S里只剩下一个连通分量时，算里只剩下一个连通分量时，算法终止。法终止。503、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。00 #include01 #include02 #define M 2003 #define MAX 2004 typedef struct 05 06 int begi

41、n;07 int end;08 int weight;09 edge;10 typedef struct11 12 int adj;13 int weight;14 AdjMatrixMAXMAX;513、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。15 typedef struct /* 定义一个图类型定义一个图类型 */16 17 AdjMatrix arc;18 int vexnum, arcnum;19 MGraph;20 MGraph *CreatGraph() /* 创建一个图

42、创建一个图 */21 22 int i,j,n,m,w;23 MGraph *G;24 G = (MGraph*)malloc(sizeof(MGraph);25 printf(Input vertex nember:); /* 输入点数输入点数 */26 scanf(%d,&G-vexnum);27 printf(Input edges number:); /* 输入边数输入边数 */28 scanf(%d,&G-arcnum);523、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最

43、小生成树。29 for (i = 1; i vexnum; i+) /* 初始化图初始化图 */30 for ( j = 1; j vexnum; j+)31 G-arcij.adj = G-arcji.adj = 0;32 for ( i = 1; i arcnum; i+) /* 输入边和权值输入边和权值 */33 34 printf(nInput edge(i j weight):);35 scanf(%d %d %d,&n,&m,&w);36 G-arcnm.weight=w;37 G-arcnm.adj = G-arcmn.adj = 1;38 533、克鲁斯

44、卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。39 printf(Adjacency Matrix :n);40 for ( i = 1; i vexnum; i+)41 42 for ( j = 1; j vexnum; j+)43 printf(%d ,G-arcij.weight);44 printf(n);45 46 return G;47 543、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小

45、生成树。48 void sort(edge edges,MGraph *G) /* 对权值进行排序对权值进行排序 */49 50 int i,j,temp;51 for ( i = 1; i arcnum; i+)52 53 for ( j = i + 1; j arcnum; j+)54 55 if (edgesi.weight edgesj.weight) /* 交换边信息交换边信息 */56 57 temp = edgesi.begin;58 edgesi.begin = edgesj.begin;59 edgesj.begin = temp;60 temp = edgesi.end;6

46、1 edgesi.end = edgesj.end;62 edgesj.end = temp;553、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。63 temp = edgesi.weight;64 edgesi.weight = edgesj.weight;65 edgesj.weight = temp;66 67 68 69 printf( Edges after sort:n);70 for (i = 1; i arcnum; i+)71 printf( weight: %dn, e

47、dgesi.begin, edgesi.end, edgesi.weight);72 printf(n);73 563、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。74 void MiniSpanTree(MGraph *G) /* 生成最小生成树生成最小生成树 */75 76 int i, j, n, m;77 int k = 1;78 int ringM;79 edge edgesM;80 for ( i = 1; i vexnum; i+)81 82 for (j = i + 1;

48、j vexnum; j+)83 84 if (G-arcij.adj = 1)85 86 edgesk.begin = i;87 edgesk.end = j;88 edgesk.weight = G-arcij.weight;89 k+;90 573、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。93 sort(edges, G);94 for (i = 1; i arcnum; i+) /* 初始化每个顶点的连通分量编号初始化每个顶点的连通分量编号 */95 ringi = i;96 p

49、rintf(Kruscal mintree:n);97 for (i = 1,k=1; k vexnum;i+) /* 核心部分核心部分 */98 99 n = ringedgesi.begin; /* 取得起点连通分量编号取得起点连通分量编号 */100 m = ringedgesi.end; /* 取得终点连通分量编号取得终点连通分量编号 */101 if (n != m)102 103 for (j = 1; j arcnum; j+) /* 修改连通分量编号修改连通分量编号 */104 if (ringj = n)105 ringm = m;106 printf( weihet: %d

50、n, edgesi.begin, edgesi.end, edgesi.weight);107 k=k+1;108 583、克鲁斯卡尔、克鲁斯卡尔(Kruscal)算法算法算法算法7-7 建立无向网络并基于建立无向网络并基于Kruscal算法求最小生成树。算法求最小生成树。111 void main()112 113 MGraph *G;114 G = CreatGraph(G);115 MiniSpanTree(G);116 59练习：练习：v用克鲁斯卡尔算法（用克鲁斯卡尔算法（Kruskal）的思想，画出该图生成最小生成）的思想，画出该图生成最小生成树的过程。树的过程。60v总的时间复杂度

51、：总的时间复杂度：与边排序算法有关与边排序算法有关v适合：适合：与边有关，适合边稀疏的网络。与边有关，适合边稀疏的网络。3、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法2问题：如何判断是否构成回路？问题：如何判断是否构成回路？ 定义连通分量数组定义连通分量数组ringn，初始时各个，初始时各个ringi各不相同，找各不相同，找到边（到边（i，j）时，判断）时，判断ringi与与ringj是否相等：是否相等：相等：相等：说明说明i，j在同一个连通分量，舍弃；在同一个连通分量，舍弃；不相等：不相等： i，j在不同连通分量，边（在不同连通分量，边（i，j）并入生成树中，并把所有）并入生成树中，并

52、把所有与与ringi相等的相等的ring值改为值改为ringj。617.5 最短路径最短路径v问题的提出：问题的提出： A、B有若干路径相通，如何找寻一代价最小的路径？有若干路径相通，如何找寻一代价最小的路径？ v例子：例子：627.5 最短路径最短路径21、单源最短路径、单源最短路径63Dijkstra算法具体步骤：算法具体步骤： 初始时，集合初始时，集合U里只含一个源点里只含一个源点u，集合，集合VU里是图中除里是图中除u以外的以外的所有顶点，所有顶点，u到其它顶点的距离是它们间弧的权值；到其它顶点的距离是它们间弧的权值； 从从VU里挑选出一个与源点里挑选出一个与源点u的距离为最小的顶点的

53、距离为最小的顶点v，把它从，把它从VU移到移到U里，然后对里，然后对VU里剩下的顶点（比如里剩下的顶点（比如k）到源点）到源点u的距离进的距离进行修改，方法是若图中存在弧（行修改，方法是若图中存在弧（v, k），且该弧的权值加上），且该弧的权值加上u到到v的距离之和小于原先的距离之和小于原先u到到k的距离时，就用此的距离时，就用此“和和”取代原先取代原先u到到k的距离，否则原先的距离，否则原先u到到k的距离保持不变；的距离保持不变； 逐次对集合逐次对集合VU实行操作（实行操作（2），当），当VU为空时，算法结束，所求为空时，算法结束，所求得的得的u到各顶点的距离即是源点到其它顶点的最短路径长度

54、到各顶点的距离即是源点到其它顶点的最短路径长度。1、单源最短路径、单源最短路径算法算法7-8求单源最短路径的求单源最短路径的Dijkstra算法算法6400 #include01 #include02 #define MAX 10000 /* 正无穷正无穷 */03 #define n 6 /* 顶点数顶点数 */04 void Dijkstra(int v,int costn+1n+1,int distn+1,int prevn+1)05 06 int i,j,k,temp=MAX;07 int u,newdist,min;08 int sn+1=0 ; /* 作为标记定义具有最短路径的顶点

55、子集作为标记定义具有最短路径的顶点子集s */09 sv = 1; /* 源顶点标记为已具有最短路径源顶点标记为已具有最短路径 */10 prevv=v; /* 源顶点的前驱即为本身源顶点的前驱即为本身 */1、单源最短路径、单源最短路径算法算法7-8求单源最短路径的求单源最短路径的Dijkstra算法算法6511 for (i = 1; i = n; i+) /* 初始化最小路径代价初始化最小路径代价 */12 13 disti = costvi; 14 previ=v;15 16 u=v; /* u为中转顶点为中转顶点 */17 for (i = 1; i n; i+)18 19 for

56、(j = 1; j distu+costuj)22 23 distj=distu+costuj;24 prevj=u;25 26 1、单源最短路径、单源最短路径算法算法7-8求单源最短路径的求单源最短路径的Dijkstra算法算法6627 min=MAX;28 for (j = 1; j = n; j+)29 30 if (sj=0) & (distj = 0; j-) /* 逆向输出路径数组逆向输出路径数组way */52 printf(%d - ,wayj);53 printf(%dn,u);54 1、单源最短路径、单源最短路径算法算法7-8求单源最短路径的求单源最短路径的Dijk

57、stra算法算法6855 void main()56 57 int i,j,k,w;58 int v,u,arcnum;59 int costn+1n+1=0,0,0,0,0,0,0,60 0,0,10,MAX,5,MAX,MAX, /* 6顶点的网络邻接矩阵顶点的网络邻接矩阵 */61 0,10,0,1,7,MAX,MAX,62 0,MAX,1,0,MAX,MAX,5,63 0,5,7,MAX,0,2,6,64 0,MAX,MAX,MAX,2,0,3,65 0,MAX,MAX,5,6,3,0; 66 int prevn+1; /* 定义顶点路径的前驱顶点定义顶点路径的前驱顶点 */67 in

58、t distn+1; /* 最短路径代价最短路径代价 */68 printf( The number of vertexes is %d!n,n);1、单源最短路径、单源最短路径算法算法7-8求单源最短路径的求单源最短路径的Dijkstra算法算法6969 printf(please input the source node: );70 scanf(%d,&v);71 Dijkstra(v, cost,dist,prev);72 printf(n*have confirm the best path*n);73 for(i = 1; i = n ; i+)74 75 if(i!=v)

59、76 77 printf(nThe lowest cost is %d, ,v,i,disti);78 ShowPath(v,i, prev);79 80 81 例子：例子：v利用利用Dijkstra算法，求算法，求下下图源点图源点v1到其它顶点的最短路径到其它顶点的最短路径。70例子（续）：例子（续）：v基于基于Dijkstra算法最短路径计算算法最短路径计算过程：过程：717.5 最短路径最短路径32、顶点对间最短路径、顶点对间最短路径72已知有向网图已知有向网图G=（V，E），求其中任意一对顶点之间的最短路径。），求其中任意一对顶点之间的最短路径。Floyd算法具体步骤：算法具体步骤：

60、初始时，把邻接矩阵记为初始时，把邻接矩阵记为D(0)，它的元素记录了图中各弧的权值；，它的元素记录了图中各弧的权值； 逐次把顶点逐次把顶点vk(1kn)插入到矩阵所有元素中去进行探测，如果矩插入到矩阵所有元素中去进行探测，如果矩阵原先有路径（阵原先有路径（vi, vj）(i j)，现在插入，现在插入vk后，有路径（后，有路径（vi, vk）和）和（vk, vj），且：），且：D (vi, vk) + D (vk, vj) D (vi, vj)那么，就用那么，就用D (vi, vk) + D (vk, vj)代替代替D (vi, vj)，于是形成一个新的矩，于是形成一个新的矩阵阵D(k)； 在完成在完成n次探测后，矩阵次探测后，矩阵D(n)里记录了各顶点对之间的最短路径。里记录了各顶点对之间的最短路径。例子：例子：v利用利用Floyd算法，求下