《C语言数据结构第06讲图.ppt》由会员分享，可在线阅读，更多相关《C语言数据结构第06讲图.ppt（59页珍藏版）》请在三一文库上搜索。
1、实用数据结构基础,第7章 图,第7章 图,知 识 点 图的逻辑结构及基本术语 邻接矩阵和邻接表的存储结构和特点 深度优先搜索和广度优先搜索两种遍历算法 图的连通性和生成树的概念 最短路径的含义及求最短路径的算法,难 点 图的遍历 最小生成树 最短路径 要 求 熟练掌握以下内容： 图的存储结构 图的遍历算法 了解以下内容： 图的最小生成树和求最小生成树算法 带权有向图的最短路径问题,第7章 目录,7-1 图的定义和术语 7-2 图的存储表示 7-3 图的遍历 7-4 图的连通性 7-5 最短路径 小 结 实验7 图子系统 习题7,7-1 图的定义和术语,图（Graph）是一种比树形结构更复杂的非
2、线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后继。 7-1 图的定义和术语 7-1-1 图的定义 图（Graph）是由非空的顶点（Vertices）集合和一个描述顶点之间关系边（Edges）的有限集合组成的一种数据结构。可以用二元组定义为： G（V，E） 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。,图7-1 无向图G1,图7-2 有向图G2,G1=（V，E） Vv1,v2,v3,v4,v5； E(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)。 (vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称
3、为边。,G2=(V,E) V=v1,v2,v3,v4 E=, 表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。,7-1-2 图的相关术语 （1）无向图（Undigraph） 在一个图中，如果每条边都没有方向（如图7-1），则称该图为无向图。 （2）有向图（Digraph） 在一个图中，如果每条边都有方向（如图7-2），则称该图为有向图。 （3）无向完全图 在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n (n-1)/2条边。,（4）有向完全图 在一个有向图中，如果任意两顶点之间都有
4、方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n (n-1) 条弧。 （5）稠密图、稀疏图 我们称边数很多的图为稠密图；称边数很少的图为稀疏图。 （6）顶点的度 在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD (v)。,在有向图中： (a) 一个顶点拥有的弧头的数目，称为该顶点的入度， 记为ID (v)； (b) 一个顶点拥有的弧尾的数目，称为该顶点的出度， 记为OD (v)； (c) 一个顶点度等于顶点的入度+出度， 即：TD (v)=ID (v)OD (v)。 在图7-1的G1中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 T
5、D(v4)=2 TD(v5)=2 在图7-2的G2中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2,可以证明，对于具有n个顶点、e条边的图，顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系： （7）权 图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight）。,（8）网边（或弧）上带权的图称为网（Network）。 如图7-3所示，就是一个无向网。如果边是有方向的带权图，则就是一个有向网。,图7
6、-3 一个无向网示意,图7-3 一个无向网示意,（9）路径、路径长度 顶点vi到顶点vj之间的路径是指顶点序列vi,vi1,vi2, , vim,vj.。其中，（vi,vi1），(vi1,vi2)，, (vim,.vj)分别为图中的边。路径上边的数目称为路径长度。 在图7-1的无向图G1中，v1v4v3v5与v1v2v5是从顶点v1 到顶点v5 的两条路径，路径长度分别为3和2。 （10）回路、简单路径、简单回路 在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。 在图7-1中，前面提到的v1到v5的
7、两条路径都为简单路径。除起始点和终止点外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图7-2中的v1v3v4v1。,（11）子图 对于图G=（V，E），G=（V，E），若存在V是V的子集 ，E是E的子集 ，则称图G是G的一个子图。 图7-4示出了G1和G2的子图。,图7-4 图G1和G2的两个子图示意,(a) G1的子图 (b) G2的子图,图7-1 无向图G1,（12）连通图、连通分量 在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。图7-5 (a)中有两个连通分量，如图7
8、-5 (b)所示。,(a) 无向图G3 (b) G3的两个连通分量 图7-5 无向图及连通分量示意,（13）强连通图、强连通分量 对于有向图来说，若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。 图7-2中有两个强连通分量，分别是v1,v2,v3和v4，如图7-6所示。,（14）生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间
9、有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。n个顶点的生成树具有n-1条边。,V1,V3,V2,V4,图7-6 有向图G2的两个 强连通分量示意,7-1-3 图的基本操作 图的基本操作有： （1）CreatGraph（G）输入图G的顶点和边，建立图G的存储。 （2）DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历图G。 （3）BFSTtaverse（G，v）在图G中，从顶点v出发广度优先遍历图G。,图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需要进行的运算。 下面介绍几种常用的图的存储结构。,7-2 图的存储表示,邻接矩阵是表示顶点之间相邻关
10、系的矩阵。 假设图G（V，E）有n个顶点，即Vv0,v1,vn-1，则G的邻接矩阵是具有如下性质的n阶方阵： 1 若(vi,vj)或是E(G)中的边 Aij= 0 若(vi,vj)或不是E(G)中的边 若G是网，则邻接矩阵可定义为： wij 若(vi,vj)或是E(G)中的边 Aij= 0或 若(vi,vj)或不是E(G)中的边 其中，wij表示边(vi,vj)或上的权值（如图7-3）；表示一个计算机允许的、大于所有边上权值的数。,用邻接矩阵表示法如图7-7所示；用邻接矩阵表示法如图7-8所示。,图的邻接矩阵具有以下性质： （1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只
11、需存放上（或下）三角矩阵的元素即可。 （2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的度TD(vi)。 （3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。 （4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,图的邻接矩阵存储的描述如下： #define MAXLEN 10 typedef struct char vexsMAXLEN; i
12、nt edgesMAXLENMAXLEN; int n,e; MGraph;,建立一个图的邻接矩阵存储的算法如下： void CreateMGraph(MGraph *G) int i,j,k; char ch1,ch2; printf(“请输入顶点数和边数(输入格式为:顶点数,边数):n“); scanf(“%d,%d“,printf (“请输入每条边对应的两个顶点的序号(输入格式为:i,j):n“); for(k=0;ke;k+) getchar(); printf (“请输入第%d条边的顶点序号：“,k+1); scanf (“%c,%c“, ,7-2-2 邻接表 邻接表(Adjacen
13、cy List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。 在邻接表表示中有两种结点结构，如图7-9所示。 顶点域 边表头指针 邻接点域 指针域 顶点表 边表 图7-9 邻接矩阵表示的结点结构,一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成，另一种是边表结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网
14、的边表需再增设一个存储边上信息（如权值等）的域（info），网的边表结构如图7-10所示。 邻接点域 边上信息 指针域 图7-10 网的边表结构,图7-11给出无向图7-7对应的邻接表表示。,邻接表表示形式描述如下：,define MAXLEN 10 / 最大顶点数为10 typedef struct node / 边表结点 int adjvex; / 邻接点域 struct node * next; / 指向下一个邻接点的指针域 /若要表示边上信息，则应增加一个数据域info EdgeNode; typedef struct vnode / 顶点表结点 VertexType vertex;
15、/ 顶点域 EdgeNode * firstedge; / 边表头指针 VertexNode; typedef VertexNode AdjListMAXLEN; / AdjList是邻接表类型 typedef struct AdjList adjlist; / 接表 int n,e; / 顶点数和边数 ALGraph; / ALGraph是以邻接表方式存储的图类型,建立一个有向图的邻接表存储的算法如下： void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(“请输入顶点数和边数(输入格式为:顶点数,边数) ：n“);
16、scanf(“%d,%d“, ,若无向图中有n 个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏(en(n-1)/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。 在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；但在有向图中，第i个链表中的结点个数只是顶点vi的出度。如果要求入度，则必须遍历整个邻接表才能得到结果。有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接，以vi为弧头的弧的链表。例如图7-12所示为有向图G2（图7-2）的邻接表和逆邻接表。,在建立邻接表或逆
17、邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为O（n+e），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n*e）。,7-3 图的遍历,图的遍历（traversing graph）是指从图中的某一顶点出发，对图中的所有顶点访问一次，而且仅访问一次。图的遍历是图的一种基本操作。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面： （1）在图结构中，每一个结点的地位都是相同的，没有一个“自然”的首结点，图中任意一个顶点都可作为访问的起始结点。 （2）在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何访问图中
18、其余的连通分量。 （3）在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。 （4）在图中，一个顶点可以和其它多个顶点相连，当这个顶点访问过后，就要考虑如何选取下一个要访问的顶点。,7-3-1 深度优先搜索 深度优先搜索（Depth-Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。 假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v出发，首先访问此顶点，然后任选一个v的未被访问的邻接点w出发，继续进行深度优先搜索，直到图中所有和v路径相通的顶点都被访问到；若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，
19、重复上面的做法，直至图中所有的顶点都被访问。,图7-13 无向图G5,以图7-13的无向图G5为例，其深度优先搜索得到的顶点访问序列为：,v1 v2 v4 v8 v5 v3 v6 、 v7,显然，以上方法是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited0:n-1, ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。 从图的某一点v出发，递归地进行深度优先遍历的过程如下面算法所示。 void DFSTraverseM(MGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; / FALSE在
20、c语言中定义为0，以下同 for(i=0;in;i+) if (!visitedi) DFSM(G,i); ,void DFSM(MGraph *G,int i) int j; printf (“tt深度优先遍历结点: 结点%cn“,G-vexsi); visitedi=TRUE; / TRUE在c语言中定义为1，以下同 for (j=0;jn;j+) if (G-edgesij=1 在遍历时，对图中每个顶点至多调用一次DFSM 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维
21、数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2) ，其中n为图中顶点数。,当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e) 。,7-3-2广度优先搜索 广度优先搜索 遍历类似于树的按层次遍历。 假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问
22、，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,的顶点。,对图7-13无向图G5 进行广度优先搜索遍历，首先访问v1 和v1的邻接点v2和v3，然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6和v7，最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为： v1v2 v3 v4 v5 v6 v7 v8,和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺
23、次访问路径长度为2、3、的顶点，需附设队列以存储已被访问的路径长度为1、2、 的顶点。,图7-13 无向图G5,从图的某一点v出发，递归地进行广度优先遍历的过程如下面的算法所示。 void BFSTraverseM(MGraph *G) int i; for (i=0;in;i+) visitedi=FALSE; for (i=0;in;i+) if (!visitedi) BFSM(G,i); ,void BFSM(MGraph *G,int k) int i,j; CirQueue Q; InitQueue( ,图7-4 图的连通性,分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是
24、通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历的时间复杂度是相同的，两者不同之处仅仅在于对顶点访问的顺序不同。,判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树等问题。,7-4-1 无向图的连通分量和生成树 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。 例如，图7-14 (a)是一个非连通图G6，按
25、照图7-14 (b) 所示G3 的邻接表进行深度优先搜索遍历,图7-14(a) 非连通图 图7-14(b) G6的邻接表,两次调用DFS过程（即分别从顶点A 和D出发），得到的顶点访问序列为： A B F E C E 这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G3的两个连通分量。 因此，要想判定一个无向图是否为连通图，或有几个连通分量，就可设一个计数变量count，初始时取值为0，在深度优先搜索算法循环中，每调用一次DFS，就给count增1。这样，当整个算法结束时，依据count 的值，就可确定图的连通性了。 设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时
26、，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图。,按照7-1-2节的定义，它是连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。例如，图7-15(a)和(b)所示分别为图7-13连通图G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G) 中的边，实线为集合T(G)中的边。,图7-15(a) G5的深度优先生成树,图7-15(b) G5的广度优先生成树,对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图
27、7-16 (b) 所示为图7-16 (a)的深度优先生成森林，它由三棵深度优先生成树组成。,图7-16(a) 非连通无向图G7,图7-16(b) G7的深度优先生成树林,7-4-2 最小生成树 1最小生成树的基本概念 由生成树的定义可知，无向连通图的生成树不一定是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图7-17 (a)、(b)和(c)所示的均为图7-13的无向连通图G5的生成树。,图7-17 无向连通图G5的三棵生成树,（a）,（b）,（c）,可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何
28、，所有生成树中都有且仅有n-1条边。 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。 最小生成树的概念可以应用到许多实际问题中。例如有这样一个问题：以尽可能抵的总造价建造城市间的通讯网络，把十个城市联系在一起。在这十个城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间的距离不同而有不同的造价，可以构造一个通讯线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。,2常用的构造最小生成树的方法 （1）构造最小
29、生成树的Prim算法 假设G（V，E）为一连通网，顶点集V=v1，v2，vn，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为Uv1（假设构造最小生成树时，从顶点v1出发），集合T的初值为T。 Prim算法的基本思想：从所有uU，vVU的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到UV时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。 图7-18 (a)所示的一个网，按照Prim方法，从顶点A出发，该网的最小生成树的产生过程如图7
30、-18 (b)、(c)、(d)、(e)、(f)所示。,图7-18 Prim 算法构造最小生成树的过程示意图,（2）构造最小生成树的Kruskal算法 Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：首先选取全部的n个顶点，将其看成n个连通分量；然后按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。,图7-19 Kruskal 算法构造最小生成树的过程示意图,返 回,7-5 最短路径,最短路径问题是图的又一个比较典型的应
31、用问题。例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，问题是如何在城市A和城市B之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。 例如在图7-20中，设V1为源点，则从V1出发的路径有（括号里为路径长度）：,V1到V2的路径有条：V1V2(20)
32、 V1到V3的路径有条：V1V3(15),V1V2V3(55) V1到V4的路径有条：V1V2V4(30),V1V3V4(45),V1V2V3V4(85) V1到V5的路径有条：V1V2V3V5(65),V1V3V5(25) 选出V1到其它各顶点的最短路径，并按路径长度递增顺序排列如下： V1V3(15)，V1V2(20)，V1V3V5(25)，V1V2V4(30)。,图7-20 V1 出发的路径,从上面的序列中，可以看出一个规律：按路径长度递增顺序生成从源点到其它各顶点的最短路径时，当前正生成的最短路径上除终点外，其它顶点的最短路径已经生成。迪杰斯特拉算法正是根据此规律得到的。 迪杰斯特拉（
33、Dijkstra）算法的基本思想：设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。初始时S中仅有一个源点，T中含除源点外其余顶点，此时各顶点的当前最短长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中剩余顶点的当前最短路径长度，修改原则是：当v的最短路径长度与v到T中顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复以上过程，直到S中包含所有顶点。,图7-21 用迪杰斯特拉算法求有向图的最短路径过程,小 结,（1）图是一种复杂的数据结构，图中的每一个顶点都可以有多个直接前驱和多个直接后继，所以是
34、一种非线性的数据结构。 （2）因为图是由顶点的集合和顶点间边的集合组成，所以图的存储也包括顶点信息和边的信息两个方面。 （3）图的存储结构常用的有：邻接矩阵和邻接表等要求掌握。 （4）对于n个顶点的图来说，它的邻接矩阵是一个nn阶的方阵。邻接矩阵中的元素取值只能是0或1，若图为无向图，则矩阵一定是对称矩阵，所以可以采用压缩存储；若是网，则要存储的是权值。 （5）对于由n个顶点和e 条边的图，它的邻接表由n个单链表所组成。无向图的邻接表占用n+2e个存储单元；有向图的邻接表占用n+e个存储单元。,（6）图的遍历就是从图的某一顶点出发，访问图中每个顶点一次且仅一次。遍历的基本方法有深度优先搜索遍历
35、和广度优先搜索遍历两种。深度优先遍历类似于树的先序遍历；广度优先遍历类似于树的按层次遍历。 （7）取一个无向连通图的全部顶点和一部分边构成一个子图，若其中所有顶点仍是连通的，但各边不构成回路，这个子图称为原图的一个生成树，同一个图可以有多个不同的生成树。对于带权的图，其各条边权值之和为最小的生成树即最小生成树。求最小生成树的方法，得到最小生成树中边的次序也可能不同，但最小生成树的权值之和却相同。 （8）对于带权的有向图，求从某一顶点出发到其余各顶点的最短路径（所经过的有向边权值总和最小的路径）或求每一顶点之间的最短路径称为最短路径问题。,1实验目的 （1） 掌握图邻接矩阵的存储方法； （2）
36、掌握图深度优先编历的基本思想； （3） 掌握图广度优先编历的基本思想。 2实验内容 （1） 编写按键盘输入的数据建立图的邻接矩阵存储； （2） 编写图的深度优先编历程序； （3） 编写图的广度优先编历程序； （4） 设计一个选择式菜单形式如下：,实验7 图子系统,图子系统 * * 1-更新邻接矩阵 * * 2-深度优先遍历 * * 3-广度优先遍历 * * 0-退 出 * *,3操作举例 （1） 按下图建立图的邻接矩阵存储；,A,E,D,C,B,（2） 按提示输入：,建立一个有向图的邻接矩阵表示 请输入顶点数和边数(输入格式为:顶点数,边数): 5,7 请输入顶点信息(顶点号)每个顶点以回车作为结束: A B C D E 请输入每条边对应的两个顶点的序号(输入格式为:i,j): 请输入第1条边的顶点序号：A,B 请输入第2条边的顶点序号：A,D 请输入第3条边的顶点序号：B,C 请输入第4条边的顶点序号：C,A 请输入第5条边的顶点序号：D,B 请输入第6条边的顶点序号：D,E 请输入第7条边的顶点序号：E,C,已建立一个图的邻矩阵存储 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 （3） 再进行图的其它操作。,习题7,参见习题解答,返 回,