《数据结构——C语言描述》第7章：图.ppt

《《数据结构——C语言描述》第7章：图.ppt》由会员分享，可在线阅读，更多相关《《数据结构——C语言描述》第7章：图.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 基本概念基本概念 图的存储结构图的存储结构 图的遍历图的遍历 生成树生成树 最短路径最短路径 拓扑排序拓扑排序第第7 7章章 图图7.1 图的基本概念图的基本概念图定义图定义图定义图定义 图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关及顶点间的关及顶点间的关系系系系集合组成的一种数据结构集合组成的一种数据结构集合组成的一种数据结构集合组成的一种数据结构：GraphGraph(V V,E E)其中其中其中其中 V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 是顶点的有穷是顶点的有穷是顶点的有穷是顶点的有穷非空集合；非空

2、集合；非空集合；非空集合；E E=(=(x x,y y)|)|x x,y y V V 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)(edge)集集集集合。合。合。合。有向图与无向图有向图与无向图 若图若图G G中的每条边都是有方中的每条边都是有方向的，则称向的，则称G G为有向图。有向边也称为为有向图。有向边也称为弧弧。若图若图G G中的每条边都是没有方向的，则称中的每条边都是没有方向的，则称G G为为无向图。无向图。完全图完全图 对有对有n n个顶点的图，若为无向图且边个顶点的图，若为无向

3、图且边数为数为n(n-1)/2n(n-1)/2，则称其为，则称其为无向完全图无向完全图；若为；若为有向图且边数为有向图且边数为n(n-1)n(n-1)，则称其为，则称其为有向完有向完全图。全图。邻接顶点邻接顶点 若（若（v vi i,v,vj j）是一条无向边，则称）是一条无向边，则称顶点顶点v vi i和和v vj j互为邻接点，或称互为邻接点，或称v vi i和和v vj j相邻接，相邻接，并称边（并称边（v vi i,v,vj j）关联于顶点）关联于顶点v vi i和和v vj j，或称，或称（v vi i,v,vj j）与顶点）与顶点v vi i和和v vj j相关联。相关联。n n顶

4、点的度顶点的度顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条的度是与它相关联的边的条数。记作数。记作数。记作数。记作TD(TD(v v)。顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(v);ID(v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 O

5、D(v)OD(v)。n n子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V,E)(V,E)和和和和 GG(V,E)(V,E)。若。若。若。若 VV V V 且且且且 EE E,E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。路径路径路径路径 在图在图在图在图 G G G G(V V V V,E E E E)中中中中,若存在一个顶点序列若存在一个顶点序列若存在一个顶点序列若存在一个顶点序列 v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2,v v v vpmpmpmpm，使得，使得，使得，使

6、得(v v v vi i i i,v v v vp p p p1 1 1 1)、(v v v vp p p p1 1 1 1,v v v vp p p p2 2 2 2)、.、(v v v vpmpmpmpm,v v v vj j j j)均属于均属于均属于均属于E E E E，则称顶点则称顶点则称顶点则称顶点v v v vi i i i到到到到v v v vj j j j存在一存在一存在一存在一 条路径。若一条路径上除了条路径。若一条路径上除了条路径。若一条路径上除了条路径。若一条路径上除了v v v vi i i i 和和和和v v v vj j j j 可以相同外，可以相同外，可以相同外

7、，可以相同外，其余顶点均不相同，则称此路径为一条其余顶点均不相同，则称此路径为一条其余顶点均不相同，则称此路径为一条其余顶点均不相同，则称此路径为一条简单路径简单路径简单路径简单路径 。起点和终点相同的路径称为。起点和终点相同的路径称为。起点和终点相同的路径称为。起点和终点相同的路径称为简单回路或简单环简单回路或简单环简单回路或简单环简单回路或简单环。图的连通图的连通图的连通图的连通 在无向图在无向图在无向图在无向图G G G G中，若两个顶点中，若两个顶点中，若两个顶点中，若两个顶点v v v vi i i i和和和和v v v vj j j j之间有之间有之间有之间有 路径存在，则称路径存

8、在，则称路径存在，则称路径存在，则称v v v vi i i i 和和和和v v v vj j j j 是连通的。若是连通的。若是连通的。若是连通的。若G G G G中任意两中任意两中任意两中任意两 个顶点都是连通的，则称个顶点都是连通的，则称个顶点都是连通的，则称个顶点都是连通的，则称G G G G为为为为连通图连通图连通图连通图。非连通图的非连通图的非连通图的非连通图的 极大连通子图叫做极大连通子图叫做极大连通子图叫做极大连通子图叫做连通分量连通分量连通分量连通分量。强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,

9、若对于每一若对于每一若对于每一若对于每一对顶点对顶点对顶点对顶点vivivivi和和和和vj,vj,vj,vj,都存在一条从都存在一条从都存在一条从都存在一条从vivivivi到到到到vjvjvjvj和从和从和从和从vjvjvjvj到到到到vivivivi的的的的路径路径路径路径,则称此图是强连通图。非强连通图的极大强连则称此图是强连通图。非强连通图的极大强连则称此图是强连通图。非强连通图的极大强连则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。通子图叫做强连通分量。通子图叫做强连通分量。通子图叫做强连通分量。权权权权 某些图的边具有与它相关的数某些图的边具有与它相关的数某些图的

10、边具有与它相关的数某些图的边具有与它相关的数,称之为权。这称之为权。这称之为权。这称之为权。这种带权图叫做种带权图叫做种带权图叫做种带权图叫做网络网络网络网络。12356874ABDCE1079667123151660304535804075权图权图权图权图 生成树生成树 一个连通图的生成树是它的极小一个连通图的生成树是它的极小 连通子图，在连通子图，在n个顶点的情形下，有个顶点的情形下，有n-1条条 边。边。n n生成林生成林 若若G G是一个不连通的无向图，是一个不连通的无向图，G G的的每个连通分量都有一棵生成树，这些生成每个连通分量都有一棵生成树，这些生成树构成树构成G G的生成森林。

11、的生成森林。7.2 图的存储结构图的存储结构 在图的邻接矩阵表示中，有一个记录各个顶点信在图的邻接矩阵表示中，有一个记录各个顶点信在图的邻接矩阵表示中，有一个记录各个顶点信在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的息的顶点表，还有一个表示各个顶点之间关系的息的顶点表，还有一个表示各个顶点之间关系的息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。邻接矩阵。邻接矩阵。邻接矩阵。设图设图设图设图 A=(V,E)A=(V,E)是一个有是一个有是一个有是一个有 n n 个顶点的图，则图的邻个顶点的图，则图的邻个顶点的图，则图的邻个顶点的图，则图的邻接矩阵是一

12、个二维数组接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组 A.EdgennA.Edgenn，定义：，定义：，定义：，定义：无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。可能是不对称的。可能是不对称的。可能是不对称的。邻接矩阵邻接矩阵(Adjacency Matrix)在有向图中在有向图中在有向图中在有向图中,统计第统计第统计第统计第 i i 行行行行 1 1 的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 i i 的出度，的出度，的出

13、度，的出度，统计第统计第统计第统计第 j j 列列列列 1 1 的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点 j j 的入度。的入度。的入度。的入度。在无向图中在无向图中在无向图中在无向图中,统计第统计第统计第统计第 i i 行行行行(列列列列)1)1 的个数可得顶点的个数可得顶点的个数可得顶点的个数可得顶点i i 的度。的度。的度。的度。网络的邻接矩阵网络的邻接矩阵邻接矩阵表示法中图的类型定义邻接矩阵表示法中图的类型定义：#define MAXSIZE 100 /*图的顶点个数图的顶点个数*/typedef int datatype;typedef struct datatype

14、 vexsMAXSIZE；/*顶点信息表顶点信息表*/int edgesMAXSIZE MAXSIZE；*邻接矩阵邻接矩阵*/int n，e；/*顶点数和边数顶点数和边数*/graph；21435无向图无向图无向图无向图BADCE有向图有向图有向图有向图215346203050407080有向权图有向权图有向权图有向权图邻接矩阵表示法中无向网络的建立算法邻接矩阵表示法中无向网络的建立算法void Create_Graph（graph *ga）int i，j，k，w；printf(请输入图的顶点数和边数：请输入图的顶点数和边数：n)；scanf(%d，&(ga-n)，&(ga-e)；printf

15、(请输入顶点信息请输入顶点信息(顶点编号顶点编号)，建立顶点信息表：，建立顶点信息表：n)；for(i=0；in；i+)scanf(%c,&(ga-vexsi)；/*输入顶点信息输入顶点信息*/for(i=0；in；i+)/*邻接矩阵初始化邻接矩阵初始化*/for(j=0；jn；j+)ga-edgesij=0；for(k=0；ke；k+)/*读入边的顶点编号和权值，建立邻接矩阵读入边的顶点编号和权值，建立邻接矩阵*/printf(请输入第请输入第%d条边的顶点序号条边的顶点序号i，j和权值和权值w：,k+1)；scanf(%d，%d，%d，&i，&j，&w)；ga-edgesij=w；ga-e

16、dgesji=w；算法分析算法分析该算法的执行时间是该算法的执行时间是O(n+n2+e)，由于，由于en)；for(i=1;in;i+)/*读入顶点信息，建立顶点表读入顶点信息，建立顶点表*/scanf(“n%c”，&(ga-adlistidata)；ga-adlistifirst=NULL；e=0；scanf(“n%d,%dn”，&i，&j)；/*读入一个顶点对号读入一个顶点对号i和和j*/while(i0)/*读入顶点对号读入顶点对号,建立边表建立边表*/e+；/*累计边数累计边数*/p=(pointer)malloc(size(struct node)；/*生成新的邻接点序号为生成新的邻

17、接点序号为j的表结点的表结点*/p-vertex=j;p-next=ga-adlistifirst；ga-adlisti.first=p；/*将新表结点插入到顶点将新表结点插入到顶点vi的边表的头部的边表的头部*/p=(pointer)malloc(size(struct node)；/*生成邻接点序号为生成邻接点序号为i的表结点的表结点*/p-vertex=i；p-next=ga-adlistj.first;ga-adlistj.first=p；/*将新表结点插入到顶点将新表结点插入到顶点vj的边表头部的边表头部*/scanf(“n%d,%dn”，&i，&j)；/*读入一个顶点对号读入一个顶

18、点对号i和和j*/ga-e=e；算法的时间复杂度是算法的时间复杂度是O（ne）在邻接表的边链表中，各个表结点的链入顺序在邻接表的边链表中，各个表结点的链入顺序任意，视表结点输入次序而定。任意，视表结点输入次序而定。设图中有设图中有 n 个顶点，个顶点，e 条边，则用邻接表表示条边，则用邻接表表示无向图时，需要无向图时，需要 n 个表头结点，个表头结点，2e 个表结点；个表结点；用邻接表表示有向图时，若不考虑逆邻接表，用邻接表表示有向图时，若不考虑逆邻接表，只需只需 n 个表头结点，个表头结点，e 个表结点。个表结点。带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 cost。网

19、络网络(带权图带权图)的邻接表的邻接表表结点vertexcostnext7.3 图的遍历性图的遍历性 从已给的连通图中某一顶点出发，沿着一些边访遍从已给的连通图中某一顶点出发，沿着一些边访遍从已给的连通图中某一顶点出发，沿着一些边访遍从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就叫做叫做叫做叫做图的遍历图的遍历图的遍历图的遍历 (Graph Traversal)(Graph Traversal)。图中可能存在回路，且图的任

20、一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标

21、志顶点是否被访问过的辅助数组问过的辅助数组问过的辅助数组问过的辅助数组 visited visited ，它的初始状态为，它的初始状态为，它的初始状态为，它的初始状态为 0 0，在，在，在，在图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点图的遍历过程中，一旦某一个顶点 i i 被访问，就立被访问，就立被访问，就立被访问，就立即让即让即让即让 visited i visited i 为为为为 1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。深度优先搜索深度优先搜索DFS(Depth First Search)深度优

22、先搜索的示例深度优先搜索的示例 DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由后，由后，由 v v 出发，出发，出发，出发，访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点 w w1 1；再从；再从；再从；再从 w w1 1 出发，访问与出发，访问与出发，访问与出发，访问与 w w1 1邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点邻接但还没有访问过的顶点 w w2 2；然后再从；然后再从；然后再从；然后再从 w w2 2 出出出出发，进行类似的访问，发，进

23、行类似的访问，发，进行类似的访问，发，进行类似的访问，如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达如此进行下去，直至到达所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点所有的邻接顶点都被访问过的顶点 u u 为止。接着，为止。接着，为止。接着，为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此有其它没有被访问

24、的邻接顶点。如果有，则访问此有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。过程，直到连通图中所有顶点都被访问过为止。深度优先

25、搜索算法深度优先搜索算法void DFS（graph *g）/*按深度优先搜索法遍历图按深度优先搜索法遍历图g*/int i；for（i0；ig-n；i+）visidi=0；/*初始化数组初始化数组visid，使每个元素为，使每个元素为0*/*标示图中的每个结点都未曾访问过标示图中的每个结点都未曾访问过*/for（i=0；in；i+）if（!visidi）DFSM(g，i)；/*调用函数调用函数DFSM，对图进行遍历，对图进行遍历*/void DFSM（graph *g，int i）/*邻接矩阵上进行邻接矩阵上进行DFS遍历遍历*/int j；printf（深度优先遍历结点：深度优先遍历结点：

26、%cn，g-vexsi）；）；visidi=1;/*假定假定g-vexsi为顶点的编号，然后变访问标志为为顶点的编号，然后变访问标志为1*/for（j=0；jn；j+）if（g-edgesij=1）！）！visidj）DFSM（g，j）；）；void DFSL（lkgraph *g，int n）/*邻接表上进行邻接表上进行DFS遍历遍历*/pointer p;int j；printf（%dn，g-adlistn.data）；）；/*访问出发点，输出顶点数据访问出发点，输出顶点数据*/visidi=1;/*然后变访问标志为然后变访问标志为1*/for（p=g-adlistn.first；p!=N

27、ULL；p=p-next）if（！（！visidp-vertex）DFSL（g，p-vertex）；）；算法分析算法分析 图中有图中有 n 个顶点，个顶点，e 条边。条边。如果用邻接表表示图，沿链可以找到某个顶点如果用邻接表表示图，沿链可以找到某个顶点 v 的所有邻接顶点的所有邻接顶点 w。由于总共有。由于总共有 2e 个边结点，个边结点，所以扫描边的时间为所以扫描边的时间为O(e)。而且对所有顶点递。而且对所有顶点递归访问归访问1次，所以遍历图的时间复杂性为次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需

28、时间为所有的边，所需时间为O(n)，则遍历图中所有，则遍历图中所有的顶点所需的时间为的顶点所需的时间为O(n2)。广度优先搜索广度优先搜索BFS(Breadth First Search)广度优先搜索的示例广度优先搜索的示例广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树 使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v v 之后，由之后，由之后，由之后，由 v v 出出出出发，依次访问发，依次访问发，依次访问发，依次访问 v v 的各个未曾被访问过的邻接顶点的各个未曾被访问过的邻接顶点的各个未曾

29、被访问过的邻接顶点的各个未曾被访问过的邻接顶点 w w1 1,w w2 2,w wt t，然后再顺序访问，然后再顺序访问，然后再顺序访问，然后再顺序访问 w w1 1,w w2 2,w wt t 的所有还未的所有还未的所有还未的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，被访问过的邻接顶点。再从这些访问过的顶点出发，被访问过的邻接顶点。再从这些访问过的顶点出发，被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，再访问它们的所有还未被访问过的邻接顶点，再访问它们的所有还未被访问过的邻接顶点，再访问它们的所有还未被访问过的邻接顶点，如如如如此做下去，直

30、到图中所有顶点都被访问到为止。此做下去，直到图中所有顶点都被访问到为止。此做下去，直到图中所有顶点都被访问到为止。此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的回退的情况。因此，广度优先搜索不是一个递归的回退

31、的情况。因此，广度优先搜索不是一个递归的回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。过程，其算法也不是递归的。过程，其算法也不是递归的。过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶，给被访问过的顶点加标记。点加标记。广度优先搜索算法广度优先搜索算法v

32、oid BFS（graph*g，int v）/*v是是出出发发顶顶点点的的序序号号，按按广广度度优优先先搜搜索索法法遍遍历图历图g，采用邻接矩阵存储结构，采用邻接矩阵存储结构，BFS遍历遍历*/int j，n；seqqueue q；/*假设采用顺序队列，定义顺序队列类型变量假设采用顺序队列，定义顺序队列类型变量q*/n=g-n；init_seqqueue（q）；）；/*队列初始化队列初始化*/printf(“访问出发点访问出发点%d”,v)；/*访问出发点，假设为输出顶点序号访问出发点，假设为输出顶点序号*/visidv=1；/*置访问标志为置访问标志为1，表示此点已访问过，表示此点已访问过*

33、/en_sqqueue（q，v）；）；/*顶点顶点v入队入队*/while(!empty_Seqqueue(q)/*队列空否？队列空否？*/de_ sqqueue（q，v）；）；/*队列非空时，出队队列非空时，出队*/for（j=l；jadges vj=l！visidj）printf(“访问顶点访问顶点%d”，j)；visidj=1；/*置顶点置顶点j被访问标志被访问标志*/en_seqqueue(q，j)；/*顶点顶点j入队入队*/void BFSL（graph*g，int v）/*采用邻接表存储结构，采用邻接表存储结构，BFS遍历遍历*/seqqueue q；/*假设采用顺序队列假设采用顺

34、序队列,定义顺序队列类型变量定义顺序队列类型变量q*/pointer p；init_seqqueue（q）；）；/*队列初始化队列初始化*/printf（“访问出发点访问出发点%d”,v）；）；/*访问出发点，假设为输出顶点序号访问出发点，假设为输出顶点序号*/visidv=1；/*置访问标志为置访问标志为1，表示此点已访问过，表示此点已访问过*/en_seqqueue（q，v）；）；/*顶点顶点v入队入队*/while（！（！empty _seqqueue（q）de_seqqueue（q，v）；）；p=g-adlistvfirst；While（p!=NULL）if（!visidp-verte

35、x）printf(%d”，p-vertex)；visidp-vertex=1；en_ seqqueue(q，p-vertex)；p=p-next；算法分析算法分析如果使用邻接表表示图，则循环的总时如果使用邻接表表示图，则循环的总时间代价为间代价为 d0+d1+dn-1=O(e)，其中，其中的的 di 是顶点是顶点 i 的度。的度。如果使用邻接矩阵，则对于每一个被访如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的问过的顶点，循环要检测矩阵中的 n 个个元素，总的时间代价为元素，总的时间代价为O(n2)。非连通图的遍历非连通图的遍历非连通图的遍历必须多次调用深度优先搜索或广度非连通

36、图的遍历必须多次调用深度优先搜索或广度非连通图的遍历必须多次调用深度优先搜索或广度非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以优先搜索算法，以优先搜索算法，以优先搜索算法，以DFSDFSDFSDFS为例：为例：为例：为例：TRAVER()/*遍历用邻接矩阵表示的非连通图遍历用邻接矩阵表示的非连通图*/int i;for (i=0;i n;i+)visitedi=FALSE;/*标志数组初始化标志数组初始化*/for (i=0;i n;i+)if (!visitedi)DFS(i);/*从顶点出发遍历一个连从顶点出发遍历一个连 通分量通分量*/printf(“comp endn”

37、);7.4 生成树生成树 连通图连通图G G的一个子图如果是一棵包含的一个子图如果是一棵包含G G的所的所有顶点的树，则该子图称为有顶点的树，则该子图称为G G的的生成树生成树。生成树是连通图的极小连通子图。所谓生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变出现一个回路；若去掉一条边，将会使之变成非连通图。成非连通图。生成树各边的权值总和称为生成树的权。生成树各边的权值总和称为生成树的权。权最小的生成树称为权最小的生成树称为最小生成树最小生成树 用不同的遍历图的方法，可以得到不同的用不同的遍历

38、图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同生成树；从不同的顶点出发，也可能得到不同的生成树。的生成树。按照生成树的定义，按照生成树的定义，n 个顶点的连通网络个顶点的连通网络的生成树有的生成树有 n 个顶点、个顶点、n-1 条边。条边。构造最小生成树，要解决以下二个问题构造最小生成树，要解决以下二个问题：尽可能选取权值小的边，但不能构成回路。尽可能选取权值小的边，但不能构成回路。选取选取n-1n-1条恰当的边以连接网的条恰当的边以连接网的 n n个顶点。个顶点。普里姆普里姆(Prim)算法算法普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络 N=V,E 中

39、的某一顶点中的某一顶点 u0 出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合将其顶点加入到生成树的顶点集合U中。以后每中。以后每一步从一个顶点在一步从一个顶点在U中，而另一个顶点不在中，而另一个顶点不在U中中的各条边中选择权值最小的边的各条边中选择权值最小的边(u,v),把它的顶点把它的顶点加入到集合加入到集合U中。如此继续下去，直到网络中的中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合所有顶点都加入到生成树顶点集合U中为止。中为止。用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程1234655

40、65173254612346551324PrimPrim算法的形式描述如下：算法的形式描述如下：置置置置T T为任意一个顶点；为任意一个顶点；为任意一个顶点；为任意一个顶点；求初始候选边集：求初始候选边集：求初始候选边集：求初始候选边集：whilewhile（T T中结点数中结点数中结点数中结点数n n）从候选边集中选取最短边（从候选边集中选取最短边（从候选边集中选取最短边（从候选边集中选取最短边（u u，v v）；）；）；）；将（将（将（将（u u，v v）及顶点）及顶点）及顶点）及顶点v v，扩充到，扩充到，扩充到，扩充到T T中；中；中；中；调整候选边集：调整候选边集：调整候选边集：调整

41、候选边集：PRIMPRIM算法算法voidprim（graph*g，intu）intv，k，j，min；for(v=1；vn；v+)if（v!=u）minedgev.end=u；minedgev.len=g-edgesvu；minedgeu.len=0；for（k=1；kn；k+）min=minedgek.len；v=k；for（j=1；jn；j+）if（minedgej.len0&minedgej.lenmin）min=minedgej.len；v=j；if（min=INTMAX）printf(“图不连通，无生成树！”)；return(0)；printf(“%d%d”,v,minedgev.

42、end)；minedgev.len=-minedgev.len；for(j1；jn；j+)if（g-edgesjvedgesjv；minedgej.end=v；算法分析算法分析 上述算法的初始化时间是上述算法的初始化时间是O(1)O(1)，k k循环循环中有两个循环语句，其时间大致为：中有两个循环语句，其时间大致为：令令O(1)O(1)为某一正常数为某一正常数C C，展开上述求和，展开上述求和公式可知其数量级仍是公式可知其数量级仍是 n n 的平方。所以，的平方。所以，整个算法的时间复杂性是整个算法的时间复杂性是O(nO(n2 2)克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法克鲁斯卡尔算法的

43、基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点，没有边的非连通个顶点，没有边的非连通图图 T=V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。当在当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的若该边的两个顶点落在不同的连通分量上，则将此边加入两个顶点落在不同的连通分量上，则将此边加入到到 T 中；否则将此边舍去，重新选择一条权值最中；否则将此边舍去，重新选择一条权值最小的边。小的边。如此重复下去，直到所有顶点在同一个连通如此重复下去，直到所

44、有顶点在同一个连通分量上为止。分量上为止。用克鲁斯卡尔算法构造最小生成树的过程用克鲁斯卡尔算法构造最小生成树的过程123465565173254612346551324克鲁斯卡尔算法的形式描述克鲁斯卡尔算法的形式描述T=(V,)；While (T中所含边数中所含边数 0）i=parenti；returni；/*若无双亲（初始点），双亲运算结果为其自己*/intgetedge（edgetypeem，inte）/*找最短边，e为边数*/inti,j,min=0;for(i=1;i=e;i+)if(emi-1.lenmin)min=emi-1.len；returnmin；Kruskal算法算法 vo

45、idkruskal（edqetypeem，intn，inte）/*n为结点数，e为边数*/inti，p1，p2，m，i0；for（i=1；i=n；i+）/*初始结点为根，无双亲*/parenti=-1；/*以后用于累计结点个数，此初值不能置为0*/m=1；while（mp2）parentp2=parentp1parentp2；/*p2的双亲中累计结点总数（为负值）*/parentpl=p2；/*p1成为p2的孩子elseparentp1=parentp1parentp2;parentp2=p1;m+；printf(“%d%d%dn”，m，emi0.v1，emi0.v2)；算法分析算法分析用用K

46、ruskal算算法法构构造造最最小小生生成成树树的的时时间间复复杂杂度度为为O（eloge），与与网网中中边边的的数数目目e有有关关，因因此此，它它适用于求稀疏图的最小生成树。适用于求稀疏图的最小生成树。7.5 最短路径最短路径 最短路径问题：最短路径问题：如果从图中某一顶点如果从图中某一顶点(称为称为源点源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能的路径可能不止一条，如何找到一条路径，使得沿此不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。路径各边上的权值总和达到最小。问题解法问题解法 单源最短路径单源最短路径 Dijkstra算法算法 任意顶点对之间的最短

47、路径任意顶点对之间的最短路径 Floyd算法算法单源最短路径问题单源最短路径问题 问题的提出：问题的提出：给定一个带权有向图给定一个带权有向图G与源点与源点v，求从求从v到到G中其它顶点的最短路径。限定各边上中其它顶点的最短路径。限定各边上的权值大于或等于的权值大于或等于0。为求得这些最短路径，为求得这些最短路径，Dijkstra提出按路径长度提出按路径长度的递增次序，逐步产生最短路径的算法。首先的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从长度次短的一条最短路径，依次类推，直到从

48、顶点顶点v到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。举例说明举例说明DijkstraDijkstra逐步求解的过程逐步求解的过程逐步求解的过程逐步求解的过程10301020DijkstraDijkstra算法算法算法算法voiddijkstra（graph*G，intv，int*dist,int*path,char*S）inti,j,k,pre，min；for（i=l;in;i+）si=0；disti=G-adgesvi；pathi=V；sv=1；distv=0；for（i1；in；i+）min=INTMAX；for(j=1;jn；j+)if(！sj&distjm

49、in)mindistj;k=j;if(min=INTMAX)break;Sk=1；for（jl；jn；j+）if（！sj&distjdistk+G-adgeskj）distj=distk+G-adgeskj；Pathj=k;for（i=1；in；i+）printf(“顶点%d的最短路径为：%dn”，i，disti)；Prepathi；doprintf(“-%d”,pre)；pre=pathpre；while（pre！=v）；if(disti=INTMAX)printf(”无路径n”)；算法说明算法说明对于顶点对于顶点i i和和j j：1 1、首先，考虑从、首先，考虑从i i到到j j是否有以顶

50、点是否有以顶点1 1为中间为中间点的路径，：点的路径，：i i，1 1，j j，即考虑图中是否有，即考虑图中是否有边边和和，若有，则新路径，若有，则新路径i i，1 1，j j的长度是的长度是Ci1+C1jCi1+C1j，比较路径，比较路径i i，j j和和i i，1 1，j j，的长度，并以较短者为当前所，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不求得的最短路径，。该路径是中间点序号不大于大于1 1的最短路径。的最短路径。所有顶点对之间的最短路径所有顶点对之间的最短路径2 2、其次，考虑从、其次，考虑从i i到到j j是否包含顶点是否包含顶点2 2为中间为中间点的路径：