数据结构图2016分析.pptxVIP

第七章 图;7.1 图的概念;7.1 图的概念;7.1 图的概念;2）邻接、关联 无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)关联于顶点vi和顶点vj。 有向图中，对于任意两个顶点vi和顶点vj，若存在弧vi，vj，则称顶点vi邻接到顶点vj，顶点vj邻接于顶点vi，同时称弧vi，vj关联于顶点vi和顶点vj 。 ;7.1 图的概念;7.1 图的概念;7.1 图的概念;7.1 图的概念;7.1 图的概念;7.1 图的概念;7.1 图的概念;;7.1 图的概念;7.2 图的存储;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法;7.2.1 邻接矩阵表示法; ;7.2.1 邻接矩阵表示法;7.2.2 邻接表表示法;例1：无向图的邻接表;分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。;7.2.2 邻接表表示法;7.2.2 邻接表表示法;void CREATADJLIST(vexnode ga[ ], int n, int e) { int i,j,k; edgenode *s; for(i=0;in;i++) /*读入顶点信息*/ { ga[i].vertex=getchar(); ga[i].link=NULL; } ;7.2 图的存储;7.3 图的遍历;7.3.1 连通图的深度优先搜索遍历;7.3.1 连通图的深度优先搜索遍历;邻接矩阵中图的基本操作——深度优先遍历;7.3.1 连通图的深度优先搜索遍历;邻接表中图的基本操作——深度优先遍历;7.3.1 连通图的深度优先搜索遍历;7.3.2 连通图的广度优先搜索遍历;7.3.2 连通图的广度优先搜索遍历;邻接矩阵中图的基本操作——广度优先遍历;7.3.2 连通图的广度优先搜索遍历;邻接表中图的基本操作——广度优先遍历;7.3.2 连通图的广度优先搜索遍历;7.3.3 非连通图的遍历;int visited[n]; graph g; void TRAVER() { int i; for(i=0;in;i++) visited[i]=0; /*标志数组初始化*/ for (i=0; in; i++) if (visited[i]==0) { DFS (i); /*从顶点i出发遍历某一个连通分量*/ ptintf(“comp end\n”); } } ;7.4 生成树和最小生成树;7.4 生成树和最小生成树;7.4 生成树和???小生成树;7.4 生成树和最小生成树;7.4 生成树和最小生成树;（1）从V中任选一顶点u0，并置T为只含一个顶点的树： 即初始状态： U ={u0 }, TE={ }； （2）只要U≠V,就找出一条权值最小的边(u,v),且u∈U, v ∈V-U,将该条边(u,v)和不在T中的顶点v加入T中。 即： while(U ≠ V) { (u,v)=min{wuv, u∈U, v ∈V-U}; U=U+{v}; TE=TE+{(u,v)} } （3）直到把所有顶点加入T为止。;7.4 生成树和最小生成树;7.4 生成树和最小生成树;1;7.4 生成树和最小生成树;for(k=0;kn-1;k++) /*找n-1条边*/ { min=max; for(j=k;jn-1;j++) /*找最短边*/ if(T[j].lengthmin) { min=T[j].length; m=j;} e=T[m]; T[m]=T[k]; T[k]=e; /*交换*/ v=T[k].endvex; for(j=k+1;jn-1;j++) /*调整候选边*/ { d=dist[v-1][T[j].endvex-1];