《数据结构图的算法的毕业论文正稿》由会员分享，可在线阅读，更多相关《数据结构图的算法的毕业论文正稿（68页珍藏版）》请在金锄头文库上搜索。
1、. . . . . 图图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。1 图的基本概念和存储结构 1.1 图的定义图（Graph）是由非空的顶点集合V与描述顶点之间关系边（或者弧）的集合E组成，其形式化定义为：G=(V, E) 如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(v
2、i,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。 如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系边或弧的信息。因此无论采取什么方法来建
3、立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用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中的
4、边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行非零元
5、素（或非元素）的个数正好是第i个顶点的出度OD(vi)，第i列非零元素（或非元素）的个数正好是第i个顶点的入度ID(vi)。（4）用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中具体有多少条边，则必须按行、按列对每一个元素进行查找后方能确定，因此花费的时间代价较大，这也是用邻接矩阵存储图的局限性。 在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的邻接矩阵之外，还需要用一个一维数组存储顶点信息。这样，一个图在顺序存储结构下的类型定义为； typedef struct char vertexMaxNum; /*顶点为字符型且顶点表的长度小于Ma
6、xNum*/ 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)
7、 /建立无向图的邻接矩阵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
8、(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 无向图及邻接矩阵表示对图
9、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 邻接表 邻接表是图的一种顺序存储与链式存储相结合的存储方法。邻接
10、表表示法类似于树的孩子表示法。也即，对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表。用邻接表表示的图有两种结构，如图7-9所示。顶点域 邻接表表头指针 邻接点域 指针域vertexfirstedgeadjvexnext 顶点表结点 邻接表结点图7-9 邻接表表示的结点结构 一种是用一维数组表示的顶点表的结点（即数组元素）结构，它由顶点域（vertex）和指向该顶点第一条邻接边的指针域（firstedge）（也即，这个指针指向该顶点的邻接表）所构成。另一种是邻接表结点（
11、边结点），它由邻接点域(adjvex)和指向下一条邻接边的指针域（next）所构成。对带权图（网）的邻接表结点则需增加一个存储边上权值信息的这样一个域。因此，带权图的邻接表结点结构如图7-10所示。adjvexinfonext图7-10 带权图（网）的邻接表结点结构图7-11给出了图7-6所示的无向图所对应的邻接表表示。图7-11 无向图的邻接表表示邻接表表示下的类型定义为：typedef struct node /*邻接表结点*/ int adjvex; /*邻接点域*/ struct node *next; /*指向下一个邻接边结点的指针域*/EdgeNode; /*邻接表结点类型*/ty
12、pedef 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信息*/
