非线性数据结构

非线性数据结构(2)--图教学目标了解有关图的基本概念存储结构及实现遍历算法教学要求通过本单元学习，了解、掌握有关图:基本概念有向图、无向图、连通图、网存储结构及实现邻接矩阵、邻接表遍历及其它操作深度优先、广度优先遍历应用本单元涉及的内容第2章2.5图的逻辑结构及其运算2.6图类2.7图的遍历2.8树和图的基本应用P73~P90一、图及其基本概念图是一种较之线性表和树形结构更为复杂的非线性数据结构。图中各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。图的定义有向图、无向图图的基本概念邻接点、顶点、边、弧、顶点的度连通图、强连通图、连通分量网、权图结构图是对结点的前趋和后继个数不加限制的数据结构。有关图的理论，在“离散数学”的图论中有详细论述和证明。在DS中，只讨论图在计算机中的实现和操作。现实生活中，图的应用范围很广泛，涉及：电讯工程、电网调度、集成电路设计交通管理、工程管理、系统工程等领域图（Graph）的定义

图G=（V，E）其中：V={v1，v2，……,vn}是非空有穷的结点集合;E是顶点偶对的集合。例，图G1=（V，E）

V={v1，v2，v3，v4}E={（v1，v2），（v1，v3），（v2，v1），（v2，v3），（v2，v4），（v3，v1），（v3，v2），（v4，v2）

}oooov1v2v3v4G1有向图、无向图有向图（Digraph）

图G中顶点的偶对若是有向的，形成的图称有向图。如图G2所示。为示区别，其偶对用<vx,vy>表示。无向图（Undigraph）图G中顶点的偶对若是无向的，形成的图称为无向图，其偶对用（vx，vy）表示，如图G1所示。

G2=（V，E）

V={1，2，3，4}E={〈1，2〉，〈1，3〉

，〈3，4〉，〈4，1〉}1324G2边、弧边（Edge）顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可以看成是（Vx，Vy），也可以看成是（Vy，Vx）。弧（Arc）若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：〈Vx，Vy〉。弧是有序的，〈Vx，Vy〉表示从Vx到Vy。弧头（Head）弧的终点（TerminaLNode）称为弧头（方向前方）。弧尾（Tail）弧的起始点（InitialNode）称为弧尾（方向后方）。弧〈Vx，Vy〉表示为，VxVy弧尾弧头顶点、邻接点顶点（Vertex）图中的数据元素（结点）称为顶点。如图G1、G2中的Ｖ1、Ｖ2，1，2。邻接点（Adjacent）无向图中，若边（Ｖx，Ｖy）

E，则Ｖx、Ｖy互为邻接点。有向图中，若弧〈Ｖx，Ｖy〉E，则Ｖy是Ｖx的邻接点，反之，不是。VxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx的邻接点1324

G2oooov1v2v3v4G1顶点的度（Degree）无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（Indegree）。例如G2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（Outdegree）。例如G2中顶点1的出度为2。该顶点的度=入度+出度。例如，G2中顶点1的度=2+1=3。oooov1v2v3v4G11324

G2路径、长度路径（Path）在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，…,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：（V1V2V3）或（V1V3）；而G2中，1到4的路径为<134>。长度（Length）路径的长度是该路径上边或弧的数目。例如，G1中V1到V3的长度为1或2；而G2中1到4的长度为2。1324

G2oooov1v2v3v4G1连通图、强连通图、连通分量

12连通图（ConnectedGraph）

在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。连通分量（ConnectedComponent）

无向图中的极大连通子图称为连通分量。强连通图（StronglyConnectedGraph）在有向图中，若每对顶点Vx到Vy

间都存在Vx到Vy，及从Vy到Vx的路径，则称此图是强连通图。如图G4所示。345G321345G4子图、生成树子图

有两个图G和G1，若V1V，E1E，即V1中的顶点

G=（V，E）都属于V中的顶点，E1中的关系都

G1=（V1，E1）属于E中的关系，则称G1是G的子图。生成树

设G是一个连通图，G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树，则称为G的生成树。G的生成树不是唯一的。一棵有n个顶点的生成树，有且仅有n-1条边（弧）。网、权权（Weight）若图的边或弧带有与之相关的数，称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。网（Network）带权的图称为网。如G5为带权的网。V1V2V3V4G52357二、图的存储结构

前面在讨论树和线性表的存储结构时，用到两种存储结构：顺序表和链表。但图结构中的结点间没有确定的关系（没根），任意两点之间都可能存在联系，因此无法用顺序结构来存放图的顶点数据。但借助数组可以用来表示顶点之间的关系。实际上，在图的存储结构中，常用下面两种方法：邻接矩阵表示法邻接表表示法

1、邻接矩阵表示法根据图的定义可知，图的逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。有向图邻接矩阵定义

设图G=（V，E）是有n（n

1）个顶点的图，则G的邻接矩阵是具有下述性质的nxn的方阵，元素为：

1当〈Vi，Vj>E时

A[i，j]=0当〈Vi，Vj>E时例如，G2的邻接矩阵为：

G.nodes=1234A=G.Arc=

01100000000110004x41324

G2无向图邻接矩阵定义

设图G=（V，E）是有n（n

1）个顶点的图，则G的邻接矩阵是具有下述性质的对称阵，元素为：

1当(Vi，Vj）

E时

A[i，j]=A[j,i]=0当(Vi，Vj）

E时例如，G1的邻接矩阵为：G.nodes=

1234A=G.edge=

01101011110001004x4oooov1v2v3v4G1求图中顶点的度借助邻接矩阵,可以很容易地求出图中顶点的度。无向图邻接矩阵的第i行（或第i列）的元素之和是顶点Vi的度。例，G1中V2的度是3。有向图邻接矩阵第i行的元素之和为顶点Vi的出度；第j列的元素之和为顶点Vj的入度。例，G2中，V2的出度为0（第2行的元素之和为0），V1的入度为1（第1列的元素之和为1）。oooov1v2v3v4G1A=G.Arc=

01100000000110001324

G2网的邻接矩阵定义：

Wij若（Vi，Vj）或〈Vi，Vj〉EA[i，j]=

若（Vi，Vj）或〈Vi，Vj〉EG.nodes=V1V2V3V4A=G.Arc=532

74x4G5的邻接矩阵。V1V2V3V4G523572、邻接表表示法邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。在邻接表中，每个顶点由三个域组成：

每个单链表附设一个头结点，结构为：adjvexdatanextarc顶点Vi的邻接点与边或弧有关的权值指向Vi的下一个邻接点的指针Vexdatafirstarc指向Vi单链表的第一个结点存放Vi信息邻接表存储结构描述C语言描述

#defineVTXNUMnstructarcnode{intadjvex；

floatdata；

structarcnode*nextarc；

}；

typedefstructarcnodeARCNODE；

structheadnode{intdata；

ARCNODE*firstarc；

}adjlist[VTXNUM]；无向图G1的邻接表

V1V2V3V4^V3V2

V1V4^V3^V1V2^V2顶点Vi的度恰好就是第i个单链表中的结点数。oooov1v2v3v4G1

有向图G2的邻接表

123

4^2

3^4^1^在有向图中，第i个单链表中结点的个数是顶点Vi的出度；例如，V2的出度为0。为求入度，必须遍历整个邻接表。1324

G2逆邻接表为求顶点Vi的入度，对每个顶点Vi，建立一个链接以Vi为弧头的邻接点链表，称该表为逆邻接表。例如G2的逆邻接表为：

12344113^^^^显然逆邻接表的单链表中结点的个数就是顶点Vi的入度。1324

G2建立邻接表的算法操作步骤：step1

初始化邻接表的n个头结点，并读入一条弧或边的偶对〈i，j〉或（i，j）。step2

申请一个结点S的空间，将S插入到第i个单链表中；step3读下一条弧或边的偶对，若存在此弧或边，则继续执行step2；否则，结束。建立邻接表算法的程序createadjlist(structheadnodeG[],intn){inti,j,k;floatw;ARCNODE*s;for(k=1;k<=n;k++){scanf(“%d”,&G[k].data);G[k].firstarc=NULL;}scanf(“%d,%d,%f”,&i,&j,&w);while((i>=0&&i<n)&&(j>=0&&j<n)){s=(ARCNODDE*)malloc(sizeof(ARCNODE));s->adjvex=j;s->info=w;s->nextarc=G[i].firstarc;G[i].firstarc=s;scanf(“%d,%d,%f”,&i,&j,&w);}}三、图的遍历图的遍历（TraversingGraph）从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组visited[]，每访问一个顶点，便将其状态visited[i]置为“真”。常用的图的遍历方法有两种：深度优先遍历法广度优先遍历法深度优先遍历法深度优先遍历法类似于树的先根遍历法。算法思想：step1从图中某个顶点V0出发，并访问此顶点；step2

从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未访问过的邻接点为止。step3如果是连通图，从任一顶点V0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。深度优先遍历法举例遍历过程访问顶点所过边起始顶点V1V1V1的第1个邻接点V3V3（V1，V3）V3的第1个邻接点V1已访问，取下一个邻接点V5V5（V3，V5）V5的第1个邻接点V3已访问，取下一个邻接点V2V2（V5，V2）V2的两个邻接点均被访问，回退到V5，V5的邻接点均被访问，回退到V3，V3的邻接点均被访问，回退到V1，V1的另一个邻接点V4

未被访问V4（V1，V4）V4的第一个邻接点V1已被访问，另一个邻接点V6未被访问V6（V4，V6）V6的邻接点被访问，回退到V4V4的邻接点均被访问回退到V1，返回到出发点，遍历结束。V1V3V5V4V6G6V2示例遍历产生的结果深度优先遍历G6所走过的序列：

V1

V3

V5

V2

V4

V6所走过的边：（V1，V3），（V3，V5），（V5，V2），（V1，V4），（V4，V6）遍历生成树V1V3V5V2V4V6深度优先遍历算法程序(非递归)Traver_dfs(structheadnodeG[],intv){inti,stack[N],visited[N],top=-1;ARCNODE*p;for(i=0;i<N;i++)visited[I]=0;printf(“%d->”,G[v].data);visited[v]=1;top++;stack[top]=v;p=G[v].firstarc;while((top!=-1)||(p!=NULL)){while(p!=NULL){if(visited[p->adjvex])p=p->nextarc;else{printf(“%d->”,G[p->adjvex].data);visited[p->adjvex]=1;top++;stack[top]=p->adjvex;p=G[p->adjvex].firstarc;}if(top!=-1){v=stack[top];top--;p=G[v].firstarc;p=p->nextarc;}}}}广度优先遍历算法广度优先遍历法类似于树的按层次遍历的过程。即先访问第1个顶点所有邻接点后，再访问下一个顶点所有未被访问的邻接点。算法思想：step1

从图中某个顶点V0出发，并访问此顶点；step2从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依此从W1,W2,…,Wk出发访问各自未被访问的邻接点。step3重复step2，直到全部顶点都被访问为止。广度优先遍历法举例遍历过程访问顶点所过边起始顶点V1V1访问V1的未被访问过的所有邻接点V3,V2,V4（V1，V3）

(V1,V2)(V1,V4)访问V3的未被访问过的所有的邻接点V5（V3，V5）访问V2的未被访问过的所有的邻接点无访问V4的未被访问过的所有的邻接点V6(V4,V6)所有顶点已被访问,结束。V1V3V5V4V6G6V2示例遍历产生的结果广度优先遍历G6所走过的序列：

V1

V3

V2

V4

V5

V6所走过的边：

（V1，V3），（V1，V2），（V1，V4），（V3，V5），（V4，V6）遍历生成树V1V3V5V2V4V6四、图的操作图中顶点无序可言任一顶点都可以看作第一个顶点；任一顶点的邻接点间也无序可言；为操作方便，对图中顶点按人为意志给其排序；同样，也可以对某个顶点的所有邻接点进行排队，在这个队列中自然形成第一个或第K个邻接点。若某个顶点的邻接点个数大于K，则称第K+1个邻接点为第K个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为“空”。图的常用基本操作LOC_VERTEX（G，Vi）确定顶点Vi在G中的位置。GET_VERTEX（G，i）求图G中第i个顶点。FIRST_VERTEX（G，i）求图G中Vi的第1个邻接点。NEXT_ADJ(G,v,w)已知w为G中顶点v的第1个邻接点,求顶点w的下一个邻接点。INS_VERTEX(G,u)在图G中插入一个顶点u,为图G的第n+1个顶点。INS_ARC(G,v,w)在图G中插入一条从顶点v到顶点w的弧。DEL_VERTEX(G,Vi)删除图G中顶点Vi,以及与Vi相关联的边或弧。DEL_ARC(G,v,w)删除图G中从顶点v到顶点w的弧。五、图的应用最小生成树拓扑排序关键路径最短路径最小生成树该问题是构造连通图的最小代价生成树问题。一棵生成树的代价就是树上各边（弧）的代价之和。例如，若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n（n-1）/2条线路，选择哪n-1条线路，使费用最少。普里姆（Prim）算法克鲁斯卡尔（Kruskal）算法普里姆（Prim）算法假设N=（V，E）是连通图，TE是N上最小生成树中边的集合。从U={u0}（u0

V），TE=空开始；重复执行：在所有uU，vV-U的边（u，v）E中找一条代价最小的边（u0，v0）并入TE，同时u0并入U，直到U=V为止；此时TE中必有n-1条边，则T=（V，TE）为N的最小生成树。普里姆（Prim）算法举例12345687214357681110912U={1}，V-U={2，3，4，5，6，7，8}12212421473（1）（2）（3）(1)U={1,2},V-U={3,4,5,6,7,8}(2)U={1,2,4},V-U={3,5,6,7,8}(3)U={1,2,4,7},V-U={3,5,6,8}普里姆（Prim）算法举例(续)

47535（4）76（5）6（6）47638（7）83654722136589(4)U={1,2,4,7,5},V-U={3,6,8}(5)U={1,2,4,7,5,6},V-U={3,8}(6)U={1,2,4,7,5,6,3},V-U={8}(7)U={1,2,4,7,5,6,3,8),V-U={}43631克鲁斯卡尔（Kruskal）算法操作步骤:假设N=（V，E）是连通图取图中每个顶点自成一个连通分量在{E}中选择代价最小的边，若该边所依附的顶点落在T中不同的连通分量上，则将此边加入生成树T中；否则，舍去此边，再选择下一条代价最小的边。重复上述步，直到T中所有顶点都在同一连通分量上为止。克鲁斯卡尔（Kruskal）算法举例

1234561524663556251346123(4)1311462(3)123456

(1)13(2)11克鲁斯卡尔（Kruskal）算法举例(续）

123456

(5)1234123456152466355613256412435（6）拓扑排序研究一个有机整体中不同个体间的次序问题。例如课程间优先关系有向图问题。软件专业的课程优先关系：课程编号课程名称先决条件

C1程序设计基础无

C2离散数学C1C3汇编语言C1，C2

……C9高等数学无拓扑排序举例方法步骤在有向图中选一个没有前驱的顶点并输出;从图中删除该顶点和所有以它为尾的弧;重复前2步,直到全部顶点均输出为止。输出序列即为拓扑排序序列。拓扑排序序列不唯一。拓扑排序举例

C1C9C4C2C3C5C7C12C10C11C6C8C1C2C3C4C5C7C9C10C11C6C12C8C9C10C11C6C1C12C4C2C3C5C7C8关键路径研究的是在一个有机整体中不同个体间的次序问题。即研究的是工程进度及影响进度的关键因素问题。最短路径研究的是类似于交通调度一类的带权有向图问题。求路径最短或费用最省。六、二叉排序树的生成

对给定数列{a1，a2，…,an},根据二叉排序树特性,逐个将结点插入到二叉排序中。具体操作步骤：

step1a1是根结点；

step2

若ai<aj,且aj的左子为空,则将ai插入到aj的左子;若aj的左子非空,则继续寻找合适的插入位置。若aiaj，且aj的右子为空，则将ai插入到aj的右子；否则继续沿右子树寻找合适的插入位置；插入ai插入到aj的左子ai〈aj

插入到aj的右子aiaj

step3重复step2，直到所有结点插入完为止。二叉排序树算法二叉排序树结点结构：

structtree{charinfo；

structtree*left，*right；

}

算法描述:输入结点非空循环,若是第1个结点,令指针ROOT指向该结点。打印输出该二叉排序树；输入一个值，在该树中查找，若找到输出该结点值；否则，显示查找失败。二叉排序树生成算法

主程序框图

开始初始化输入结点数据！ROOTroot=create_btee（）create_btree()结束?NY打印该树查找指定结点Print_btree()Search_btree()

生成二叉排序树程序框图

Create_btree()开始r=0？Y申请结点空间r=0？显示“溢出”结束根结点的处理NYNr->left=0;r->right=0;r->info=info;非根结点info<r->info?Yt=r->leftt=r->rightN调用本函数root?返回YNr->left=0r->right=0root->left=r或root->right=r

查询二叉排序树算法框图

开始Search_btree()!rootY显示“空树”返回Nroot->info!=key循环key<root->info?root=root->leftroot=root->rightroot=0?NY查找成功,显示返回显示“失败”root!=0?循环结束?NY

打印算法框图

开始Print_btree()r=0?YN调用自身打印左子打印当前结点值调用自身打印右子返回

主程序Btree.C#include“stdio.h”

structtree{charinfo;structtree*left,*right;}main(){char*s,*c,key=‘’;structtree*create_btree(),*search_btree(),*root=0;do{printf(“Enteraletter:”);gets(s);if(!root)root=create_btree(root,root,*s);elsecreate_btrr(root,root,*s);}while(*s);

主程序Btree.C(续）

print_btree(root,0);key=‘1’;while(key){printf(“Enterakeytofind:”);scanf(“%s”,&c);key=search_btree(root,c);printf(“presstocontinue\n”);}}/*Btree.C结束*/

生成二叉排序树程序

structtreecreate_btree(root,r,info)structtree*root,*r;charinfo;{if(r==0){r=malloc(sizeof(structtree));if(r==0){printf(“Outofmemory\n”);exit(0);}r->left=0;r->right=0;r->info=info;if(root){if(info<root->info)root->left=r;elseroot->right=r;}else{r->right=0;r->left=0;}returnr;}/*if==0接下页*/生成二叉排序树程序（续）

if(info<r->info)create_btree(r,r->left,info);if(info>=r->info)create_btree(r,r->right,info);}/*create_btree(root,r,info)*/

structtree*search_btree(root,key)structtree*root;charkey;{if(!root){printf(“Emptubtree\n”);returnroot;}while(root->info!=key){if(key<root->info)root=root->left;elseroot=root->right;if(root==0){printf(“SearchFailure\n”);break;}}/*while(root->info!=key)*/查询二叉排序树程序

if(root!=0)

printf(“Successfulsearch\nkey=%c\n”,root->info);returnroot;}/**search_btree(root,key)*/查询二叉排序树程序（续）打印二叉排序树程序print_btree(r,l)structtree*r;intl;{inti;if(r==0)return;print_tree(r->left,l+1);for(i=0;i<l;i++)printf(“

“);printf(“%c\n”,r->info);print_btree(r->right,l+1);}程序输入输入：输出：

hbddperhbper

举例

对数列{10，18，3，4，9，13，25}，生成二叉排序树。

10

（1）1018（2）10318（3）103184（4）1034189（5）

（7）10394181325103491813（6）示例

平衡二叉排序树

在二叉排序树的动态生成过程中，由于数据本身的特性，将影响二叉排序树的性质，例如{3，5，7，9，20}这样的数列，生成的二叉排序树就是一棵单枝树。因此，在动态生成二叉排序树的过程中，要进行平衡化处理。平衡化处理就是在不影响二叉排序树特性的前题下，通过“旋转”处理，使该结点的平衡因子不大于2。旋转分：LL、RR、LR和RL

四种。357920LL平衡化处理

由于在A的左子树的左子树上插入结点，使A点失去平衡，需进行一次LL旋转（顺时针旋转）操作。程序实现为：

b=a.lca.lc=b.rcb.rc=aa.bf=0b.bf=0b为子树的新根ABCLLBCA示例示意为：RR平衡化处理

由于在A的右子树的右子树上插入结点，使A点失去平衡，需进行一次RR旋转（逆时针旋转）操作。程序实现为：

b=a.rca.rc=b.lcb.lc=aa.bf=0b.bf=0b为子树新根ABCRRBAC示例示意为：LR平衡化处理程序实现为：

b=a.lc、c=b.rc、a.lc=c.rcb.rc=c.lc、c.lc=b、c.rc=aABCCBAACB示例

由于在A的左子树的右子树上插入结点，使A点失去平衡，需进行一次LR旋转（两次旋转;先逆时针,再顺时针旋转）操作。示意为：RL平衡化处理

由于在A的右子树的左子树上插入结点，使A点失去平衡，需进行一次RL旋转（两次旋转;先顺时针,再逆时针旋转）操作。

ABCCABACB程序实现为：

b=a.rc、c=b.lc、a.rc=c.lcb.lc=c.rc、c.lc=a、c.rc=b

示意为：示例平衡化处理举例有数据序列{13,24,37,90,53}插入13,树是平衡的;插入24,树仍为平衡;插入37,树不再平衡,

执行RR旋转;插入90,树仍平衡;插入53,失去平衡,

执行RL旋转.13(1)1324(2)132437371324(3)24133790(4)241337905324133753902413533790(5)示例Huffman(哈夫曼）树及应用Huffman树的定义构造Huffman树Huffman编码Huffman编码的译码Huffman树的定义Huffman树也称为最优树，是一类带权路径最短的二叉树。树的带权路径长度定义为：

WPL=∑wklkk=1n

其中：

n是树中叶结点的个数

wi是第i个结点的权值

li是第i个结点的路径长度

Huffman树举例以下有三棵树：（a）（b）（c）abcdabcdacbd777555222444WPLa=7x2+5x2+2x2+4x2=36WPLb=7x3+5x3+2x1+4x2=46WPLc=

7x1+5x2+2x3+4x3=35√事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。应用举例由统计规律可知，考试成绩的分布符合正态分布：-110

分数0～5960～6970～7980～8990～100比例数0.050.150.400.30.10根据正态分布规律，在60～90之间的分数占85%，而不及格和优秀是少数。将百分制转换成五分制判定树比较：a<60?a<70?a<80?a<90?不及格

及格

中等

良好

优秀YYYYNNNNa<80?a<70?a<90?a<60?不及格

优秀

良好

中等

中等

及格不及格YYYNNNNYY(A)(B)若输入1万个数据，按A的判定过