1、第第0303章章非线性数据结构非线性数据结构-图图2 图及其基本概念图及其基本概念 图的存储结构图的存储结构 图的遍历图的遍历 图的连通性及最小生成树图的连通性及最小生成树3图的基本概念图的基本概念 树与图树与图:在在树树中，每个结点只与上层的父结中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有点有联系，并可以与其下层的多个子结点有联系。在联系。在图图中，结点之间的联系是任意的，中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。每个结点都可以与其它的结点相联系。图图:图图G G由两个集合由两个集合V(G)V(G)和和E(G)E(G)所组成，记作所组成，记作G=(V,
2、E)G=(V,E)。V(G)V(G)是图中顶点的非空有限集合；是图中顶点的非空有限集合；E(G)E(G)是图中边的有限集合。是图中边的有限集合。4图的基本概念图的基本概念 有向图有向图:如果图中每条边都是顶点的有序对，即每条边都用如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为箭头表明了方向，则此图为有向图。有向图中的边也称为弧弧，用用尖括号尖括号括起一对顶点表示。括起一对顶点表示。V(G1)=V1，V2，V3，V4E(G1)=，如其中弧如其中弧，称，称V1为初始点或弧之尾，为初始点或弧之尾，V2为终端点或弧之头。为终端点或弧之头。无向图无向图:如
3、果图中每条边都是顶点的无序对，则称此图为无如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用向图。无向边用圆括号圆括号括起的两个相关顶点来表示。括起的两个相关顶点来表示。V(G2)=V1，V2，V3，V4 E(G2)=(V1,V2)，(V1,V3)，(V3,V4)，(V4,V1)注注:在无向图中，在无向图中，(V1,V2)与与(V2,V1)表示同一条边表示同一条边5图的基本概念图的基本概念 子图子图:设有两个图设有两个图G GA A和和G GB B，且满足，且满足 V(GV(GB B)V(G)V(GA A)，E(GE(GB B)E(G)E(GA A)则称则称G GB B是是G GA A
4、的子图。的子图。132112132132G3G3的子图6图的基本概念图的基本概念 带权图带权图:在图的边或弧上加上一个相关联在图的边或弧上加上一个相关联的数的数(权权)，称为，称为带权图带权图或或网网。7图的基本概念图的基本概念 路径路径:图中一个顶点的序列称路径。如图中一个顶点的序列称路径。如v v到到vv的路径为的路径为(V=V(V=Vi0i0，V Vi1i1，V Vi2i2，V Vinin=V)=V)，并且，并且V V 都属于集合都属于集合E E。路径上弧的数目称为该路径的长度。在。路径上弧的数目称为该路径的长度。在无向无向图图中，若每一对顶点之间都有路径，则称此图为中，若每一对顶点之间
5、都有路径，则称此图为连通图连通图。在。在有向图有向图中，若每一对顶点中，若每一对顶点u u和和v v之间都存在之间都存在v v到到u u及及u u到到v v的路径，的路径，则称此图为则称此图为强连通图强连通图。邻接点邻接点:在在无向图无向图中，如果边中，如果边(u,v)E(u,v)E，则，则u u和和v v互为邻结点，互为邻结点，即即u u是是v v的邻结点，的邻结点，v v也是也是u u的邻结点。在的邻结点。在有向图有向图中，如果弧中，如果弧u,vEE，则，则v v是是u u的邻结点。称的邻结点。称u u邻接到邻接到v v，或顶点，或顶点v v邻接自邻接自顶点顶点u u。顶点的度顶点的度:在
6、在无向图无向图中，顶点的度就是和该顶点相关联的边中，顶点的度就是和该顶点相关联的边的数目，记为的数目，记为TD(V)TD(V)。在。在有向图有向图中，以某顶点为弧头的弧的中，以某顶点为弧头的弧的数目，称为此顶点的数目，称为此顶点的入度入度，记作，记作ID(V)ID(V)；以某顶点为弧尾的；以某顶点为弧尾的弧的数目称为此顶点的弧的数目称为此顶点的出度出度，记作，记作OD(V)OD(V)。该顶点的度则是。该顶点的度则是此顶点的入度与出度之和。此顶点的入度与出度之和。8图的存储结构图的存储结构 邻接矩阵邻接矩阵表示法和表示法和邻接表邻接表表示法表示法 邻接矩阵：邻接矩阵：用一个一维数组存放图中所有顶
7、点的信息；用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息用一个二维数组来存放数据元素之间的关系的信息(即边即边或弧的集合或弧的集合E)E)。这个二维数组称之为。这个二维数组称之为邻接矩阵邻接矩阵。邻接矩阵邻接矩阵是表示顶点之间的邻接关系的矩阵。设是表示顶点之间的邻接关系的矩阵。设G=(V,E)是有是有n(n1)个顶点的图，则个顶点的图，则G的邻接矩阵的邻接矩阵A是是一个具有下列性质的一个具有下列性质的nn阶矩阵：阶矩阵：ijij1 (V,V)V,VE(G)Ai,j0 反之若或9图的存储结构图的存储结构 将顶点编号为将顶点编号为1 1VtxnumVtxnum，
8、设弧上或边上无权值，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：则图的存储结构可以简化为用一个二维数组表示：int adjmatrixvtxnumvtxnumint adjmatrixvtxnumvtxnum；0111100010011010A2010100A301010 无向图无向图的邻接矩阵是对称的，而的邻接矩阵是对称的，而有向图有向图的邻接矩的邻接矩阵不一定对称。对无向图可考虑只存下三角阵不一定对称。对无向图可考虑只存下三角(或上或上三角三角)元素。元素。对于对于无向图无向图，邻接矩阵第，邻接矩阵第i i行行(或第或第i i列列)的元素之的元素之和是顶点和是顶点V V
9、i i的度。的度。对于对于有向图有向图，邻接矩阵，邻接矩阵第第i i行行元素之和为顶点元素之和为顶点V Vi i的的出度出度；第第i i列列的元素之和为顶点的元素之和为顶点V Vi i的的入度入度。图的存储结构图的存储结构0111100010011010A2010100A301011图的存储结构图的存储结构 网的邻接矩阵可定义为网的邻接矩阵可定义为:ijijijW (V,V)V,VE(G)Ai,j 反之其中其中W Wijij是边是边(V(Vi i,V,Vj j)或弧或弧 V 上的权值。上的权值。若或12图的存储结构图的存储结构 邻接表邻接表:邻接表是一种顺序分配和链式分配相结合的存储结邻接表是
10、一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是构。它包括两个部分：一部分是链表链表；另一部分是；另一部分是向量向量。在邻接表中，对图中在邻接表中，对图中每个顶点建立一个单链表每个顶点建立一个单链表，第，第i i个单链个单链表中的结点包含了顶点表中的结点包含了顶点V Vi i的所有邻接顶点。每个结点由三的所有邻接顶点。每个结点由三个域组成：个域组成：adjvexadjvex、datadata和和nextarcnextarc，adjvexdatanextarc指向顶点Vi的下一邻接点的指针权值顶点Vi的邻接点在图中的位置13 为便于邻接表操作，在每个单链表上附设一个为便于邻接表操
11、作，在每个单链表上附设一个头结点，在头结点中有两个域：头结点，在头结点中有两个域：vexdatavexdata和和firstarcfirstarc。vexdata firstarc指向Vi的第一个邻接点的指针存储Vi的名字或有关信息图的存储结构图的存储结构 邻接表中将邻接表中将每个单链表的头结点以顺序结构的形每个单链表的头结点以顺序结构的形式存储式存储，以便能随机访问任一顶点的单链表。，以便能随机访问任一顶点的单链表。14 邻接表的存储结构可以用邻接表的存储结构可以用C C语言描述如下：语言描述如下：#define VTXNUM n#define VTXNUM n/*n n为图中顶点个数的最大
12、可能值为图中顶点个数的最大可能值*/struct arcnodestruct arcnode int adjvexint adjvex;float data;float data;struct arcnode struct arcnode*nextarcnextarc;typedef struct arcnode ARCNODEtypedef struct arcnode ARCNODE;struct headnodestruct headnode int vexdataint vexdata;ARCNODE ARCNODE*firstarcfirstarc;adjlistVTXNUMadjl
13、istVTXNUM;n邻接表特别适合与表示结点数多但边数较少的图邻接表特别适合与表示结点数多但边数较少的图图的存储结构图的存储结构15231231437ABCABC734(a)(b)有向带权图及其邻接表有向带权图及其邻接表图的存储结构图的存储结构231231437ABCABC734(a)(b)1642123123124(a)(b)3413412412343无向图及其邻接表无向图及其邻接表 图的存储结构图的存储结构42123123124(a)(b)341341241234317 在邻接表上容易找到任一顶点的第一个邻接点和下在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶
14、点一个邻接点，但要判定任意两个顶点(V(Vi i和和V Vj j)之间之间是否有边或弧相连，则需搜索第是否有边或弧相连，则需搜索第i i个或第个或第j j个链表，个链表，因此不及邻接矩阵方便。因此不及邻接矩阵方便。对一个图来说，邻接表不是唯一的，它取决于建立对一个图来说，邻接表不是唯一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。邻接表时，结点在每个单链表中的插入策略。对于有向图，其邻接表中第对于有向图，其邻接表中第i i个单链表的结点个数个单链表的结点个数就是此结点的就是此结点的出度出度；对于无向图，其邻接表中第；对于无向图，其邻接表中第i i个单链表的结点个数就是此结点的个单链表
15、的结点个数就是此结点的度度。图的存储结构图的存储结构18图的遍历图的遍历 从图中某一顶点出发访问图中其余的顶点，使每从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅被访问一次，这个过程就叫个顶点都被访问且仅被访问一次，这个过程就叫做图的遍历做图的遍历(traversing graph)(traversing graph)。为避免同一顶点被访问多次，在遍历图的过程中，为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅必须记下每个已访问过的顶点。为此，设一个辅助数组助数组visitednvisitedn，它的初值为，它的初值为“假假”或者零，或者零，
16、一旦访问了顶点一旦访问了顶点V Vi i，便置，便置visitedivisitedi为为“真真”或或者为被访问时的次序号。者为被访问时的次序号。通常有两种遍历图的方法，通常有两种遍历图的方法，深度优先搜索深度优先搜索和和广度广度优先搜索优先搜索。19 深度优先搜索深度优先搜索图的深度优先搜索遍历图的深度优先搜索遍历(depth-first(depth-first search)search)类似于树的先序遍历，是树的类似于树的先序遍历，是树的先序遍历先序遍历的推广。的推广。深度优先搜索深度优先搜索的基本思想是：的基本思想是：首先访问图首先访问图G G的指定起始点的指定起始点V V0 0；从从V
17、 V0 0出发，访问一个与出发，访问一个与V V0 0邻接的顶点邻接的顶点W W1 1后，再从后，再从W W1 1出发，出发，访问与访问与W W1 1邻接且未被访问过的顶点邻接且未被访问过的顶点W W2 2。从。从W W2 2出发，重复上出发，重复上述过程，直到遇到一个所有与之邻接的顶点均被访问过述过程，直到遇到一个所有与之邻接的顶点均被访问过的顶点为止；的顶点为止；沿着刚才访问的次序，反向回退到尚有未被访问过的邻沿着刚才访问的次序，反向回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复前两步，直到所有被接点的顶点，从该顶点出发，重复前两步，直到所有被访问过的顶点的邻接点都已被访问过为止；
18、若此时图中访问过的顶点的邻接点都已被访问过为止；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问作起始点，重复上述过程，直至图中所有顶点都被访问到为止。到为止。图的遍历图的遍历20深度优先搜索的访问序列为：深度优先搜索的访问序列为：V1V2V4V8V5V6V3V7V1V2V4V8V5V6V3V7图的遍历图的遍历21图的遍历图的遍历深度优先搜索的递归算法深度优先搜索的递归算法:#define VTXNUM#define VTXNUM n/n/*n n为图中顶点个为图中顶点个数的最大可能值数的
19、最大可能值*/struct arcnodestruct arcnode int adjvexint adjvex;float data;float data;struct arcnode struct arcnode*nextarcnextarc;typedef struct arcnodetypedef struct arcnode ARCNODE;ARCNODE;struct headnodestruct headnode int vexdataint vexdata;ARCNODE ARCNODE*firstarcfirstarc;struct headnodestruct headno
20、de GVTXNUM+1;GVTXNUM+1;intint visitedVTXNUM+1;visitedVTXNUM+1;void dfs(struct headnode G,intvoid dfs(struct headnode G,int v)v)ARCNODE ARCNODE*p;p;printf(“%d-”,Gv.vexdata printf(“%d-”,Gv.vexdata););visitedv=1;visitedv=1;p=Gv.firstarc p=Gv.firstarc;while(p!=NULL)/while(p!=NULL)/*当邻接点存在时当邻接点存在时*/if(vi
21、sitedp-adjvex if(visitedp-adjvex=0)=0)dfs(G,p-adjvex dfs(G,p-adjvex););p=p-nextarc p=p-nextarc;/;/*找下一邻接点找下一邻接点*/;void traver(struct headnodevoid traver(struct headnode G)G)intint v;v;for(v=1;v=VTXNUM;v for(v=1;v=VTXNUM;v+)+)visitedv=0;visitedv=0;for(v=1;v=VTXNUM;v for(v=1;v”,Gv.vexdata printf(“%d-”
22、,Gv.vexdata););visitedv=1;visitedv=1;rear=(rear+1)%VTXNUM;rear=(rear+1)%VTXNUM;queuerear=v;queuerear=v;/*访问过的顶点进队列访问过的顶点进队列*/while(rear!=front)while(rear!=front)front=(front+1)%VTXNUM;front=(front+1)%VTXNUM;v=queuefront;v=queuefront;p=Gv.firstarc p=Gv.firstarc;while(p!=NULL)while(p!=NULL)if(visitedp
23、-adjvexif(visitedp-adjvex=0)=0)printf(“%d printf(“%d-”,-”,Gp-adjvex.vexdata Gp-adjvex.vexdata););visitedp-adjvex visitedp-adjvex=1;=1;rear=(rear+1)%VTXNUM;rear=(rear+1)%VTXNUM;queuerear=p-adjvex queuerear=p-adjvex;p=p-nextarc p=p-nextarc;26图邻接表的构造图邻接表的构造#include stdio.h#include stdio.h#include stdli
24、b.h#include stdlib.h#define VTXNUM#define VTXNUM n n struct arcnodestruct arcnode int adjvex int adjvex;int int data;data;struct arcnode struct arcnode*nextarcnextarc;typedef struct arcnodetypedef struct arcnode ARCNODE;ARCNODE;struct headnodestruct headnode int vexdata int vexdata;ARCNODE ARCNODE*f
25、irstarcfirstarc;struct headnode struct headnode*creatgp(int creatgp(int d,intd,int n)n)/di/di为顶点为顶点ViVi的值的值 /*该算法要求按图中顶点编号的顺序依次输该算法要求按图中顶点编号的顺序依次输入（从后往前）每个顶点的所有后件位置编入（从后往前）每个顶点的所有后件位置编号与权值；当结束时附加一对结束符号与权值；当结束时附加一对结束符*/struct headnodestruct headnode *head;head;ARCNODE ARCNODE*p;p;intint k,m;k,m;/m m为
26、顶点为顶点ViVi的邻接点的位置的邻接点的位置intint v;v;/v v为顶点为顶点ViVi的邻接点的权值的邻接点的权值head=(struct headnode head=(struct headnode*)malloc(n+1)malloc(n+1)*sizeof(struct headnodesizeof(struct headnode););for(k=1;k=n;k+)for(k=1;kvexdata(head+k)-vexdata=dk;=dk;(head+k)-firstarc(head+k)-firstarc=NULL;=NULL;printf(input printf(i
27、nput linked list of linked list of%d:n,dk);%d:n,dk);scanf(%d,%d,&m,&v scanf(%d,%d,&m,&v););while(m0)while(m0)/0/0为结束符为结束符 p=(ARCNODE p=(ARCNODE*)malloc(sizeof(ARCNODE)malloc(sizeof(ARCNODE););p-adjvex p-adjvex=m;p-data=v;=m;p-data=v;p-nextarc=(head+k)-firstarc p-nextarc=(head+k)-firstarc;(head+k)-fi
28、rstarc (head+k)-firstarc=p;=p;scanf(%d,%d,&m,&v scanf(%d,%d,&m,&v););return(head);return(head);27图的连通性及最小生成树图的连通性及最小生成树 对于对于无向图无向图进行遍历时：进行遍历时：若图若图G G为为连通图连通图，仅需调用一次，仅需调用一次dfsdfs或或bfsbfs，即从，即从图中任一顶点出发，便可访遍图中所有的顶点；图中任一顶点出发，便可访遍图中所有的顶点；若图若图G G为为非连通图非连通图，则需多次调用，则需多次调用dfsdfs或或bfsbfs。每。每调用一次调用一次dfsdfs或或bf
29、sbfs得到的顶点集合恰为图中一个得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加连通分量的顶点集合，这些顶点集合中的顶点加上所有依附于这些顶点的边，便构成了非连通图上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。的一个连通分量。28图的连通性及最小生成树图的连通性及最小生成树 进行深度优先搜索遍历，需三次调用进行深度优先搜索遍历，需三次调用dfsdfs过程过程(分别从分别从顶点顶点A A、D D和和G G出发出发)得到的访问序列为：得到的访问序列为：ALMBFCALMBFC；DEDE；GIKHGIKH。29图的连通性及最小生成树图的连通性及最小生成树 生成树：生
30、成树：若图是连通图，从图中的某一个顶点出发进行遍历时，若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所有的可以系统地访问图中所有顶点，此时图中所有的顶点顶点加上加上遍历遍历时经过的边所时经过的边所构成的子图，称为连通图的生成树。构成的子图，称为连通图的生成树。由深度优先搜索得到的生成树为由深度优先搜索得到的生成树为深度优先生成树深度优先生成树；由广度优先；由广度优先搜索得到的生成树为搜索得到的生成树为广度优先生成树广度优先生成树。(a)(a)深度优先生成树；深度优先生成树；(b)(b)广度优先生成树广度优先生成树30图的连通性及最小生成树图的连通性及最小生
31、成树 深度优先生成树深度优先生成树和和广度优先生成树广度优先生成树也可画为树的形式。也可画为树的形式。对于非连通图，每个连通分量中的顶点集和遍历时走过对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。成非连通图的生成森林。深度优先生成森林深度优先生成森林31 有有n n个顶点的连通图，其个顶点的连通图，其生成树有生成树有n n1 1条边条边；生成树中；生成树中不含回路不含回路；生成树生成树不是唯一的不是唯一的，因为起点不同，访问的路径也不同。，因为起点不同，访问的路径也不同。最小
32、生成树：最小生成树：生成树各边上的代价之和，称为生成树的代价，生成树各边上的代价之和，称为生成树的代价，使代价最小的生成树，称为使代价最小的生成树，称为最小代价生成树最小代价生成树，简称最小生成树。，简称最小生成树。图的连通性及最小生成树图的连通性及最小生成树(a)(a)无向连通网无向连通网 (b)(b)最小生成树最小生成树32 构造最小生成树的原则：构造最小生成树的原则：尽可能选权值小的边，但不构成回路。尽可能选权值小的边，但不构成回路。在网中选在网中选n n1 1条边以连接网中的条边以连接网中的n n个顶点。个顶点。图的连通性及最小生成树图的连通性及最小生成树33第三章作业（第三章作业（2）P73:1315第三次实验第三次实验u1 1生成给定图的邻接表生成给定图的邻接表u2 2对其进行深度优先搜对其进行深度优先搜索和广度优先搜索索和广度优先搜索。
