第7章++图.ppt

DATA STRUCTURE 第7章 图 引言 图是另一种非线性结构，它比树形结构更复杂。 §1 基本概念 一、图的定义和术语 1. 定义：图由V(G)和E(G)组成，记为G＝(V，E)。 其中① V(G) 是图中顶点(Vertex)的非空有限集合； ② E(G) 是图中边(Edge)的有限集合。 2. 图的分类 (1) 2. 图的分类(2) 连通图: 任意两个顶点间都是相互可到达的无向图。 强连通图：任意两个顶点间都是相互可到达的有向图。 非连通图: 至少有两个顶点间是相互不可到达的图。 完全图：图中 n 个顶点与其它 n-1 个顶点之间都有边。 无向完全图：有 条边 有向完全图：有 条弧 3. 基本术语 (1) 路径：从一个顶点到达另一个顶点所经过的顶点序列。 (2) 路径长度：路径上所包含的边的数目。 (3) 简单路径：路径上除起点和终点外，其余顶点都不相同。 (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）强连通分量：有向图的极大强连通子图。 二、图的基本操作 图的创建 操作 图的遍历 §2 图的存储结构 图的结构较复杂，表示图的存储结构有多种形式，一般取决于具体的应用。 一．邻接矩阵(Adjacency Matrix) 1. 图的邻接矩阵 设图G＝(V，E)有n ≥ 1个顶点，则图Ｇ的邻接矩阵定义如下： A[i-1][j-1]= 1 若（vi，vj）?E(G)或 vi，vj?E(G) 0 反之 邻接矩阵特点： ⑴无向图的邻接矩阵必对称，故可压缩存储； ⑵无向图的邻接矩阵的第i 行(或列)非0元素个数正好是 第i 个顶点的度； ⑶有向图邻接矩阵的第i 行非0元素个数正好是第i个顶 点的出度，第i列非0元素个数正好是第i个顶点的入度。 注意：邻接矩阵并非图的顺序存储结构（图没有顺序存储结构），而是借助二维数组这一数据类型来表示图中元素间的相邻关系。 2. 网的邻接矩阵 A[i-1][j-1]= wij 若(vi,vj)或vi,vj?E(G)，且权值为wij 0或∞ 反之 其中 ∞表示计算机允许的最大值 3. 邻接矩阵数据类型定义 #define Max 20; /*最大顶点个数*/ typedef char vextype; /*顶点的数据类型*/ typedef int arctype; /*1,0或wij*/ typedef struct { vextype vexs[Max]; /*顶点向量*/ arctype arcs[Max][Max]; /*存放边*/ int vexnum,arcnum; } Mgraph; 4. 建立邻接矩阵算法 无向图 有向图 网 建立无向图邻接矩阵算法 creat_adjmatrix(Mgraph *g) { int n,i,j,v1,v2,data; printf(“ input numbers of vertex :”); scanf(“%