数据结构-图课件

5.1图的基本概念图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。图的定义及相关术语图的定义：图G由两个集合V(G)和E(G)所组成，记作G=(V, E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。

(2)有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。有向图示例图中所示的G1为有向图，它由V(G1)和E(G1)组成。V(G1)={V1，V2，V3，V4}E(G1)={<V1,V2>，<V1,V3>，<V3,V4>，<V4,V1>}如其中弧<V1,V2>，称V1为初始点或弧之尾，V2为终端点或弧之头。(3)无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。如图所示的G2为无向图。V(G2)={V1，V2，V3，V4}E(G2)={(V1,V2)，(V1,V3)，(V3,V4)，(V4,V1)}注意，在无向图中，(V1,V2)与(V2,V1)表示同一条边。图3-23无向图示例(4)子图。设有两个图GA和GB，且满足

V(GB)V(GA)E(GB)E(GA)则称GB是GA的子图。如下图所示。

图与子图(5)带权图。在图的边或弧上加上一个相关联的数(权)，称为带权图或网。如下图所示。ABECF1597211132有向网无向网(6)完全图。假设图中有

n个顶点，e

条边，则含有e=n(n-1)/2

条边的无向图称作完全图；含有e=n(n-1)

条弧的有向图称作有向完全图。(7)稠密图与稀疏图。若图的边或弧的数目接近于相应完全图的边或弧的数目，则称之为稠密图，否则称为稀疏图。

(8)路径。在一个图中，如果从顶点V1出发，沿着一些边经过顶点V1，V2，…，Vn-1到达顶点Vn，则称顶点序列(V1，V2，…，Vn-1，Vn)为从V1到Vn的一条路径。路径上边(弧)的数目称为该路径的长度。例如：下图中，{A,B,C,F}的路径长度为3。ABECF(9)

简单路径：序列中顶点不重复出现的路径。(10)

简单回路：序列中第一个顶点和最后一个顶点相同的简单路径。(11)

连通图：在无向图中，若每一对顶点之间都有路径，则称此图为连通图。(12)

连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。连通图BACDFEBACDFE非连通图(13)

强连通图：在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。(14)

强连通分量：各个强连通子图称作该有向图的强连通分量。强连通图ABECFABECF非强连通图(15)邻接点。在无向图中，如果边(u,v)∈E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。边(v,w)

与顶点u和v相关联。在有向图中，如果弧<u,v>∈E，则v是u的邻结点。称u邻接到v，或顶点v邻接自顶点u。(16)顶点的度。在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，记作ID(V)；以某顶点为弧尾的弧的数目称为此顶点的出度，记作OD(V)。该顶点的度则是此顶点的入度与出度之和。ACDFETD(B)=3，TD(A)=2

BABECFID(B)=2，OD(B)=1TD(B)=ID(B)+OD(B)=3建立和销毁图结构插入或删除顶点对邻接点的操作访问顶点遍历图插入和删除弧基本操作5.2图的存储结构图的存储结构一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示*三、有向图的十字链表存储表示*四、无向图的邻接多重表存储表示根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合；另一部分是顶点之间的联系，即边或弧的集合。可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n≥1)个顶点的图，则G的邻接矩阵A是一个n×n阶矩阵。Aij={0若(Vi,Vj)或<Vi,Vj>E(G)1若(Vi,Vj)或<Vi,Vj>E(G)一、图的数组(邻接矩阵)存储表示定义:矩阵的元素为BADFEC010010100011000101001001110000011100ABCDEFABCDEF有向图的邻接矩阵ABDCE0101000100000010010011000ABCDE在一般情况下，我们不关心图中顶点的情况，若将顶点编号为1～Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：

intadjmatrix[Vtxnum][Vtxnum]；特点无向图的邻接矩阵是对称的;

有向图的邻接矩阵不一定对称。对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。使用邻接矩阵法容易判断任意两个点的邻接关系。网的邻接矩阵可定义为若或其中Wij是边(Vi,Vj)或弧<Vi,Vj>上的权值。邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如下图所示。二、图的邻接表存储表示邻接表中表结点的结点结构顶点Vi的邻接点在图中的位置指向顶点Vi的下一邻接点的指针adjvexdatanextarc权值为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：vexdata和firstarc。如下图所示。邻接表中头结点的结点结构vexdatafirstarc指向顶点Vi的第一个邻接点的指针存储Vi的名字或有关信息为了利用顺序存储结构的随机访问特性，邻接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。邻接表的存储结构可以用C语言描述如下：

#defineVTXUNM n /*n为图中顶点个数的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc;}

adjlist[VTXUNM];BACDFE0A141B0452C353D254E015F123示例：无向图的邻接表有向图的邻接表ABDCE在有向图的邻接表中不易找到指向该顶点的弧，即难以确定某个顶点的入度BCDE1ABECD有向图的逆邻接表在有向图的逆邻接表中，每个顶点链接的是指向该顶点的弧。ABCDE303120012344有向带权图的邻接表在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。对一个图来说，邻接表不是惟一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。5.3图的遍历图的遍历从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先搜索广度优先搜索从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。一、深度优先搜索遍历图连通图的深度优先搜索遍历(用栈)W1、W2和W3

均为V0的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3

的子图。访问顶点V0

：for(W1、W2、W3)

若该邻接点Wi未被访问过，

则从它出发进行深度优先搜索遍历。V0w1SG1SG2SG3w2w3w2算法分析1.深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法：设立一个一维数组，用来记录每个顶点是否被访问过，即“访问标志visited[w]”。2.如何判别V0的邻接点是否被访问？显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例

连通图G的邻接表表示如下图所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。连通图G及其邻接表解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1→V2→V4→V8→V5→V6→V3→V7。下面给出dfs的递归算法。#defineVTXUNM n /*n为图中顶点个数的最大可能值*/structarcnode{ intadjvex; floatdata; structarcnode*nextarc;};typedefstructarcnodeARCNODE;structheadnode{ intvexdata; ARCNODE*firstarc;};structheadnodeG[VTXUNM+1];intvisited[VTXUNM+1];voiddfs(structheadnodeG[],intv){ ARCNODE*p; printf(''%d->'',G[v].vexdata); visited[v]=1; p=G[v].firstarc; while(p!=NULL){ /*当邻接点存在时*/ if(visited[p->adjvex]==0) dfs(G,p->adjvex);

p=p->nextarc; /*找下一邻接点*/ }}voidtraver(structheadnodeG[]){ intv; for(v=1;v<=VTXUNM;v++) visited[v]=0; for(v=1;v<=VTXUNM;v++) ifvisited[v]==0 dfs(G,v);}首先将图中每个顶点的访问标志设为FALSE,随后搜索图中每个顶点，如果未被访问过，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一个顶点。非连通图的深度优先搜索遍历需多次调用dfs算法。每调用一次dfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。非连通图的深度优先搜索遍历FFFFFFFFFTTTTTTTTTachdkfebg访问标志:访问次序:例如:012345678abchdekfgachkfedbg016234578二、广度优先搜索遍历图对连通图，从起始点v到其余各顶点必定存在路径。其中，vw1,vw2,vw8

的路径长度为1；vw7,vw3,vw5

的路径长度为2；vw6,vw4

的路径长度为3。Vw1w8w3w7w6w2w5w4w1vw2w7w6w3w8w5w4

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。连通图的广度优先搜索遍历例

对图示连通图G，从顶点V1出发，写出顶点的广度优先遍历序列。解：按广度优先搜索法从V1开始遍历，访问V1，然后访问V1的邻接点V2，V3，再依次访问V2和V3的未曾被访问的邻接点V4，V5及V6，V7，最后访问V4的邻接点V8。遍历序列如下：V1→V2→V3→V4→V5→V6→V7→V8连通图G及其邻接表注意，在bfs算法中，若W1在W2之前访问，则W1的邻接点也将在W2的邻接点之前访问，这里蕴涵了一个排队关系。在实现算法时，需设一个队列，每访问一个顶点后将其入队，然后将队头顶点出列，去访问与它邻接的所有顶点，重复上述过程，直至队空为止。下面给出bfs的相应算法。广度优先遍历算法。#defineVTXUNM nvoidbfs(structheadnodeG[],intv){intqueue[VTXUNM];int

rear=VTXUNM−1,front=VTXUNM−1;inti;ARCNODE*p;printf(''%d->'',G[v].vexdata); visited[v]=1; rear=(rear+1)%VTXUNM; queue[rear]=v; /*访问过的顶点进队列*/ while(rear!=front){ front=(front+1)%VTXUNM; v=queue[front]; p=G[v].firstarc; while(p!=NULL){ if(visited[p->adjvex]==0){ printf(''%d->'',G[p->adjvex].vexdata); visited[p->adjvex]=1; rear=(rear+1)%VTXUNM; queue[rear]=p->adjvex; } p=p->nextarc; }}}若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。非连通图的广度优先搜索遍历需多次调用bfs算法。每调用一次bfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。非连通图的广度优先搜索遍历5.4图的应用生成树：若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所有的顶点加上遍历时经过的边所构成的子图，称为连通图的生成树。并且称由深度优先搜索得到的生成树为深度优先生成树；由广度优先搜索得到的生成树为广度优先生成树。例如，下面的图示分别为连通图G的深度优先生成树和广度优先生成树。生成树的概念连通图G及其邻接表连通图G从V1出发的两种生成树(a)深度优先生成树；(b)广度优先生成树有n个顶点的连通图，其生成树有n−1条边；生成树中不含回路；生成树不是惟一的，因为起点不同，访问的路径也不同。对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。生成树可以解决一些实际问题。如要建n个城市之间的通信联络网，则连通n个城市只需n−1条线路。若以n个城市做图的顶点，n−1条线路做图的边，则该图的生成树就是可行的建造方案。每条线路建造需付出一定代价(相当于边上的权)，那么对n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，我们当然希望选择一个总耗费最小的生成树，即最小代价生成树。最小生