数据结构

2023-08-14 15:55| 来源: 网络整理| 查看: 265

图的定义：

图(Graph)G由两个集合V和E组成，记为：G=(V,E)，其中V是顶点的有穷非空集合(其实就是顶点)，E是V中顶点偶对的有穷集合(就是边)。V(G)和E(G)通常分别表示图G的顶点集合以及边集合，E(G)可以为空集合，但是此时的图只有顶点，没有边。分类：

有向图：在有向图中，顶点对是有序的，表示它从V到W的一条有向边。所以，表示的和不同的边，顶点的指向不同。有向图中顶点对用尖括号表示，，x是有向边的始点，y是有向边的终点，称x为弧尾，y为弧头。无向图：在无向图中，顶点对(V,W)是无序的，表示V到W的一条边，这条边没有特定的方向即，(V,W)和(W,V)表示同一条边。和有向图不同的是，无向图的表示方法是用圆括号括起来()。

下面是图的示例：在这里插入图片描述

图的存储结构：邻接矩阵：邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵： ①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。 ②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。 ③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。声明一下，上述邻接矩阵的定义的描述来自于百度百科，可能大家第一遍看的时候不是那么理解，这里整那么多什么i啊，什么度啊，还有什么空间啥的，整的大家比较烦，那么就让我这个小菜鸡来给大家捋一捋。首先，看这个名词邻接矩阵，不就是元素与元素相邻形成一个矩阵么，这时，希望大家，脑海中有一个矩阵的画面。这里面就存放了一些数据，至于是什么数据，后面会给大家讲到。其次，我们现在就要给脑海中这个矩阵放点东西了。好，我们想啊，一个图用邻接矩阵表示出来，这个矩阵中无非就是放了些从一个顶点"走"到另外一个顶点，要花去的"费用"嘛，这个费用就是我们的权重，那么显然这个矩阵中的数据就是顶点之间的权重。那么光有权重在里面我们不好理解，那么我们就在这个矩阵的最上方以及最左方加上每个元素的下标或者标号，这个我们看的时候就可以找到对应元素的权重了，实际操作中是不需要的。也就是说，我们现在这个矩阵，相当于变成了表格了，上面和左边是坐标，下面那一块全是数据(权重),此时这个表格就是我们所说的图，不知道大家理解没有，如果没有的话，可以在草稿纸上画画，便于理解。接下来，讲讲我们的干货了。如何实现呢。邻接矩阵的实现：思路(接下来，会以非常平常的语气，来讲述，因为本身我就是个小菜鸡，水平有限，还请见谅!) 大家想啊，我要对这个图要进行一些操作，那么我们首先要做的就是初始化一个图，初始化什么样的一个图呢，初始化一个只有顶点，没有边的图，因为这样我们才能把权重放入图中。好，从这个出发点想，这个图要有什么要素呢，，，，，要有顶点数，边数，以及存放顶点的一些数据，还有顶点之间的权重，那么用什么来表示这些要素呢，顶点数，边数，自然是用整形类型的变量来表示咯，那顶点数据用什么来存放，因为顶点数是一维的，所以我们采用数组的存储形式存放顶点数据。最后一个，权重，，，emm想想它的定义，从一个顶点到另外一个顶点所要花去的"费用"，自然想到的就是二维数组咯。好了，废话讲到这里，接下来，干货来了，代码奉上再声明一下，代码中也会有一些注释，还有一些思路，都是本菜鸡写的，写的不好的地方，恳求大家指出，谢谢！！！ #pragma once # include # include # define MaxVertexnum 100 typedef int ElemType; //邻接矩阵 typedef struct graph { int Nv; //顶点数 int Ne; //边数 int Data[MaxVertexnum]; //存放顶点数据 int Weight[MaxVertexnum][MaxVertexnum]; //存放权重 }graph,*MGraph; typedef struct edge { int V1, V2; //V1到V2 int Weight; //边用来存放权重 }*Edge; //初始化有Vertnex个顶点的图 void InitGraph(MGraph G, int Vertnex) { G->Nv = Vertnex; //有Vertnex个顶点 G->Ne = 0; //边数为0 //初始化每条边的权重 for (int i = 0; i G->Weight[E->V1][E->V2] = E->Weight; G->Weight[E->V2][E->V1] = E->Weight; } 邻接表：邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点v建立一个单链表，把与v相邻接的顶点放在这个链表中。邻接表中的每个单链表的结点存放有关顶点的信息，把这个结点看成这个链表的表头，其余结点存放有关边的信息，这样邻接表便有两部分组成：表头结点和边表。

表头结点表：由所有的表头结点以顺序结构的形式存储，以便计算机随机访问任一顶点的边链表。表头结点包括**数据域和链域(指向边表指针)**两部分组成。

边表：边链表中边结点包括邻接点域，数据域，链域三部分。邻接点域指的是指向同类的指针，数据域指的是存放与边相关的一些信息(权重),链域指的是与头结点链域中指针所指向的指针域。相信大家对于这个理解还是比较的深刻的，我这个小菜鸡就不瞎哔哔了^ - ^。现在脑子里应该有这样一副画面，有一个长方形块，这个长方形块有若干个小块组成，每个小块有两个部分，第一部分是数据域，第二部分是指针域，这个指针域就指向边表。代码奉上：

typedef struct EdgeNode //边结点 { int weight; //存放权重 struct EdgeNode *next; //指向边结点 int local; //该边指向的顶点 }EdgeNode; /*边链表中边结点包括邻接点域，数据域，链域，邻接点域指示与顶点v邻接的位置(指针)，数据域存放与边相关的数据，如：权重。链域指示与顶点v 邻接的下一条边的结点*/ typedef struct VNode //顶点结点 { int data; //顶点数据 EdgeNode *firstVertnex; //指向边 }VNode,AdjList[MaxVertexnum]; /*表头结点表：由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表表头结点包括数据域，链域，数据域存放顶点的一些数据,链域用于指向链表中第一个结点(即与定点v邻接的第一个邻接点)*/ typedef struct Adjgraph { int Nv; int Ne; AdjList List; }AdjMGraph; void InitAdjGraph(AdjMGraph* G) { printf("请输入顶点数和边数(空格分隔)!\n"); int Nv, Ne; scanf("%d %d", &G->Nv, &G->Ne); printf("请输入顶点数据:\n"); for (int i = 1; i Nv; i++) { printf("第%d个顶点数据为:\n",i); scanf("%d", &G->List[i].data); //收入每一个顶点的数据 G->List[i].firstVertnex = NULL; //每个顶点的指针域置为空 } getchar(); } /*接下来要进行放入有效数据，把权重放入邻接表中,由于是生成无向图，所以此时要生成两个结点*/ void CreateAdjGraph(AdjMGraph *G) { printf("一共有%d条边!\n", G->Ne); printf("请输入两个顶点以及二者之间的权重(中间用空格分隔):\n"); int W, V,weight; for (int i = 1; i Ne; i++) { scanf("%d %d %d", &W, &V,&weight); EdgeNode *p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->local = V; p->weight = weight; p->next = G->List[W].firstVertnex; G->List[W].firstVertnex= p; EdgeNode *q = (EdgeNode*)malloc(sizeof(EdgeNode)); q->local = W; q->weight = weight; q->next = G->List[V].firstVertnex; G->List[V].firstVertnex = q; } }

打印出邻接矩阵：

void PrintAdjGraph(AdjMGraph *G) { printf("将打印出邻接表的示意图!\n"); for (int i = 1; i Nv; i++) { printf("%-3d->", i); while (G->List[i].firstVertnex != NULL) { printf("%-3d---weight:%-3d->",G->List[i].firstVertnex->local,G->List[i].firstVertnex->weight); G->List[i].firstVertnex = G->List[i].firstVertnex->next; } if (G->List[i].firstVertnex == NULL) printf("!\n"); } }

接下来，main函数(里面包含了邻接矩阵的打印)

# include # include # include "Graph.h" int main() { printf("用邻接矩阵创建无向图!\n"); //要建立一个有vertnex个顶点无边的图 int vertnex; printf("请输入有图中有多少个顶点:\n"); scanf("%d", &vertnex); //建立一个图，首先要声明一个图 MGraph G; G = (MGraph)malloc(sizeof(graph)); //接着要初始化图 InitGraph(G, vertnex); //接着往图中插入数据 printf("请输入边数:\n"); int Ne; scanf("%d", &Ne); if (Ne != 0) { printf("请输入顶点和权重(空格分隔!)\n"); for (int i = 0; i for (int i = 0; i Weight[i][j]); printf("\n"); } printf("将打印顶点元素中的数据!\n"); for (int i = 0; i Data[i]); printf("-------------------------------------------------\n"); printf("用邻接表创建无向图\n"); AdjMGraph *Graph = (Adjgraph*)malloc(sizeof(Adjgraph)); InitAdjGraph(Graph); CreateAdjGraph(Graph); PrintAdjGraph(Graph); system("pause"); return 0; }

代码运行截图：在这里插入图片描述

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻