非线性数据结构图讲解课件

1、第03章非线性数据结构-图1图及其基本概念 图的存储结构 图的遍历 图的连通性及最小生成树2图的基本概念树与图:在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图:图G由两个集合V(G)和E(G)所组成，记作G=(V,E)。V(G)是图中顶点的非空有限集合；E(G)是图中边的有限集合。3图的基本概念有向图:如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。V(G1)= V1，V2，V3，V4E(G1)= ， 如其中弧，称V1为初始

2、点或弧之尾，V2为终端点或弧之头。无向图:如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。V(G2)= V1，V2，V3，V4 E(G2)= (V1, V2)，(V1, V3)，(V3, V4)，( V4, V1)注:在无向图中，(V1, V2)与(V2, V1)表示同一条边4图的基本概念子图:设有两个图GA和GB，且满足 V(GB) V(GA) ，E(GB) E(GA)则称GB是GA的子图。5图的基本概念带权图:在图的边或弧上加上一个相关联的数(权)，称为带权图或网。6图的基本概念路径:图中一个顶点的序列称路径。如v到v的路径为(V=Vi0，Vi1，

3、Vi2，Vin=V)，并且都属于集合E。路径上弧的数目称为该路径的长度。在无向图中，若每一对顶点之间都有路径，则称此图为连通图。在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。邻接点:在无向图中，如果边(u,v)E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。在有向图中，如果弧E，则v是u的邻结点。称u邻接到v，或顶点v邻接自顶点u。顶点的度:在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，记作ID(V)；以某顶点为弧尾的弧的数目称为此顶点的出度，记作OD(V)。该顶点的度则

4、是此顶点的入度与出度之和。7图的存储结构邻接矩阵表示法和邻接表表示法邻接矩阵：用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G =(V,E)是有n(n1)个顶点的图，则G的邻接矩阵A是一个具有下列性质的nn阶矩阵：若或8图的存储结构将顶点编号为1Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示： int adjmatrixvtxnumvtxnum；9无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。对无向图可考虑只存下三角(或上三角)

5、元素。对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。图的存储结构10图的存储结构网的邻接矩阵可定义为:其中Wij是边(Vi, Vj)或弧上的权值。若或11图的存储结构邻接表:邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，12为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：v

6、exdata和firstarc。图的存储结构邻接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。13邻接表的存储结构可以用C语言描述如下：#define VTXNUM n/*n为图中顶点个数的最大可能值*/struct arcnode int adjvex;float data;struct arcnode *nextarc;typedef struct arcnode ARCNODE;struct headnode int vexdata;ARCNODE *firstarc;adjlistVTXNUM;邻接表特别适合与表示结点数多但边数较少的图图的存储结构14有

7、向带权图及其邻接表图的存储结构15无向图及其邻接表 图的存储结构16在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。对一个图来说，邻接表不是唯一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。图的存储结构17图的遍历从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅被访问一次，这个过程就叫做图的遍历(traversing graph)。为避免同

8、一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visitedn，它的初值为“假”或者零，一旦访问了顶点Vi，便置visitedi为“真”或者为被访问时的次序号。通常有两种遍历图的方法，深度优先搜索和广度优先搜索。 18深度优先搜索图的深度优先搜索遍历(depth-first search)类似于树的先序遍历，是树的先序遍历的推广。深度优先搜索的基本思想是：首先访问图G的指定起始点V0；从V0出发，访问一个与V0邻接的顶点W1后，再从W1出发，访问与W1邻接且未被访问过的顶点W2。从W2出发，重复上述过程，直到遇到一个所有与之邻接的顶点均被访问过的顶点为止；

9、沿着刚才访问的次序，反向回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复前两步，直到所有被访问过的顶点的邻接点都已被访问过为止；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。图的遍历19深度优先搜索的访问序列为：V1V2V4V8V5V6V3V7图的遍历20图的遍历深度优先搜索的递归算法:#define VTXNUM n /*n为图中顶点个数的最大可能值*/struct arcnode int adjvex;float data;struct arcnode *nextarc;typedef struct arcnode

10、ARCNODE;struct headnode int vexdata;ARCNODE *firstarc;struct headnode GVTXNUM+1;int visitedVTXNUM+1;void dfs(struct headnode G,int v)ARCNODE *p; printf(“%d-”,Gv.vexdata); visitedv=1; p=Gv.firstarc; while(p!=NULL)/*当邻接点存在时*/ if(visitedp-adjvex=0) dfs(G,p-adjvex); p=p-nextarc;/*找下一邻接点*/ ;void traver(s

11、truct headnode G)int v; for(v=1;v=VTXNUM;v+) visitedv=0; for(v=1;v”,Gv.vexdata); visitedv=1; rear=(rear+1)%VTXNUM; queuerear=v;/*访问过的顶点进队列*/while(rear!=front) front=(front+1)% VTXNUM; v=queuefront; p=Gv.firstarc; while(p!=NULL)if(visitedp-adjvex=0) printf(“%d-”, Gp-adjvex.vexdata); visitedp-adjvex=1

12、; rear=(rear+1)% VTXNUM; queuerear=p-adjvex; p=p-nextarc; 25图邻接表的构造#include stdio.h#include stdlib.h#define VTXNUM n struct arcnode int adjvex; int data; struct arcnode *nextarc; ;typedef struct arcnode ARCNODE;struct headnode int vexdata; ARCNODE *firstarc; ;struct headnode *creatgp(int d,int n)/di

13、为顶点Vi的值 /*该算法要求按图中顶点编号的顺序依次输入（从后往前）每个顶点的所有后件位置编号与权值；当结束时附加一对结束符*/struct headnode *head;ARCNODE *p;int k,m;/m为顶点Vi的邻接点的位置int v;/v为顶点Vi的邻接点的权值head=(struct headnode *)malloc(n+1)*sizeof(struct headnode);for(k=1;kvexdata=dk; (head+k)-firstarc=NULL; printf(input linked list of %d:n,dk); scanf(%d,%d,&m,&v

14、); while(m0)/0为结束符 p=(ARCNODE *)malloc(sizeof(ARCNODE); p-adjvex=m;p-data=v; p-nextarc=(head+k)-firstarc; (head+k)-firstarc=p; scanf(%d,%d,&m,&v); return(head);26图的连通性及最小生成树对于无向图进行遍历时：若图G为连通图，仅需调用一次dfs或bfs，即从图中任一顶点出发，便可访遍图中所有的顶点；若图G为非连通图，则需多次调用dfs或bfs。每调用一次dfs或bfs得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶点加上所

15、有依附于这些顶点的边，便构成了非连通图的一个连通分量。27图的连通性及最小生成树进行深度优先搜索遍历，需三次调用dfs过程(分别从顶点A、D和G出发)得到的访问序列为：ALMBFC；DE；GIKH。28图的连通性及最小生成树生成树：若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所有的顶点加上遍历时经过的边所构成的子图，称为连通图的生成树。由深度优先搜索得到的生成树为深度优先生成树；由广度优先搜索得到的生成树为广度优先生成树。(a) 深度优先生成树；(b) 广度优先生成树29图的连通性及最小生成树深度优先生成树和广度优先生成树也可画为树的形式。对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。深度优先生成森林30有n个顶点的连通图，其生成树