数据结构图的算法的毕业论文.doc

图图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。1 图的基本概念和存储结构 1.1 图的定义图（graph）是由非空的顶点集合v与描述顶点之间关系边（或者弧）的集合e组成，其形式化定义为：g=(v, e) 如果图g中的每一条边都是没有方向的，则称g为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(vi,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。 如果图g中的每一条边都是有方向的，则称g为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用c语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为：v=v0,v1,vn-1。下面介绍几种常用的图的存储结构。1.2 邻接矩阵所谓邻接矩阵存储结构，就是用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。假定图g=(v, e)有n个顶点，即v=v0,v1,vn-1，则表示g中各顶点相邻关系需用一个nn的矩阵，且矩阵元素为：1 若(vi,vj)或是e中的边0 若(vi,vj)或不是e中的边aij= 若g是带权图（网），则邻接矩阵可定义为：wij 若(vi,vj)或是e中的边0或 若(vi,vj)或不是e中的边aij= 其中，wij表示(vi,vj)或上的权值；则为计算机上所允许的大于所有边上权值的数值。无向图的邻接矩阵表示如图7-6所示。图7-6 无向图及邻接矩阵表示有向图的邻接矩阵表示如图7-7所示。图7-7 有向图及邻接矩阵表示带权图的邻接矩阵表示如图7-8所示。图7-8 带权图及邻接矩阵表示从图的邻接矩阵可以看出以下特点：（1）无向图（包括带权图）的邻接矩阵一定是一个按对角线对称的对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2）对于无向图，邻接矩阵的第i行或第i列的非零元素（或非元素）个数正好是第i个顶点的度d(vi)。（3）对有向图，邻接矩阵的第i行非零元素（或非元素）的个数正好是第i个顶点的出度od(vi)，第i列非零元素（或非元素）的个数正好是第i个顶点的入度id(vi)。（4）用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中具体有多少条边，则必须按行、按列对每一个元素进行查找后方能确定，因此花费的时间代价较大，这也是用邻接矩阵存储图的局限性。 在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的邻接矩阵之外，还需要用一个一维数组存储顶点信息。这样，一个图在顺序存储结构下的类型定义为； typedef struct char vertexmaxnum; /*顶点为字符型且顶点表的长度小于maxnum*/ int edgesmaxnummaxnum; /*边为整型且edges为邻接矩阵*/ mgraph; /*mgraph为采用邻接矩阵存储的图类型*/建立一个无向图的邻接矩阵程序如下：#include#include#define maxsize 30typedef struct char vertexmaxsize; /顶点为字符型且顶点表的长度小于maxsize int edgesmaxsizemaxsize; /边为整型且edges为邻接矩阵 mgraph; /mgraph为采用邻接矩阵存储的图类型void creatmgraph(mgraph *g,int e,int n) /建立无向图的邻接矩阵g-egdes，n为顶点个数，e为边数 int i,j,k; printf(input data of vertexs(0n-1):n); for(i=0;ivertexi=i; /读入顶点信息 for(i=0;in;i+) for(j=0;jedgesij=0; /初始化邻接矩阵 for(k=1;kedgesij=1; g-edgesji=1; void main()int i,j,n,e; mgraph *g; /建立指向采用邻接矩阵存储图类型指针g=(mgraph *)malloc(sizeof(mgraph); /生成采用邻接矩阵存储图类型的存储空间printf(input size of mgraph: ); /输入邻接矩阵的大小scanf(%d,&n); printf(input number of edge: ); /输入邻接矩阵的边数scanf(%d,&e); creatmgraph(g,e,n); /生成存储图的邻接矩阵printf(output mgraph:n); /输出存储图的邻接矩阵for(i=0;in;i+)for(j=0;jedgesij);printf(n);【说明】无向图的邻接矩阵表示如图15-1所示。 0 1 0 1 a= 1 0 1 1 0 1 0 0 1 1 0 0 v0v3v1v2图15-1 无向图及邻接矩阵表示对图15-1所示的无向图，程序执行如下：输入： input size of mgraph: 4input number of edge: 4input data of vertexs(0n-1):input edge of(i,j): 0,1input edge of(i,j): 0,3input edge of(i,j): 1,3input edge of(i,j): 1,2输出： output mgraph: 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0press any key to continue 1.3 邻接表 邻接表是图的一种顺序存储与链式存储相结合的存储方法。邻接表表示法类似于树的孩子表示法。也即，对于图g中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表。用邻接表表示的图有两种结构，如图7-9所示。顶点域 邻接表表头指针 邻接点域 指针域vertexfirstedgeadjvexnext 顶点表结点 邻接表结点图7-9 邻接表表示的结点结构 一种是用一维数组表示的顶点表的结点（即数组元素）结构，它由顶点域（vertex）和指向该顶点第一条邻接边的指针域（firstedge）（也即，这个指针指向该顶点的邻接表）所构成。另一种是邻接表结点（边结点），它由邻接点域(adjvex)和指向下一条邻接边的指针域（next）所构成。对带权图（网）的邻接表结点则需增加一个存储边上权值信息的这样一个域。因此，带权图的邻接表结点结构如图7-10所示。adjvexinfonext图7-10 带权图（网）的邻接表结点结构图7-11给出了图7-6所示的无向图所对应的邻接表表示。图7-11 无向图的邻接表表示邻接表表示下的类型定义为：typedef struct node /*邻接表结点*/ int adjvex; /*邻接点域*/ struct node *next; /*指向下一个邻接边结点的指针域*/edgenode; /*邻接表结点类型*/typedef struct vnode /*顶点表结点*/ int vertex; /*顶点域*/ edgenode *firstedge; /*指向邻接表第一个邻接边结点的指针域*/vertexnode /*顶点表结点类型*/ 建立一个无向图的邻接表存储算法如下：void creatadjlist（vetexnode g,int e,int n）/*建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点*/ edgenode *p;int i,j,k; printf(“input date of vetex(0n-1);n”); for(i=0;in;i+) /*建立有n个顶点的顶点表*/ gi.vertex=i; /*读入顶点i信息*/ gi.firstedge=null; /*初始化指向顶点i的邻接表表头指针*/ for(k=1;kadjex=j; /*在顶点vi的邻接表中添加邻接点为j的结点*/ p-next=gi.firstedge; /*插入是在邻接表表头进行的*/ gi.firstedge=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=i; /*在顶点vj的邻接表中添加邻接点为i的结点*/ p-next=gj.firstedge; /*插入是在邻接表表头进行的*/ gi.firstedge=p; 2 图的遍历 图的遍历是指从图中的任一顶点出发，按照事先确定的某种搜索方法依次对图中所有顶点进行访问且仅访问一次的过程。图的遍历要比树的遍历复杂得多，其复杂性主要表现在以下4个方面：（1） 在图结构中，没有象树根结点那样 “自然” 的首结点，即图中的任何一个顶点都可以作为第一个被访问的结点。（2） 在非连通图中，从一个顶点出发只能访问它所在的连通分量上的所有顶点；因此，还需考虑如何选取下一个未被访问的顶点来继续访问图中其余的连通分量。（3） 在图结构中如果有回路存在，则一个顶点被访问后有可能沿回路又回到该顶点。（4） 在图结构中一个顶点可以和其它多个顶点相邻，当该顶点访问过后则存在如何从众多相邻顶点中选取下一个要访问的顶点问题。图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。图的遍历通常采用深度优先搜索（depth first search,dfs）和广度优先搜索（breadth first search,bfs）两种方式，这两种方式对无向图和有向图的遍历都适用。2.1 深度优先搜索深度优先搜索对图的遍历类似于树的先根遍历，是树的先根遍历的一种推广；也即，搜索顶点的次序是沿着一条路径尽量向纵深发展。深度优先搜索的基本思想是：假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点v出发即先访问v，然后依次从v的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和v有路径相通的顶点都被访问过；若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。我们以图7-18的无向图为例进行图的深度优先搜索。假定从顶点v0出发，在访问了顶点v0后选择邻接点v1作为下一个访问的顶点；由于v1未曾访问过，则访问v1并继续由v1开始搜索下一个邻接点v3作为访问顶点；v3同样没有访问过，则访问v3并继续搜索下一个邻接点v6；v6也未访问过，则访问v6再继续搜索下一个邻接点v4；v4未曾访问过，则访问v4并继续搜索下一个邻接点v1，此时由于v1已被访问过则回退至v4继续搜索v4的下一个邻接点；由于v4已无未被访问过的邻接点，则继续回退到v6再搜索v6的未被访问邻接点；这种回退一直持续到v0，此时可搜索到v0的未被访问邻接点v2，即访问v2并继续搜索下一个邻接点v5；由于v5未被访问，则访问v5并继续搜索v5的邻接点；因v5已无未被访问过的邻接点故回退至v2，继续搜索v2的未被访问邻接点，但v2已无未被访问过的邻接点，则回退至v0，而v0也无未被访问的邻接点。由于v0为搜索图时的出发结点，故到此搜索结束。由此得到深度优先搜索遍历图的结点序列为：v0v1v3v6v4v2v5图7-18 无向图深度优先搜索示意显然，深度优先搜索遍历图的过程是一个递归过程，我们可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿着某条回路回到该顶点这种重复访问的情况出现，就必须在图的遍历过程中对每一个访问过的顶点进行标识，这样才可以避免一个顶点被重复访问的情况出现。所以，我们在遍历算法中对n个顶点的图设置了一个长度为n的访问标志数组visitedn，每个数组元素被初始化0，一旦某个顶点i被访问则相应的visitedi就置为1来做为访问过的标志。对以邻接表为存储结构的图（可为非连通图）进行深度优先搜索的程序如下：#include#include#define maxsize 30typedef struct node /邻接表结点 int adjvex; /邻接点域 struct node *next; /指向下一个邻接边结点的指针域edgenode; /邻接表结点类型typedef struct vnode /顶点表结点 int vertex; /顶点域 edgenode *firstedge; /指向邻接表第一个邻接边结点的指针域vertexnode; /顶点表结点类型void creatadjlist(vertexnode g,int e,int n)/建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 edgenode *p; int i,j,k; printf(input date of vetex(0n-1);n); for(i=0;in;i+) /建立有n个顶点的顶点表 gi.vertex=i; /读入顶点i信息 gi.firstedge=null; /初始化指向顶点i的邻接表表头指针 for(k=1;kadjvex=j; /在顶点vi的邻接表中添加邻接点为j的结点 p-next=gi.firstedge; /插入是在邻接表表头进行的 gi.firstedge=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; int visitedmaxsize; /maxsize为大于或等于无向图顶点个数的常量void dfs(vertexnode g,int i) edgenode *p; printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点i visitedi=1; /置顶点i为访问过标志 p=gi.firstedge; /根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=null) /当邻接边结点不为空时 if(!visitedp-adjvex) /如果邻接的这个边结点未被访问过 dfs(g,p-adjvex); /对这个边结点进行深度优先搜索 p=p-next; /查找顶点i的下一个邻接边结点 void dfstraverse(vertexnode g,int n)/深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 int i; for(i=0;in;i+) visitedi=0; /访问标志置0 for(i=0;in;i+) /对n个顶点的图查找未访问过的顶点并由该顶点开始遍历 if(!visitedi) /当visitedi等于0时即顶点i未访问过 dfs(g,i); /从未访问过的顶点i开始遍历void main()int e,n; vertexnode gmaxsize; /定义顶点表结点类型数组gprintf(input number of node:n); /输入图中结点个数scanf(%d,&n); printf(input number of edge:n); /输入图中边的个数scanf(%d,&e); printf(make adjlist:n);creatadjlist(g,e,n); /建立无向图的邻接表 printf(dfstraverse:n); dfstraverse(g,n); /深度优先遍历以邻接表存储的无向图printf(n);【说明】对图15-1所示的无向图，程序执行如下：输入： input number of node:4input number of edge:4make adjlist:input date of vetex(0n-1);input edge of(i,j): 0,1input edge of(i,j): 0,3input edge of(i,j): 1,3input edge of(i,j): 1,2输出： dfstraverse: 0 3 1 2press any key to continue2.2 广度优先搜索广度优先搜索遍历图类似于树的按层次遍历。广度优先搜索的基本思想是：从图中某顶点v出发，访问顶点v后再依次访问与v相邻接的未曾访问过的其余邻接边结点v1，v2，vk；接下来再按上述方法访问与v1邻接的未曾访问过的各邻接边结点、与v2邻接的未曾访问过的各邻接边结点、与vk邻接的未曾访问过的各邻接边结点；这样逐层下去直至图中的全部顶点都被访问过。广度优先搜索遍历图的特点是尽可能先进行横向搜索，即先访问的顶点其邻接边结点也先访问，后访问的顶点其邻接边结点也后访问。例如，对图7-19所示的无向图进行广度优先搜索遍历，首先访问v0，然后访问v0未被访问的邻接边结点v1和v3（注意，先是v1然后才是v3），接下来访问v1未被访问的邻接边结点v4，再访问v3未被访问邻接边结点v2（v3的邻接边结点v4已被访问过）。此时，图中所有顶点都被访问过即完成了图的遍历，所得到的顶点访问序列为：v0v1v3v4v2为了实现图的广度优先搜索，必须引入队列结构来保存已访问过的顶点序列；即从指定的顶点开始，每访问一个顶点就同时使该顶点进入队尾；然后由队头取出一个顶点并访问该顶点的所有未被访问过的邻接边结点并且使该邻接边结点进入队尾，如此进行下去直到队空时为止，则图中所有由开始顶点所能到达的全部顶点均已访问过。对以邻接表为存储结构的图进行广度优先搜索的程序如下：#include#include#define maxsize 30typedef struct node1 /邻接表结点 int adjvex; /邻接点域 struct node1 *next; /指向下一个邻接边结点的指针域edgenode; /邻接表结点类型typedef struct vnode /顶点表结点 int vertex; /顶点域 edgenode *firstedge; /指向邻接表第一个邻接边结点的指针域vertexnode; /顶点表结点类型void creatadjlist(vertexnode g,int e,int n)/建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 edgenode *p; int i,j,k; printf(input date of vetex(0n-1);n); for(i=0;in;i+) /建立有n个顶点的顶点表 gi.vertex=i; /读入顶点i信息 gi.firstedge=null; /初始化指向顶点i的邻接表表头指针 for(k=1;kadjvex=j; /在顶点vi的邻接表中添加邻接点为j的结点 p-next=gi.firstedge; /插入是在邻接表表头进行的 gi.firstedge=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; typedef struct node int data; struct node *next;qnode; /链队列结点的类型typedef struct qnode *front,*rear; /将头、尾指针纳入到一个结构体的链队列lqueue;void init_lqueue(lqueue *q) /创建一个带头结点的空队列 qnode *p; *q=(lqueue *)malloc(sizeof(lqueue);/申请带头、尾指针的结点 p=(qnode*)malloc(sizeof(qnode);/申请链队列的头结点 p-next=null; /头结点的next指针置为空 (*q)-front=p; /队头指针指向头结点 (*q)-rear=p; /队尾指针指向头结点int empty_lqueue(lqueue *q) /判队空 if(q-front=q-rear)/队为空 return 1; else return 0;void in_lqueue(lqueue *q,int x) /入队 qnode *p; p=(qnode *)malloc(sizeof(qnode);/申请新链队列结点 p-data=x; p-next=null;/新结点作为队尾结点时其next域为空 q-rear-next=p; /将新结点*p链到原队尾结点之后 q-rear=p; /使队尾指针指向新的队尾结点*pvoid out_lqueue(lqueue *q,int *x) /出队 qnode *p; if(empty_lqueue(q) printf(queue is empty!n);/队空，出队失败 else p=q-front-next;/指针p指向链队列第一个数据结点（即队头结点） q-front-next=p-next; /头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点） *x=p-data;/将删除的队头结点数据经由x返回 free(p); if(q-front-next=null)/出队后队为空，则置为空队列 q-rear=q-front; int visitedmaxsize; /maxsize为大于或等于无向图顶点个数的常量void bfs(vertexnode g,lqueue *q,int i)/广度优先搜索遍历邻接表存储的图，g为顶点表，q为队指针，i为第i个顶点 int j,*x=&j; edgenode *p; printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点i visitedi=1; /置顶点i为访问过标志 in_lqueue(q,i); /顶点i入队q while(!empty_lqueue(q) /当队q非空时 out_lqueue(q,x); /队头顶点出队并送j（暂记为顶点j） p=gj.firstedge;/根据顶点j的表头指针查找其邻接表的第一个邻接边结点 while(p!=null) if(!visitedp-adjvex) /如果邻接的这个边结点未被访问过 printf(%4d,gp-adjvex.vertex);/输出这个邻接边结点的顶点信息 visitedp-adjvex=1; /置该邻接边结点为访问过标志 in_lqueue(q,p-adjvex); /将该邻接边结点送入队q p=p-next; /在顶点j 的邻接表中查找j的下一个邻接边结点 void main()int e,n; vertexnode gmaxsize; /定义顶点表结点类型数组glqueue *q;printf(input number of node:n); /输入图中结点个数scanf(%d,&n); printf(input number of edge:n); /输入图中边的个数scanf(%d,&e); printf(make adjlist:n);creatadjlist(g,e,n); /建立无向图的邻接表 init_lqueue(&q); /队列q初始化printf(bfstraverse:n); bfs(g,q,0); /广度优先遍历以邻接表存储的无向图printf(n);【说明】对图15-1所示的无向图，程序执行如下：输入： input number of node:4input number of edge:4make adjlist:input date of vetex(0n-1);input edge of(i,j): 0,1input edge of(i,j): 0,3input edge of(i,j): 1,3input edge of(i,j): 1,2输出： bfstraverse: 0 3 1 2press any key to continue2.3图的连通性问题 判断一个图的连通性是图的应用问题，我们可以利用图的遍历算法来求解这一问题。1. 无向图的连通性 在对无向图进行遍历时，对连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点；对于非连通图，则需要由不连通的多个顶点开始进行搜索，且每一次从一个新的顶点出发进行搜索过程中得到的顶点访问序列，就是包含该出发顶点的这个连通分量中的顶点集。 因此，要想判断一个无向图是否为连通图，或者有几个连通分量，则可增加一个计数变量count并设其初值为0，在深度优先搜索算法dfstraverse函数里的第二个for循环中，每调用一次dfs就给count增1；这样当算法执行结束时的count值即为连通分量的个数。 无向图连通分量的计算程序如下#include#include#define maxsize 30typedef struct node1 /邻接表结点 int adjvex; /邻接点域 struct node1 *next; /指向下一个邻接边结点的指针域edgenode; /邻接表结点类型typedef struct vnode /顶点表结点 int vertex; /顶点域 edgenode *firstedge; /指向邻接表第一个邻接边结点的指针域vertexnode; /顶点表结点类型void creatadjlist(vertexnode g,int e,int n)/建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 edgenode *p; int i,j,k; printf(input date of vetex(0n-1);n); for(i=0;in;i+) /建立有n个顶点的顶点表 gi.vertex=i; /读入顶点i信息 gi.firstedge=null; /初始化指向顶点i的邻接表表头指针 for(k=1;kadjvex=j; /在顶点vi的邻接表中添加邻接点为j的结点 p-next=gi.firstedge; /插入是在邻接表表头进行的 gi.firstedge=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; int visitedmaxsize; /maxsize为大于或等于无向图顶点个数的常量void dfs(vertexnode g,int i) /图的深度优先遍历 edgenode *p; printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点i visitedi=1; /置顶点i为访问过标志 p=gi.firstedge; /根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=null) /当邻接边结点不为空时 if(!visitedp-adjvex) /如果邻接的这个边结点未被访问过 dfs(g,p-adjvex); /对这个边结点进行深度优先搜索 p=p-next; /查找顶点i的下一个邻接边结点 int count=0; /连通分量计数count初值为0void connectedge(vertexnode g,int n) /求图的连通分量/深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 int i; for(i=0