第7章++图.ppt

《第7章++图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATASTRUCTURE第7章图引言图是另一种非线性结构，它比树形结构更复杂。ACBDEFGHIJKLM图与树的区别：树：层次关系，结点间一对多关系。图：顶点间多对多关系。线性表、树都看作是简单的图。图的应用十分广泛如通信线路、交通航线、工程进度计划、计算机网络等很多问题可用图来表示。§1基本概念一、图的定义和术语1.定义：图由V(G)和E(G)组成，记为G＝(V，E)。其中①V(G)是图中顶点(Vertex)的非空有限集合；②E(G)是图中边(Edge)的有限集合。G1=(V1,E1)其中V1={1,2,3,4

2、},E1={(1,2),(1,3),(2,3),(2,4)}G2=(V2,E2)其中V2={a,b,c},E2={,,,}图G2abc图G11234例如：2.图的分类(1)若(vi,vj)E(G)，则称：vi和vj互为邻接点或vi和vj邻接;边(vi,vj)依附于顶点vi和vj;或边(vi,vj)与顶点vi，vj相关联。若弧E(G)，则称:vi为弧尾(tail)或初始点;vj为弧头(head)或终端点(terminalnode);顶点vi邻接到顶点vj，顶点

3、vj邻接自顶点vi;弧与顶点vi，vj相关联。无向图：E(G)是无向边的集合。1234有向图：E(G)是有向边的集合。abc2.图的分类(2)连通图:任意两个顶点间都是相互可到达的无向图。强连通图：任意两个顶点间都是相互可到达的有向图。非连通图:至少有两个顶点间是相互不可到达的图。完全图：图中n个顶点与其它n-1个顶点之间都有边。无向完全图：有条边有向完全图：有条弧3.基本术语(1)路径：从一个顶点到达另一个顶点所经过的顶点序列。(2)路径长度：路径上所包含的边的数目。(3)简单路径：路径上除起点和终

4、点外，其余顶点都不相同。(4)回路或环：起点和终点相同的简单路径。(5)顶点的度：无向图：顶点v的度OD(v)=依附于顶点的边数。有向图：顶点v的度分为入度和出度。v的入度ID(v)=以顶点v为头的弧的数目；v的出度OD(v)=以v为尾的弧的数目；v的度D(v)＝ID(v)＋OD(v)问题：图中边的数目与各顶点的度之间的关系？3.基本术语（6）子图：设两个图和，如果且，则称是的子图。（7）网络（带权图）：每条边都附带权值的图。（8）连通分量：无向图的极大连通子图。（9）强连通分量：有向图的极大强连通子图。二、图的基

5、本操作图的创建操作图的遍历§2图的存储结构图的结构较复杂，表示图的存储结构有多种形式，一般取决于具体的应用。两种最为常用、最基本的存储结构图的存储结构：邻接矩阵邻接表十字链表多重邻接表边表一．邻接矩阵(AdjacencyMatrix)1.图的邻接矩阵设图G＝(V，E)有n≥1个顶点，则图Ｇ的邻接矩阵定义如下：A[i-1][j-1]=1若（vi，vj）E(G)或E(G)0反之邻接矩阵A1：邻接矩阵A2：例：图G11234图G2abc邻接矩阵特点：⑴无向图的邻接矩阵必对称，故可压缩存储；⑵无向图的邻接

6、矩阵的第i行(或列)非0元素个数正好是第i个顶点的度；⑶有向图邻接矩阵的第i行非0元素个数正好是第i个顶点的出度，第i列非0元素个数正好是第i个顶点的入度。注意：邻接矩阵并非图的顺序存储结构（图没有顺序存储结构），而是借助二维数组这一数据类型来表示图中元素间的相邻关系。2.网的邻接矩阵A[i-1][j-1]=wij若(vi,vj)或E(G)，且权值为wij0或∞反之其中∞表示计算机允许的最大值1235243例:3.邻接矩阵数据类型定义#defineMax20;/*最大顶点个数*/typedefcha

7、rvextype;/*顶点的数据类型*/typedefintarctype;/*1,0或wij*/typedefstruct{vextypevexs[Max];/*顶点向量*/arctypearcs[Max][Max];/*存放边*/intvexnum,arcnum;}Mgraph;4.建立邻接矩阵算法无向图有向图网建立无向图邻接矩阵算法creat_adjmatrix(Mgraph*g){intn,i,j,v1,v2,data;printf(“inputnumbersofvertex:”);scanf(“%d”,&

8、n);/*输入顶点数n>0*/g->vexnum=n;for(i=0;ivexs[i]=getchar();/*建立顶点向量*/for(i=0;iarcs[i][j]=0;/*初始化邻接矩阵*/while(1){printf(“v1v2(00exit):”);scanf(“%d%d”,&