1、数据结构图数据结构图9.1 9.1 图的根本概念图的根本概念9.1.1 9.1.1 图的定义图的定义 图图(Graph)G(Graph)G由两个集合由两个集合V(Vertex)V(Vertex)和和E(Edge)E(Edge)组成组成,记为记为G=(V,E),G=(V,E),其中其中V V是顶点是顶点的有限集合的有限集合,记为记为V(G),EV(G),E是连接是连接V V中两个不同中两个不同顶点顶点(顶点对顶点对)的边的有限集合的边的有限集合,记为记为E(G)E(G)。9.1 图的根本概念 在图在图G中中,如果代表边的顶点对是无序的如果代表边的顶点对是无序的,那么称那么称G为为无向图无向图,无
2、向图中代表边的无序顶点对通常用圆括号括无向图中代表边的无序顶点对通常用圆括号括起来起来,用以表示一条无向边。用以表示一条无向边。如果表示边的顶点对是有序的如果表示边的顶点对是有序的,那么称那么称G为有向图为有向图,在有在有向图中代表边的顶点对通常用尖括号括起来向图中代表边的顶点对通常用尖括号括起来。在图G 中,如果代表边的顶点对是无序的,那么称G 为9.1.2 9.1.2 图的根本术语图的根本术语 1.1.端点和邻接点端点和邻接点 在一个无向图中在一个无向图中,假假设存在一条边设存在一条边(vi,vj),(vi,vj),那么称那么称vivi和和vjvj为此边的两个端点为此边的两个端点,并称它们
3、并称它们互为邻接点。互为邻接点。在一个有向图中在一个有向图中,假设存假设存在一条边在一条边,那么称此边是顶点那么称此边是顶点vivi的一条出边的一条出边,同时也是顶点同时也是顶点vjvj的一的一条入边；称条入边；称vivi和和vjvj分别为此边的起始分别为此边的起始端点端点(简称为起点简称为起点)和终止端点和终止端点(简称简称终点终点)；称；称vivi和和vjvj互为邻接点。互为邻接点。1 3 0 2 4 1 3 0 2 4(a)(b)9.1.2 图的根本术语 2.顶点的度、入度和出度顶点的度、入度和出度 在无向图中在无向图中,顶点所具有的边的数目顶点所具有的边的数目称为该顶点的度。称为该顶点
4、的度。在有向图中在有向图中,以顶点以顶点vi为终点的入边为终点的入边的数目的数目,称为该顶点的入度。以顶点称为该顶点的入度。以顶点vi为为始点的出边的数目始点的出边的数目,称为该顶点的出度。称为该顶点的出度。一个顶点的入度与出度的和为该顶点的一个顶点的入度与出度的和为该顶点的度。度。假设一个图中有假设一个图中有n个顶点和个顶点和e条边条边,每个顶点的度为每个顶点的度为di(1in),那么有：那么有：1 3 0 2 4 1 3 0 2 4(a)(b)n1iid21e 2.顶点的度、入度和出度 3.完全图完全图 假设无向图中的每两个顶点之间都假设无向图中的每两个顶点之间都存在着一条边存在着一条边,
5、有向图中的每两个顶点有向图中的每两个顶点之间都存在着方向相反的两条边之间都存在着方向相反的两条边,那么那么称此图为完全图。称此图为完全图。显然显然,完全无向图包含有条边完全无向图包含有条边,完全完全有向图包含有有向图包含有n(n-1)条边。例如条边。例如,图图(a)所示的图是一个具有所示的图是一个具有4个顶点的个顶点的完全无向图完全无向图,共有共有6条边。图条边。图(b)所示所示的图是一个具有的图是一个具有4个顶点的完全有向个顶点的完全有向图图,共有共有12条边。条边。1 0 2 3 1 0 2 3(a)(b)3.完全图 4.稠密图、稀疏图稠密图、稀疏图 当一个图接近完全图时当一个图接近完全图
6、时,那么称那么称为稠密图。相反为稠密图。相反,当一个图含有较当一个图含有较少的边数少的边数(即当即当en(n-1)时时,那么那么称为稀疏图。称为稀疏图。5.子图子图 设 有 两 个 图设 有 两 个 图 G=(V,E)和和G=(V,E),假设假设V是是V的子集的子集,即即 VV,且且 E 是是 E 的 子 集的 子 集,即即EE,那么称那么称G是是G的子图。例的子图。例如图如图(b)是图是图(a)的子图的子图,而图而图(c)不是图不是图(a)的子图。的子图。1 3 0 2 4(a)(b)1 3 0 2 4 1 3 0 2 4(c)4.稠密图、稀疏图6.路径和路径长度路径和路径长度 在一个图在一
7、个图G=(V,E)中中,从顶点从顶点vi到顶点到顶点vj的一的一条路径是一个顶点序列条路径是一个顶点序列(vi,vi1,vi2,vim,vj),假假设此图设此图G是无向图是无向图,那么边那么边(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)属于属于E(G)；假 设 此 图 是 有 向 图；假 设 此 图 是 有 向 图,那 么那 么,属于属于E(G)。路径长度是指一条路径上经过的边的数路径长度是指一条路径上经过的边的数目。假设一条路径上除开始点和结束点可以目。假设一条路径上除开始点和结束点可以相同外相同外,其余顶点均不相同其余顶点均不相同,那么称此路径为那么称此路
8、径为简单路径。例如简单路径。例如,有图中有图中,(v0,v2,v1)就是一条就是一条简单路径简单路径,其长度为其长度为2。1 0 2 3 6.路径和路径长度 7.回路或环回路或环 假设一条路径上的开始点与结束点假设一条路径上的开始点与结束点为同一个顶点为同一个顶点,那么此路径被称为回路那么此路径被称为回路或环。开始点与结束点相同的简单路径或环。开始点与结束点相同的简单路径被称为简单回路或简单环。被称为简单回路或简单环。例如例如,右图中右图中,(v0,v2,v1,v0)就是一就是一条简单回路条简单回路,其长度为其长度为3。1 0 2 3 7.回路或环 8.连通、连通图和连通分量连通、连通图和连通
9、分量 在无向图在无向图G中中,假设从顶点假设从顶点vi到顶点到顶点vj有路径有路径,那么那么称称vi和和vj是连通的。是连通的。假设图假设图G中任意两个顶点都连通中任意两个顶点都连通,那么称那么称G为连为连通图通图,否那么称为非连通图。否那么称为非连通图。无向图无向图G中的极大连通子图称为中的极大连通子图称为G的连通分的连通分量。显然量。显然,任何连通图的连通分量只有一个任何连通图的连通分量只有一个,即本即本身身,而非连通图有多个连通分量。而非连通图有多个连通分量。8.连通、连通图和连通分量 9.强连通图和强连通分量强连通图和强连通分量 在有向图在有向图G中中,假设从顶点假设从顶点vi到顶到顶
10、点点vj有路径有路径,那么称从那么称从vi到到vj是连通的。是连通的。假设图假设图G中的任意两个顶点中的任意两个顶点vi和和vj都连通都连通,即从即从vi到到vj和从和从vj到到vi都存在路都存在路径径,那么称图那么称图G是强连通图。例如是强连通图。例如,右边两右边两个图都是强连通图。个图都是强连通图。有向图有向图G中的极大强连通子图称为中的极大强连通子图称为G的强连通分量。显然的强连通分量。显然,强连通图只有一个强连通图只有一个强连通分量强连通分量,即本身即本身,非强连通图有多个强非强连通图有多个强连通分量。连通分量。1 0 2 3（a）1 0 2（b）9.强连通图和强连通分量10.权和网权
11、和网 图中每一条边都可以附有一个对应的数值图中每一条边都可以附有一个对应的数值,这种这种与边相关的数值称为权。权可以表示从一个顶点到与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图另一个顶点的距离或花费的代价。边上带有权的图称为带权图称为带权图,也称作网。也称作网。1 0.权和网 例例9.1 有有n个顶点的有向强连通图最多需要多少条边？个顶点的有向强连通图最多需要多少条边？最少需要多最少需要多 少条边？少条边？答：有答：有n个顶点的有向强连通图最多有个顶点的有向强连通图最多有n(n-1)条条边边(构成一个有向完全图的情况构成一个有向完全图的情况)；最少有
12、；最少有n条边条边(n个顶点依次首尾相接构成一个环的情况个顶点依次首尾相接构成一个环的情况)。例9.1 有n 个顶点的有向强连通图最多需要多9.2 9.2 图的存储结构图的存储结构 9.2.1 9.2.1 邻接矩阵存储方法邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)G=(V,E)是具有是具有n(nn(n0)0)个顶点的图个顶点的图,顶点的顺序依次为顶点的顺序依次为(v0,v1,vn-1),(v0,v1,vn-1),那么那么G G的邻接矩阵的邻接矩阵A A是是n n阶方阵阶方阵,其定其定义如下：义如下：(1)(1)如果如果G G
13、是无向图是无向图,那么：那么：Aij=1:Aij=1:假设假设(vi,vj)E(G)0:(vi,vj)E(G)0:其他其他 (2)(2)如果如果G G是有向图是有向图,那么：那么：Aij=1:Aij=1:假设假设E(G)0:E(G)0:其他其他9.2 图的存储结构 9.2.1 邻接矩阵存储方法(3)如果如果G是带权无向图是带权无向图,那么：那么：Aij=wij:假设假设vivj且且(vi,vj)E(G):其他其他(4)如果如果G是带权有向图是带权有向图,那么：那么：Aij=wij:假设假设vivj且且E(G):其他其他(3)如果G 是带权无向图,那么：011011011111010011011
14、1010=1A 1 3 0 2 4 1 3 0 2 4(a)(b)0100100000110000110001010=2A数据结构图(共1 1 3 张)课件邻接矩阵的特点如下：邻接矩阵的特点如下：(1)图的邻接矩阵表示是惟一的。图的邻接矩阵表示是惟一的。(2)无向图的邻接矩阵一定是一个对称矩阵。因此无向图的邻接矩阵一定是一个对称矩阵。因此,按按照压缩存储的思想照压缩存储的思想,在具体存放邻接矩阵时只需存放上在具体存放邻接矩阵时只需存放上(或下或下)三角形阵的元素即可。三角形阵的元素即可。(3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵阵,因此因此
15、,当图的顶点较多时当图的顶点较多时,可以采用三元组表的方法存储可以采用三元组表的方法存储邻接矩阵。邻接矩阵。(4)对于无向图对于无向图,邻接矩阵的第邻接矩阵的第i行行(或第或第i列列)非零元素非零元素(或非或非元素元素)的个数正好是第的个数正好是第i个顶点个顶点vi的度。的度。邻接矩阵的特点如下：数据结构图(共1 1 3 张)课件邻接矩阵的数据类型定义如下：邻接矩阵的数据类型定义如下：#define MAXV typedef struct int no;/*顶点编号顶点编号*/InfoType info;/*顶点其他信息顶点其他信息*/VertexType;/*顶点类型顶点类型*/typede
16、f struct /*图的定义图的定义*/int edgesMAXVMAXV;/*邻接矩阵邻接矩阵*/int vexnum,arcnum;/*顶点数顶点数,弧数弧数*/VertexType vexsMAXV;/*存放顶点信息存放顶点信息*/MGraph;邻接矩阵的数据类型定义如下：9.2.2 9.2.2 邻接表存储方法邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中合的存储方法。在邻接表中,对图中每个顶点建立一个单链对图中每个顶点建立一个单链表表,第第i个单链表中的结点表示依附于顶点个单链表中的结点表示依附于顶
17、点vi的边的边(对有向图对有向图是以顶点是以顶点vi为尾的弧为尾的弧)。每个单链表上附设一个表头结。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：点。表结点和表头结点的结构如下：表结点表结点 表头结点表头结点advexnextarcinfodata9.2.2 邻接表存储方法a d v e x n e x t a r c i n f o 其中其中,表结点由三个域组成表结点由三个域组成,adjvex指示与顶点指示与顶点vi邻邻接的点在图中的位置接的点在图中的位置,nextarc指示下一条边或弧的结指示下一条边或弧的结点点,info存储与边或弧相关的信息存储与边或弧相关的信息,如权值等。
18、表头结点由如权值等。表头结点由两个域组成两个域组成,data存储顶点存储顶点vi的名称或其他信息的名称或其他信息,firstarc指向链表中第一个结点。指向链表中第一个结点。其中,表结点由三个域组成,a d j v e x 指示与 1 3 0 2 4 1 3 0 2 4(a)(b)0 1 2 3 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 1 2 3 0 3 3 4 3 v0 v1 v2 v3 v4(a)(b)数据结构图(共1 1 3 张)课件邻接表的特点如下：邻接表的特点如下：(1)邻接表表示不惟一。这是因为在每个顶点
19、对应的单链表邻接表表示不惟一。这是因为在每个顶点对应的单链表中中,各边结点的链接次序可以是任意的各边结点的链接次序可以是任意的,取决于建立邻接表的算取决于建立邻接表的算法以及边的输入次序。法以及边的输入次序。(2)对于有对于有n个顶点和个顶点和e条边的无向图条边的无向图,其邻接表有其邻接表有n个顶点个顶点结点和结点和2e个边结点。显然个边结点。显然,在总的边数小于在总的边数小于n(n-1)/2的情况下的情况下,邻接表比邻接矩阵要节省空间。邻接表比邻接矩阵要节省空间。(3)对于无向图对于无向图,邻接表的顶点邻接表的顶点vi对应的第对应的第i个链表的边结个链表的边结点数目正好是顶点点数目正好是顶点
20、vi的度。的度。(4)对于有向图对于有向图,邻接表的顶点邻接表的顶点vi对应的第对应的第i个链表的边结点个链表的边结点数目仅仅是数目仅仅是vi的出度。其入度为邻接表中所有的出度。其入度为邻接表中所有adjvex域值域值为为i的边结点数目。的边结点数目。邻接表的特点如下：邻接表存储结构的定义如下：邻接表存储结构的定义如下：typedef struct ANode /*弧的结点结构类型弧的结点结构类型*/int adjvex;/*该弧的终点位置该弧的终点位置*/struct ANode*nextarc;/*指向下一条弧的指针指向下一条弧的指针*/InfoType info;/*该弧的相关信息该弧的
21、相关信息*/ArcNode;typedef struct Vnode /*邻接表头结点的类型邻接表头结点的类型*/Vertex data;/*顶点信息顶点信息*/ArcNode*firstarc;/*指向第一条弧指向第一条弧*/VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型是邻接表类型*/typedef struct AdjList adjlist;/*邻接表邻接表*/int n,e;/*图中顶点数图中顶点数n和边数和边数e*/ALGraph;/*图的类型图的类型*/邻接表存储结构的定义如下：假设一条路径上的开始点与结束点为同一个顶点,那么此路径
22、被称为回路或环。例如,以下图表示某工程的AOE网。p=G-adjlistu.(2)对AOE网进行拓扑排序。广度优先搜索遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,vit,然后再按照vi1,vi2,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。vl(F)=vl(I)-c(a10)=16p=p-nextarc;找出关键活动的意义在于,可以适当地增加对关键活动的投资(人力、物力等),相应地减少对非关键活动的投资,从而减少关键活动的持续时间,缩短整个工程的工期。(2)对AOE网进行拓扑排
23、序。lowcostj=costkj;closestj=k;vl(A)=min(vl(B)-c(a1),vl(C)-c(a2),vl(D)-c(a3)=0,2,7=0其中,表结点由三个域组成,adjvex指示与顶点vi邻接的点在图中的位置,nextarc指示下一条边或弧的结点,info存储与边或弧相关的信息,如权值等。图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。n为图G的顶点个数,e为图G的边数。InfoType info;/*该弧的相关信息*/假设图G中的任意两个顶点vi和vj都连通,即从vi到vj和从vj到vi都存在路径,那么称图G是强连通图。例例9.2 给定一个具有给定一个
24、具有n个结点的无向图的邻接矩阵和邻接表。个结点的无向图的邻接矩阵和邻接表。(1)设计一个将邻接矩阵转换为邻接表的算法；设计一个将邻接矩阵转换为邻接表的算法；(2)设计一个将邻接表转换为邻接矩阵的算法；设计一个将邻接表转换为邻接矩阵的算法；(3)分析上述两个算法的时间复杂度。分析上述两个算法的时间复杂度。解：解：(1)在邻接矩阵上查找值不为在邻接矩阵上查找值不为0的元素的元素,找到这样的元素后找到这样的元素后创立一个表结点并在邻接表对应的单链表中采用前插法插入该结创立一个表结点并在邻接表对应的单链表中采用前插法插入该结点。算法如下：点。算法如下：假设一条路径上的开始点与结束点为同一个顶点,那么此
25、路径被称为void MatToList(MGraph g,ALGraph*&G)/*将邻接矩阵将邻接矩阵g转换成邻接表转换成邻接表G*/int i,j,n=g.vexnum;ArcNode*p;/*n为顶点数为顶点数*/G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgesij!=0)p=(ArcNode*)malloc(sizeof(ArcNode);/*创立结点创立结点*p*/p-adjvex=j;p-nextarc=G-adjlisti.firstarc;/*
26、将将*p链到链表后链到链表后*/G-adjlisti.firstarc=p;G-n=n;G-e=g.arcnum;v o i d Ma t T o L i s t(MG r a p h g,A L G r a p (2)在邻接表上查找相邻结点在邻接表上查找相邻结点,找到后修改相应邻接矩阵元素找到后修改相应邻接矩阵元素的值。算法如下：的值。算法如下：void ListToMat(ALGraph*G,MGraph&g)int i,j,n=G-n;ArcNode*p;for(i=0;iadjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=1;p=p-nex
27、tarc;g.vexnum=n;g.arcnum=G-e;(2)在邻接表上查找相邻结点,找到后修改相应邻接矩 (3)算法算法1的时间复杂度均为的时间复杂度均为O(n2)。算法。算法2的时的时间复杂度为间复杂度为O(n+e),其中其中e为图的边数。为图的边数。(3)算法1 的时间复杂度均为O(n 2)9.3 9.3 图的遍历图的遍历9.3.1 9.3.1 图的遍历的概念图的遍历的概念 从给定图中任意指定的顶点从给定图中任意指定的顶点(称为初始点称为初始点)出发出发,按照某种搜索方法沿着图的边访问图中的所按照某种搜索方法沿着图的边访问图中的所有顶点有顶点,使每个顶点仅被访问一次使每个顶点仅被访问一
28、次,这个过程称为这个过程称为图的遍历。如果给定图是连通的无向图或者是强图的遍历。如果给定图是连通的无向图或者是强连通的有向图连通的有向图,那么遍历过程一次就能完成那么遍历过程一次就能完成,并可并可按访问的先后顺序得到由该图所有顶点组成的一按访问的先后顺序得到由该图所有顶点组成的一个序列。个序列。根据搜索方法的不同根据搜索方法的不同,图的遍历方法有两种：图的遍历方法有两种：一种叫做深度优先搜索法一种叫做深度优先搜索法(DFS)(DFS)；另一种叫做广度优；另一种叫做广度优先搜索法先搜索法(BFS)(BFS)。9.3 图的遍历9.3.2 9.3.2 深度优先搜索遍历深度优先搜索遍历 深度优先搜索遍
29、历的过程是：从图中某个初始顶点深度优先搜索遍历的过程是：从图中某个初始顶点v出发出发,首先访问初始顶点首先访问初始顶点v,然后选择一个与顶点然后选择一个与顶点v相邻且没被访问相邻且没被访问过的顶点过的顶点w为初始顶点为初始顶点,再从再从w出发进行深度优先搜索出发进行深度优先搜索,直到图直到图中与当前顶点中与当前顶点v邻接的所有顶点都被访问过为止。显然邻接的所有顶点都被访问过为止。显然,这个这个遍历过程是个递归过程。遍历过程是个递归过程。以邻接表为存储结构的深度优先搜索遍历算法如下以邻接表为存储结构的深度优先搜索遍历算法如下(其其中中,v是初始顶点编号是初始顶点编号,visited是一个全局数组
30、是一个全局数组,初始时所有元初始时所有元素均为素均为0表示所有顶点尚未访问过表示所有顶点尚未访问过)：9.3.2 深度优先搜索遍历void DFS(ALGraph*G,int v)ArcNode*p;visitedv=1;/*置已访问标记置已访问标记*/printf(%d ,v);/*输出被访问顶点的编号输出被访问顶点的编号*/p=G-adjlistv.firstarc;/*p指向顶点指向顶点v的第一条弧的弧头结点的第一条弧的弧头结点*/while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);/*假设假设p-adjvex顶点未访问顶点未访问,递归访
31、问它递归访问它*/p=p-nextarc;/*p指向顶点指向顶点v的下一条弧的弧头结点的下一条弧的弧头结点*/v o i d D F S(A L G r a p h *G,i n t v)0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 1 3 0 2 4 例如例如,以上图的邻接表为例调用以上图的邻接表为例调用DFS()函函数数,假设初始顶点编号假设初始顶点编号v=2,给出调用给出调用DFS()的的执行过程执行过程,见教材。见教材。例如,以上图的邻接表为例调用D F S()函数,假设9.3.3 9.3.3 广度优先搜索遍历广度优先
32、搜索遍历 广度优先搜索遍历的过程是：首先访问初始点广度优先搜索遍历的过程是：首先访问初始点vi,接着访接着访问问vi的所有未被访问过的邻接点的所有未被访问过的邻接点vi1,vi2,vit,然后再按照然后再按照vi1,vi2,vit的次序的次序,访问每一个顶点的所有未被访问过的邻接访问每一个顶点的所有未被访问过的邻接点点,依次类推依次类推,直到图中所有和初始点直到图中所有和初始点vi有路径相通的顶点都有路径相通的顶点都被访问过为止。被访问过为止。以邻接表为存储结构以邻接表为存储结构,用广度优先搜索遍历图时用广度优先搜索遍历图时,需要使需要使用一个队列用一个队列,以类似于按层次遍历二叉树遍历图。对
33、应的算以类似于按层次遍历二叉树遍历图。对应的算法如下法如下(其中其中,v是初始顶点编号是初始顶点编号)：9.3.3 广度优先搜索遍历这里用深度优先遍历方法，先给visited数组为全局变量置初值0，然后从0顶点开始遍历该图。(3)如果G是带权无向图,那么：如果给定图是连通的无向图或者是强连通的有向图,那么遍历过程一次就能完成,并可按访问的先后顺序得到由该图所有顶点组成的一个序列。if(lowcostj!=0&lowcostjmin)只要计算出各项点的ve(v)和vl(v)的值,根据9.称vi和vj互为邻接点。int i;k+;/*生成边数增1*/课程之间的先后关系可用有向图表示：采用广度优先搜
34、索遍历非连通无向图的算法如下：void BFS(ALGraph*G,int v)ArcNode*p;int w,i;int queueMAXV,front=0,rear=0;/*定义循环队列定义循环队列*/int visitedMAXV;/*定义存放结点的访问标志的数组定义存放结点的访问标志的数组*/for(i=0;in;i+)visitedi=0;/*访问标志数组初始化访问标志数组初始化*/printf(%2d,v);/*输出被访问顶点的编号输出被访问顶点的编号*/visitedv=1;/*置已访问标记置已访问标记*/rear=(rear+1)%MAXV;queuerear=v;/*v进队进
35、队*/这里用深度优先遍历方法，先给v i s i t e d 数组为全局变while(front!=rear)/*假设队列不空时循环假设队列不空时循环*/front=(front+1)%MAXV;w=queuefront;/*出队并赋给出队并赋给w*/p=G-adjlistw.firstarc;/*找找w的第一个的邻接点的第一个的邻接点*/while(p!=NULL)if(visitedp-adjvex=0)printf(“%2d,p-adjvex);/*访问访问之之*/visitedp-adjvex=1;rear=(rear+1)%MAXV;/*该顶点进队该顶点进队*/queuerear=p
36、-adjvex;p=p-nextarc;/*找下一个邻接顶点找下一个邻接顶点*/printf(n);w h i l e (f r o n t!=r e a r)0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 1 3 0 2 4 例如例如,以上图的邻接表为例调用以上图的邻接表为例调用BFS()函数函数,假假设初始顶点编号设初始顶点编号v=2,给出调用给出调用BFS()的执行的执行过程过程,见教材。见教材。例如,以上图的邻接表为例调用B F S()函数,假设初始顶点编号9.3.4 9.3.4 非连通图的遍历非连通图的遍历 对于无向图
37、来说对于无向图来说,假设无向图是连通图假设无向图是连通图,那么一那么一次遍历能够访问到图中的所有顶点；次遍历能够访问到图中的所有顶点；但假设无向图是非连通图但假设无向图是非连通图,那么只能访问到初始点所那么只能访问到初始点所在连通分量中的所有顶点在连通分量中的所有顶点,其他连通分量中的顶点是不可能访其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点问到的。为此需要从其他每个连通分量中选择初始点,分别进分别进行遍历行遍历,才能够访问到图中的所有顶点；才能够访问到图中的所有顶点；9.3.4 非连通图的遍历 对于有向图来说对于有向图来说,假设从初始点到图中的每个顶点假设从初
38、始点到图中的每个顶点都有路径都有路径,那么能够访问到图中的所有顶点；否那么不那么能够访问到图中的所有顶点；否那么不能访问到所有顶点能访问到所有顶点,为此同样需要再选初始点为此同样需要再选初始点,继续进行继续进行遍历遍历,直到图中的所有顶点都被访问过为止。直到图中的所有顶点都被访问过为止。对于有向图来说,假设从初始点到图中的每个顶点都采用深度优先搜索遍历非连通无向图的算法如下：采用深度优先搜索遍历非连通无向图的算法如下：DFS1(ALGraph*g)int i;for(i=0;in;i+)/*遍历所有未访问过的顶点遍历所有未访问过的顶点*/if(visitedi=0)DFS(g,i);采用深度优
39、先搜索遍历非连通无向图的算法如下：采用广度优先搜索遍历非连通无向图的算法如下采用广度优先搜索遍历非连通无向图的算法如下：BFS1(ALGraph*g)int i;for(i=0;in;i+)/*遍历所有未访问过的顶点遍历所有未访问过的顶点*/if(visitedi=0)BFS(g,i);采用广度优先搜索遍历非连通无向图的算法如下：9.3.5 9.3.5 图遍历的应用图遍历的应用 例 假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。假设连通那么返回1；否那么返回0。解：采用遍历方式判断无向图G是否连通。这里用深度优先遍历方法，先给visited数组为全局变量置初值0，然后从0顶点开始
40、遍历该图。在一次遍历之后，假设所有顶点i的visitedi均为1，那么该图是连通的；否那么不连通。对应的算法如下：9.3.5 图遍历的应用 例 假设图G 采用邻接表 int Connect(ALGraph*G)/*判断无向图判断无向图G的连通性的连通性*/int i,flag=1;for(i=0;in;i+)/*visited数组置初值数组置初值*/visitedi=0;DFS(G,0);/*调用调用DSF算法算法,从顶点从顶点0开始深度优先遍历开始深度优先遍历*/for(i=0;in;i+)if(visitedi=0)flag=0;break;return flag;i n t C o n
41、n e c t(A L G r a p h *G)例例 假设图假设图G采用邻接表存储，设计一个算法，输出图采用邻接表存储，设计一个算法，输出图G中从顶点中从顶点u到到v的长度为的长度为l的所有简单路径。的所有简单路径。解：所谓简单路径是指路径上的顶点不重复。利用解：所谓简单路径是指路径上的顶点不重复。利用回溯的深度优先搜索方法。回溯的深度优先搜索方法。从顶点从顶点u开始，进行深度优先搜索，在搜索过程中，需要开始，进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个数组把当前的搜索线路记录下来。为此设立一个数组path保存走保存走过的路径，用过的路径，用d记录走过的路径长度
42、。假设当前扫描到的结点记录走过的路径长度。假设当前扫描到的结点u等于等于v且路径长度为且路径长度为l时，表示找到了一条路径，那么输出路时，表示找到了一条路径，那么输出路径径path。对应的算法如下：对应的算法如下：例 假设图G 采用邻接表存储，设计一个算法，输出图G 中从void PathAll(ALGraph*G,int u,int v,int l,int path,int d)/*d是到当前为止已走过的路径长度，调用时初值为是到当前为止已走过的路径长度，调用时初值为-1*/int m,i;ArcNode*p;visitedu=1;d+;/*路径长度增路径长度增1*/pathd=u;/*将当
43、前顶点添加到路径中将当前顶点添加到路径中*/if(u=v&d=l)/*输出一条路径输出一条路径*/printf();for(i=0;iadjlistu.firstarc;/*p指向指向u的第一条弧的弧头结点的第一条弧的弧头结点*/while(p!=NULL)m=p-adjvex;/*m为为u的邻接顶点的邻接顶点*/if(visitedm=0)/*假设顶点未标记访问假设顶点未标记访问,那么递归访问之那么递归访问之*/PathAll(G,m,v,l,path,d);p=p-nextarc/*找找u的下一个邻接顶点的下一个邻接顶点*/visitedu=0;/*恢复环境恢复环境*/v o i d P
44、a t h A l l(A L G r a p h *G,i n t u,void main()int pathMAXV,u=1,v=4,d=3,i,j;MGraph g;ALGraph*G;g.n=5;g.e=6;int AMAXVMAXV=0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,0 ;for(i=0;ig.n;i+)/*建立图建立图9.1(a)的邻接矩阵的邻接矩阵*/for(j=0;jg.n;j+)g.edgesij=Aij;MatToList(g,G);for(i=0;ig.n;i+)visitedi=0;printf(图图G:n)
45、;DispAdj(G);/*输出邻接表输出邻接表*/printf(从从%d到到%d的所有长度为的所有长度为%d路径路径:n,u,v,d);PathAll(G,u,v,d,path,-1);printf(n);v o i d m a i n()程序执行结果如下：程序执行结果如下：图图G:0:1 3 1:0 2 2:1 3 4 3:0 2 4 4:2 3从从1到到4的所有长度为的所有长度为3路径路径:1 0 3 4 1 2 3 4 13240程序执行结果如下：1 3 2 4 09.4 9.4 生成树和最小生成树生成树和最小生成树9.4.1 9.4.1 生成树的概念生成树的概念 一个连通图的生成树是
46、一个极小连通子图一个连通图的生成树是一个极小连通子图,它含有图中全部顶点它含有图中全部顶点,但只有构成一棵树的但只有构成一棵树的(n-1)(n-1)条边。条边。如果在一棵生成树上添加一条边如果在一棵生成树上添加一条边,必定构成必定构成一个环：因为这条边使得它依附的那两个顶点之间一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。一棵有有了第二条路径。一棵有n n个顶点的生成树个顶点的生成树(连通无连通无回路图回路图)有且仅有有且仅有(n-1)(n-1)条边条边,如果一个图有如果一个图有n n个顶点个顶点和小于和小于(n-1)(n-1)条边条边,那么是非连通图。如果它多于那么是非连通图。
47、如果它多于(n-(n-1)1)条边条边,那么一定有回路。但是那么一定有回路。但是,有有(n-1)(n-1)条边的图不条边的图不一定都是生成树。一定都是生成树。9.4 生成树和最小生成树数据结构图(共1 1 3 张)课件9.4.2 9.4.2 无向图的连通分量和生成树无向图的连通分量和生成树 在对无向图进行遍历时在对无向图进行遍历时,对于连通图对于连通图,仅需调用遍历仅需调用遍历过程过程(DFS(DFS或或BFS)BFS)一次一次,从图中任一顶点出发从图中任一顶点出发,便可以遍历图便可以遍历图中的各个顶点。对非连通图中的各个顶点。对非连通图,那么需屡次调用遍历过程那么需屡次调用遍历过程,每每次调
48、用得到的顶点集连同相关的边就构成图的一个连通分次调用得到的顶点集连同相关的边就构成图的一个连通分量。量。设设G=(V,E)G=(V,E)为连通图为连通图,那么从图中任一顶点出发那么从图中任一顶点出发遍历图时遍历图时,必定将必定将E(G)E(G)分成两个集合分成两个集合T T和和B,B,其中其中T T是遍历是遍历图过程中走过的边的集合图过程中走过的边的集合,B,B是剩余的边的集合：是剩余的边的集合：TB=,TB=E(G)TB=,TB=E(G)。显然。显然,G=(V,T),G=(V,T)是是G G的极小连通子的极小连通子图图,即即GG是是G G的一棵生成树。的一棵生成树。9.4.2 无向图的连通分
49、量和生成树 由深度优先遍历得到的生成树称为由深度优先遍历得到的生成树称为深度优先生成深度优先生成树树；由广度优先遍历得到的生成树称为广度优先生成树。；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的这样的生成树是由遍历时访问过的n个顶点和遍历时经历的个顶点和遍历时经历的n-1条边组成。条边组成。对于非连通图对于非连通图,每个连通分量中的顶点集和遍历每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树时走过的边一起构成一棵生成树,各个连通分量的生各个连通分量的生成树组成非连通图的生成森林。成树组成非连通图的生成森林。由深度优先遍历得到的生成树称为深度优先生成树；由
50、9.4.4 9.4.4 普里姆算法普里姆算法 普里姆普里姆(Prim)(Prim)算法是一种构造性算法。算法是一种构造性算法。假设假设G=(V,E)G=(V,E)是一个具有是一个具有n n个顶点的带权连通无向个顶点的带权连通无向图图,T=(U,TE),T=(U,TE)是是G G的最小生成树的最小生成树,其中其中U U是是T T的顶点集的顶点集,TE,TE是是T T的的边集边集,那么由那么由G G构造最小生成树构造最小生成树T T的步骤如下：的步骤如下：9.4.4 普里姆算法 (1)初始化初始化U=v0。v0到其他顶点的所有边为候选边；到其他顶点的所有边为候选边；(2)重复以下步骤重复以下步骤n
