欢迎来到夜场招聘网!

数据构造之图(逐个)图的存储构造

来源:夜店招聘网 时间:2019-08-14 作者:夜店招聘网 浏览量:
图的存储结构相对于线性表和树来说更为复杂,因为图中的顶点具有相对概念,没有固定的位置。那我们怎么存储图的数据结构呢?我们知道,图是由(V,E)来表示的,对于无向图来说,其中V= (v0,v1, ... ,vn),E= { (vi,vj) (0 <= i, j <= n且i 不等于j)},对于有向图,E= { (0 <= i, j <= n且i 不等于j)}。V是顶点的集合,E是边的集合。所以我们只要把顶点和边的集合储存起来,那么该图的所有数据就能够存储起来了。
本文只介绍两种比较常见和重要的图的存储结构:邻接矩阵和邻接表。
邻接矩阵,顾名思义,是一个矩阵,一个存储着边的信息的矩阵,而顶点则用矩阵的下标表示。对于一个邻接矩阵M,如果M(i,j)=1,则说明顶点i和顶点j之间存在一条边,对于无向图来说,M (j ,i) = M (i, j),所以其邻接矩阵是一个对称矩阵;对于有向图来说,则未必是一个对称矩阵。邻接矩阵的对角线元素都为0。下图是一个无向图和对应的临街矩阵:
图1:无向图
图2:邻接矩阵
需要注意的是,当边上有权值的时候,称之为网图,则邻接矩阵中的元素不再仅是0和1了,邻接矩阵M中的元素定义为:。
以下用C语言创建一个无向图的邻接矩阵:
头文件是:GraphStruct.h
1 7 typedef char vertexType; 8 typedef int edgeType; 9 typedef struct GraphMatrix{1011 int vertexNumber;// 顶点数量12 int edgeNumber; // 边的数量13 vertexType *vertex;// 顶点集合,动态数组14 edgeType** edge;// 边集合,二维动态数组1516 } GraphMatrix;1718 void GraphMatrix_create(GraphMatrix *g);
该头文件包含了邻接矩阵的数据结构,结构体的成员变量包括顶点数量、边的数量、顶点集合和边的集合。为了节省空间,将顶点集合和边集设为动态数组,根据顶点数量来分配空间。
 实现文件是:GraphStruct.c
1 #include 2 #include 3 #include"GraphStruct.h" 4 5 void GraphMatrix_create(GraphMatrix *g){ 6 7 printf("请分别输入图的顶点数量和边的数量,用空格隔开:"); 8 scanf("%d %d", &g->vertexNumber, &g->edgeNumber); //将顶点数量和边的数量存储在结构体g中相应的变量 9 g->vertex = (vertexType*)malloc(g->vertexNumber * sizeof(vertexType)); //为动态数组申请空间10 //二维动态数组申请空间11 g->edge = (edgeType**)malloc(g->vertexNumber * sizeof(edgeType));12 for (int i = 0; i < g->vertexNumber; i ){13g->edge[i] = (edgeType*)malloc(g->vertexNumber * sizeof(edgeType));14 }15 //初始化邻接矩阵的所有元素16 for (int i = 0; i < g->vertexNumber; i ){17for (int j = 0; j < g->vertexNumber; j )18 g->edge[i][j] = 0;19 }2021 //输入图的信息22 for (int k = 0; k < g->edgeNumber; k ){2324int i, j;25printf("请输入边(vi,vj)的下标, i和j,用空格隔开:");26scanf("%d%d", &i, &j);27g->edge[i][j] = 1; //(i,j)和(j,i)指的是一条边28g->edge[j][i] = 1;29 }3031 //输出图的信息32 printf("Your graph matrix is :\n");33 for (int i = 0; i < g->vertexNumber; i ){34for (int j = 0; j < g->vertexNumber; j ){35 printf("%d\t", g->edge[i][j]);36}37printf("\n");38 }39
测试文件为:main.c
1 #include 2 #include "GraphStruct.h" 3 4 int main(){ 5 6 GraphMatrix *gm; 7 gm = (GraphMatrix *)malloc(sizeof(GraphMatrix)); 8 GraphMatrix_create(gm); 9 1011 return 0;12 }
运行结果为:
图3 运行结果
对于有向图,网图的代码,只要将上面的代码稍微修改就行了,本文末尾附上代码的下载地址。
对于顶点数很多但是边数很少的图来说,用邻接矩阵显得略为“奢侈”,因为矩阵元素为1的很少,即其中的有用信息很少,但却占了很大的空间。所以下面我们来看看邻接表,以图1的无向图为例,我们先不讲理论的知识,先把图1的邻接表画出来,如图4。
图4 邻接表
作为顶点0,它的邻接顶点有1,3,4,形成的边有(0,1),(0,3)和(0,4),所以顶点0将其指出来了;对于顶点1,它的邻接顶点有0,2,4,所以顶点1将其指出来了,以
热门话题
推荐文章
最新文章

Copyright C 2018 All Rights Reserved 版权所有 午夜招聘网

微信扫一扫