对“图的存储结构”的理解

2019-11-06 09:02:36

字体：大中小

来源：转载

供稿：网友

图的存储结构1 邻接矩阵两个数组来表示图1）一个【一维数组】存储图的【顶点】信息2）一个【二维数组】存储图的【边】的信息a) 无向图无向图的邻接矩阵是一个对称矩阵并且对角线上元素数值为 0因为无向图只要两个顶点v1,v2之间有边,那么不管是v1 -> v2 还是 v2 -> v1都是有边又因为，在图结构中，目前只研究简单图结构（无向图两个顶点之间只有一条边并且顶点没有到自身的边）所以邻接矩阵对角线上的元素为 0两个顶点v1,v2之间有边 -> 邻接矩阵中的(v1，v2) = 1；否则（v1，v2）= 0无向图中的度：顶点所对应的行或列中非0元素的个数，就是该顶点的度b) 有向图有向图的邻接矩阵不是一个对称矩阵，但是矩阵主对角线上的值仍然为 0，原因和无向图中的一样两个顶点的边是由顺序的（v1，v2）有边，!= （v2，v1）就有边，正因为这个原因有向图的邻接矩阵不是对称矩阵邻接矩阵中的值，比如（v1，v2）的值，就是v1，v2之间的权值有向图中的度分为，出度，入度，在邻接矩阵中，入度，出度是这样计算的：入度：顶点所对应的【列】中非0元素的个数出度：顶点所对应的【行】中非0元素的个数3）创建邻接矩阵a) 创建邻接矩阵存储结构typedef char VertexType;typedef int EdgeType;#define Max 100//最大顶点数#define INFINITY 65535//如果两个顶点之间没有权重，就为无穷大 typedef struct {VertexType vexs[Max];//存储顶点信息的一维数组EdgeType arc[Max][Max];//二维数组组成的邻接矩阵，可看作边表int numEdge,numVertex;//边数顶点数}MGraph;b) 构造图，给顶点表和邻接矩阵输入数据的过程void CreatMGraph(MGraph *G){//01 输入边数，顶点数int i,j;int numEdge,numVertex;cout << "输入边数，顶点数: " ;cin >> numEdge >> numVertex;//02 输入顶点信息，建立顶点表cout << "请输入顶点信息： " << endl;for(i = 0; i < numVertex; i++){cin >> G->vexs[i];}//03 初始化邻接矩阵for(i = 0; i < numEdge; i++){for(j = 0; j < numEdge; j++){G->arc[i][j] = INFINITY;}}//04 输入边信息for(int k = 0; k < numVertex; k++){cout << "请输入边(v1,v2)两个顶点的下标i,j，以及边权重w" <<endl;cin >> i >> j >> w;G->arc[i][j] = w;//边的权重为wG->arc[j][i] = G->[i][j];//无向图，矩阵对称 }}4）邻接矩阵的缺点：当图中的表边数较少时，邻接矩阵仍然需要开辟 numVertex*numVertex个空间，这是对内存空间的浪费2 邻接表用一个一维数组或单链表记录图中顶点的信息（data firstedge）data 顶点信息 firstedge第一个邻接点的指针用一个线性链表存储每个顶点的所有邻接点（agjvex weight next）agjvex 邻接点在一维数组（顶点表）中的下标 weight 权重 next 下一个结点的指针邻接表由三部分结构体组成：typedef char VertexTypetypedef int EdgeType1）记录邻接边信息的结构体 EdgeNodetypedef struct EdgeNode{int agjvex; //邻接点域，存储该点对应的下标EdgeType weight; //存储权重，非网图可以不要EdgeNode *next;//链域，指向下一个链接点}EdgeNode; 2）记录顶点信息的结构体 VertexNodetypedef struct VertexNode {int data; //存储顶点数据EdgeNode *firstedge;//边表头指针，指向与该点组成边的另一个点对应的下标}VertexNode,AdjList[Max];//AdjList[Max] 存储顶点信息的一维数组多个VertexNode类型的元素组成一维数组，存储顶点信息3）记录当前图中的顶点个数，边的个数 GraphAdjListtypedef struct GraphAdjList {AdjList adjList; int numEdge,numVertex;//当前图的顶点个数，边数}GraphAdjList;4）存储邻接边信息（邻接边是 EdgeNode 类型的） GraphAdjList *Ga) 输入顶点个数numVertex，边的个数numEdge循环输入顶点信息，建立顶点表，顶点信息存储在AdjList[i].data中将G->adjList[i].firstedge = nullb) 建立边表每循环一次，就向内存申请一次的空间e EdgeNode类型，存放邻接边信息，没有某种结构类型来存储，比如数组输入（Vi，Vj）邻接边的序号i,j e->adjvex = j; //顶点i的邻接序号e->next = G->adjList[i].firstedge;//使用的是单链表中的头插法将当前顶点的 firstedge 给 e指针指向G->adjList[i].firstedge = e;//将当前顶点的 firstedge 指向 e 同样，对于下标为j的顶点，它的边表的建立如下：e->adjvex = i;e->next = G->adjList[j].firstedge;G->adjList[j].firstedge = e;3 十字链表1）将邻接表和逆邻接表结合起来2）顶点表结构： data firstin firstoutdata ：顶点数据firstin ：顶点的入边的第一个结点firstout ：表示出边表头指针，指向该顶点的出边表中的第一个结点3）边表结构：tailvex headvex headlink tailinktailvex : 弧【起】点在顶点表中的下标headvex : 弧【终】点在顶点表中的下标headlink ：指入边表指针域，指向【终点相同】的下一条边tailink : 指出边表指针域，指向【起点相同】的下一条边4）代码和邻接表的类似：typedef char VertexType;typedef int EdgeType;#define Max 65535//01 顶点表结构体 VertexNodetypedef struct VertexNode{VertexType data;EdgeNode *firstin;EdgeNode * firstout;}VertexNode,AdjList[Max];//02 边表结构体 EdgeNodetypedef struct EdgeNode{int tailvex,headvex;struct EdgeNode *headlink;struct EdgeNode *tailink;}EdgeNode;//03 顶点数，边数typedef struct GraphAdjList{AdjList adjList;int numEdge,numVertex;}GraphAdjList;//04 建立十字链接表结构void CreatOrthogonal(GraphAdjList *G){int i,j;//1 输入顶点个数numVertex，边的个数numEdgecout << "输入边数，顶点数： ";cin >> numEdge >> numVertex;cout << endl;//2 输入顶点信息，建立顶点表cout << "输入顶点信息，建立顶点表：" << endl;for(i = 0; i < numVertex; i++){cin >> G->adjList[i].data;G->adjList[i].firstin = null;//出入边表为空G->adjList[i].firstout = null;}//3 构建十字链表结构？}4 邻接多重表ivex illink jvex jlinkillink : 指向依附顶点ivex的下一条边jlink : 指向依附顶点jvex的下一条边ivex jvex ：与某条边依附的两个顶点在顶点表中的下标 5 边集数组

begin end weight

部分代码摘抄自《大话数据结构》

上一篇：大神主页

下一篇：【.ISO】一份来自2016-2017的半年总结