数据结构(第二版) 郑泳 方风波 第七章 图新.pptVIP

第七章 图 知识教学目标 图的有关概念和存储结构 图的遍历方法 生成树的概念和最小生成树 最短路径的概念和求解 能力培养目标 图的邻接矩阵表示法和邻接表表示法 图的遍历方法的实现 最小生成树的实现 迪杰斯特拉算法的实现 7.1 图的基本概念 7.1.1 图的定义 图（Graph）：是一种数据结构，由二个集合V和E组成，记作G=（V，E）。其中V是数据元素（顶点）的非空有限集，E是V中二元关系（边edge）的集合。树是图的特例，而线性表是树的特例。 图的每条边都是有序顶点对（即边是有方向的），则此图称为有向图。 图的每条边都是无序顶点对，若有（u ,v）∈E，则必有（u ,v）∈E，即边是无方向的，则此图称为无向图。 7.1.2 图的基本术语 1. 度、入度、出度 2. 子图 3. 权 4. 连通图和强连通图 5. 连通分量和强连通分量 6. 路径、回路 7. 生成树 7.2 图的存储结构 7.2.1 邻接矩阵 1．邻接矩阵的存储形式及性质 设图G=（V，E），有n个顶点，则其所对应的邻接矩阵A是按如下定义的一个二维数组： 2．网的邻接矩阵 网的邻接矩阵可类似地定义为： 3．图的邻接矩阵数据类型描述及运算 图的邻接矩阵数据类型可描述如下： typedef struct { DataType V[n+1]; int arcs[n+1][n+1]; }Graph; 【算法7.1】 无向图邻接矩阵的建立算法。 void CreateAdj(Graph g) { int i,j,k，e,n; scanf(e,n); //输入图的边树和顶点树 for(k=1;k=n;k++) scanf(g.v[k]); //输入图顶点的信息 for(i=1;i=n;i++) for(j=1;j=n;j++) g.arcs[i][j]=0; for(k=1;k=e;k++) { scanf(i,j); //输入一条边 g.arcs[i][j]=1; g.arcs[j][i]=1; } } 【算法7.2】 有向图邻接矩阵的建立算法。 void CreateAdj(Graph g) { int i,j,k，e,n; scanf(e,n); //输入图的边树和顶点树 for(k=1;k=n;k++) scanf(g.v[k]); //输入图顶点的信息 for(i=1;i=n;i++) for(j=1;j=n;j++) g.arcs[i][j]=0; for(k=1;k=e;k++) { scanf(i,j); //输入一条边 g.arcs[j][i]=1; } } 7.2.2 邻接表 1. 邻接表的存储形式及性质 链表中结点的类型定义为： typedef struct node { int data; struct node *next; }NODE; 表头结点类型定义为： typedef struct tnode { int v; NODE *next; }TNODE; 7.3 图的遍历 7.3.1 深度优先有哪些信誉好的足球投注网站 1) 首先访问出发点vi，并将其访问标志记为已访问过，即设visited[i]=1； 2) 然后依次从vi出发有哪些信誉好的足球投注网站vi的每个邻接点w，若w未曾访问过，则以w为新的出发点继续进行深度优先有哪些信誉好的足球投注网站遍历，直至图中所有和源点vi有路径相通的顶点（也称为从源点可达的顶点）均已被访问为止。 3) 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 7.3.2 广度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站遍历可以定义为： 1) 首先访问出发点v，并将其访问标志记为已访问过，即设visited[i]=1； 2) 接着依次访问顶点v的所有邻接点w1，w2，…，wi； 3) 然后再依次访问顶点w1，w2，…，wi的所有邻接点。 4) 如此类推，直至图中所有的顶点都被访问到。 7.4 生成树 最小生成树 对于连通的带权图（连通网）G，其生成树也是带权的。此时，把生成树T中各边的权值总和称为该树的权。 将图G的所有生成树中权值最小的生成树称为G的最小生成树，最小生成树可记为MST。 1．普里姆（Prim）算法 2．克鲁斯卡尔（kruskal）算法 克鲁斯卡尔算法的基本思想为：将图中所有边按权值递增顺序排列，依次选取权值较小的边，但要求后面选择的边不能与前面选择的边构成回路，若构成回路，则放弃该条边，重复这个过程，n