图论系列：图的表示 |
您所在的位置：网站首页 › 图论w表示什么 › 图论系列：图的表示 |
图论系列：图的表示
|
一、图的表示
对于一个图（graph）G=（V，E）由顶点集V（vertex）和边集E（edges）组成。每一条边就是一个点对（u，w），其中u、w属于V。 1.邻接矩阵（adjacency matrix）邻接矩阵本质上就是一个二维数组，例如对于每条边（u，w），可以表示为A[u][w]=1（边没有权值），否则A[u][w]=0（这条边不存在）。如果边有权值，可以令A[u][w]=权值。 2.邻接表邻接表使用一个表来存放所有邻接的顶点。
邻接表：由上图可知，邻接表节点由头结点和表节点组成
（1）头表结点结构 ┌────┬─────┐ │data │ firstedge │ └────┴─────┘ 顶点vi邻接表的头结点包含两个域： ① 顶点域data 存放顶点vi的信息 ② 指针域firstedge vi的邻接表的头指针。
（2）边表结点结构 ┌────┬───┐ │adjvex │next │ └────┴───┘ 邻接表中每个表结点均有两个域: ① 邻接点域adjvex 存放与vi相邻接的顶点vj的序号j。 ② 链域next 将邻接表的所有表结点链在一起。 注意： --- 若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。 ---上述图用邻接表表示为： A B C D A 0 1 1 1 B 1 0 0 1 C 1 0 0 0 D 1 1 0 0 二、C代码实现其数据结构 1.邻接矩阵在C语言中，如果我们想表示标准C语言不存在的数据类型，一般使用结构体来实现。把已有的数据类型组合成我们想要的数据类型。表示一张图，需要的参数有：图的顶点数，图的边数，一个二维数组，因此可以定义一个结构体包含三种类型的数据 #define ROW 100 #define COL 100 typedef struct AdjMatrix { int matrix[ROW][COL]; int NumVertex; //图的顶点数 int Numedges; //图的边数 }MGraph; //使用指针进行构建，自己管理内存 typedef struct AdjMatrix_P { int *matrix; int NumVertex; //图的顶点个数 int Numedges; //图的边数 }MPGraph; 这里使用了两种方法去构建图的数据类型，第一种方法定义了一个固定长度的二维数组，第二种方法定义一个指向整形类型的指针，但在使用前需要为其分配内存，来存放图的节点和边的信息。使用第一个数据类型构建一张图：
|
【本文地址】