数据库图(数据库)

第六章 图,6.1 图的定义和术语图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中： V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v),图G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),有向完备图n个顶点的有向图最大边数是n(n-1)无向完备图n个顶点的无向图最大边数是n(n-1)/2权与图的边或弧相关的数叫网带权的图叫子图如果图G(V,E)和图G(V,E),满足：VVEE 则称G为G的子图顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1<jn),路径长度沿路径边的数目或沿路径各边权值之和回路第一个顶点和最后一个顶点相同的路径叫简单路径序列中顶点不重复出现的路径叫简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫连通从顶点V到顶点W有一条路径，则说V和W是连通的连通图图中任意两个顶点都是连通的叫连通分量非连通图的每一个连通部分叫强连通图有向图中，如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是,路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1,连通图,强连通图,非连通图连通分量,6.2 图的存储结构多重链表,邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的邻接矩阵可定义为：,关联矩阵表示顶点与边的关联关系的矩阵定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵,特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中“1”的个数顶点Vi的入度是A中第i行中“-1”的个数,邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）,特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表,6.3 图的遍历深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,深度遍历：V1 V2 V4 V8 V3 V6 V7 V5,深度优先遍历算法递归算法,Ch6_1.c,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,void defarc(int xMM,int n,TD gs)int i,j; JD *w,*v; for(i=0;iadjvex=j;v=w;gsi.firstarc=w; else if (gsi.firstarc!=NULL ,void traver(TD g,int n) int i; static int visitedM; for(i=0;i<n;i+) visitedi=0; for(i=0;i<n;i+) if(visitedi=0) dfs(g,i,visited);,void dfs(TD g,int v,int visited) JD *w; int i; printf("%d ",v+1); visitedv=1; w=gv.firstarc; while(w!=NULL) i=w->adjvex; if(visitedi=0) dfs(g,i,visited); w=w->next; ,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V6 V7 V8 V5,广度优先遍历算法,Ch6_2.c,void traver(TD g,int n) int i; static int visitedM; for(i=0;i<n;i+) visitedi=0; for(i=0;i<n;i+) if(visitedi=0) bfs(g,i,visited); ,void bfs(TD g,int v,int visited) int quM,f=0,r=0; JD *p; printf("%dn",v+1); visitedv=1; qu0=v; while(fadjvex; if(visitedv=0) visitedv=1; printf("%dn",v+1); qu+r=v; p=p->next; ,6.4 生成树生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,最小生成树问题提出,要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树,问题分析,n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小,构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合初始令U=u0,(u0V), TE=在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树算法实现：图用邻接矩阵表示算法描述算法评价：T(n)=O(n²),Ch6_3.c,1,1,1,-2,1,-4,1,-1,1,-5,1,-3,#define M 30#define MAX 100void minispantree_PRIM(int adM,int n) int i,j,k,p,q,wm; q=p=n-1; adqq=1; for(k=0;kq) adpq=-adpq; else adqp=-adqp; ,方法二：克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止,（0）用顶点数组和边数组存放顶点和边信息（1）初始时，令每个顶点的jihe互不相同；每个边的flag为0（2）选出权值最小且flag为0的边（3）若该边依附的两个顶点的jihe 值不同，即非连通，则令 该边的flag=1, 选中该边；再令该边依附的两顶点的jihe 以及两集合中所有顶点的jihe 相同 若该边依附的两个顶点的jihe 值相同，即连通，则令该 边的flag=2, 即舍去该边（4）重复上述步骤，直到选出n-1条边为止,顶点结点：typedef struct int data; /顶点信息 int jihe; VEX;,