扯三种图论数据结构😂(因为觉得连浅谈都算不上,就当做个总结)

版权声明:本文为奥维原创文章,未经允许不得转载.

前言:今天简单学习了一下图论,有一点感悟,算是做一个小总结,大神不要喷

关于三种数据结构的概述

这三种数据结构都是图论里面的基本数据结构,学名分别是邻接矩阵(Adjacency Matrix),邻接表(Adjacency List),十字链表(Orthogonal List)三种.我的理解是,这三种数据结构都是对图的一个表示方法,只不过是”外观”看起来不太一样,侧重的元素不同.直接看名字比较抽象,下面一种一种做一个简单介绍(图论一些基本概念可以参照离散数学,这里不再赘述)

先上张图供大家参考
1

邻接矩阵

在邻接矩阵这个结构里面,主要的数据结构模型是用一个一维数组对vertex(图论中的顶点)做一个存储,这样我们就可以索引到每一个vertex(顶点)元素.但是此时我们还没有表达出连接两个vertex之间的arc(i.e.,edge,弦,弧,或者叫边)的关系.所以在邻接矩阵里面还用了一个二维数组去存储两个vertex之间的arc的关系,如上图,一维数组中记录下顶点值为1,0,2,3,4的部分,二维数组记录顶点之间的关系,这里是一个有向网(含有权值的有向图),那么二维数组中存储的就是两个顶点之间的权值,否则就存储默认值(无穷大,实际编程可以设定一个很大的数).说了这么多,这个邻接矩阵到底是什么呢,我个人理解就是这里的二维数组.

邻接表

邻接表这个数据结构,我目前的理解是,它是一种用于实现图的链式存储结构.他也是先用一个一维数组对vertex做一个存储,这样我们就可以索引到每一个vertex元素.然后表达边集的方式是通过每一个vertex元素存储了指向第一个这个vertex(顶点)的arc(边)的指针,然后每一个边结构除了存储了边上的信息之外,还存储了指向下一个边的指针,这样子我们就可以索引到下一个边,直到为NULL.通过这样的链式存储结构,我们就可以实现图了.个人理解是,这个数据结构是以vertex为头,然后可以不断索引到这个vertex相关的所有arc(边).又因为我们可以遍历一维数组从而索引到所有的vertex,每一个vertex又是一个类似链表的结构,所以我们就完成对图的全部索引了.

十字链表

十字链表是一种适用于有向图的链式结构.他使用一个一维数组,完成对所有vertex的索引.这个链式结构主要依赖于两种基本的结构.

  • vertex(顶点)结点结构 : 存储顶点本身的信息,以及指向它的第一个arc的指针和第一个从它指出去的arc的指针
  • arc(弧)节点结构 : 存储这个arc两端的vertex的信息数据, 以及与它同起点的下一个arc的指针,以及与他同终点的下一个arc的指针.以及arc自身的信息

相似点

这三种数据结构都依赖一个存储vertex的一维数组,从这个一维数组的vertex来索引vertex与vertex之间的关系(边).本质上来说这三种数据结构都是围绕着vertex和arc两种东西,表达出他们之间的关系

不同点

虽然本质上都是为了描述图这种数据结构,但他们的实现手段不太一样.

  • 邻接矩阵主要通过一个二维数组存储vertex之间的arc的 权值或者是无向图中两个vertex是否相连的关系.
  • 邻接表主要是通过类似链表的形式,把vertex中每一个元素当成头结点,一个接一个索引到与这个顶点相关的全部arc
  • 十字链表主要用于有向图,在顶点中保存了对指向自己和自己指向的arc的索引,同时arc中也存储了arc两端顶点的数据
    以及自身指向的下一个头arc或者尾arc

代码

简单写了一点可能会有bug,初步调试通过,只列出文件头,具体实现看个人了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//邻接矩阵
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100
//设置一个权值代表无限大
#define INFINATE 32767

typedef char vertextype;
typedef int weight;

typedef struct graphic
{
vertextype vertexes[MAX_NUM];
weight weights[MAX_NUM][MAX_NUM];
int vertexNum, edgeNum;
} *Graphics;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//邻接表
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH 100
#define INFINATE 32767

typedef struct edge
{
int whichSite;
int weight;
struct edge* nextEdge;
}*edge;

typedef struct vertex
{
char value;
struct edge* nextEdge;
}*vertex;

typedef struct graphic
{
vertex vertexes[MAX_LENGTH];
int vertexNum, edgeNum;
}*graphic;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//十字链表
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH 100
typedef char vertexType;
typedef struct arcNode
{
char headValue, tailValue;
struct arcNode *headNext;
struct arcNode *tailNext;
int weight;
}*arcNode;
typedef struct vertexNode
{
vertexType value;
arcNode firstIn, firstOut;
}*vertexNode;
typedef struct graphic
{
vertexNode vertexNodes[MAX_LENGTH];
int vertexNum, arcNum;
}*graphic;

参考

  • 数据结构 第二版 严蔚敏
啦啦啦啦啦啦