MENU

链式前向星

July 19, 2020 • Read: 55 • 算法

在存储图的时候,一般有三种办法:

  1. 邻接矩阵
  2. 邻接表
  3. 链式前向星

今天就大概来讲一讲这三种方法

邻接矩阵

邻接矩阵是这三种方法中最直观的方法了,大概意思就是生成一个二维数组。并且将数组中的每一个值都初始化为 -1 ,然后再将数据存入二维数组中

例如:

现有如下一组边

(起点,终点,边长度)
(1,2,3)
(1,4,4)
(1,3,1)
(2,5,2)
(4,5,5)
(3,5,6)

那么在这个二维数组中,(假如二维数组叫做 w ),就有边的长度为 w[1] [2] = 3, w[1] [4] = 4 ... 以此类推

这样的存储方式虽然简单易写,但是空间复杂度却很高,因此人们开发出了第二种方式

邻接表

相较于邻接数组,邻接表的空间复杂度更低,其原理大概是这样

我们依旧使用上表数据,可以知道,边的起点有1,2,3,4 四种,

我们首先看1:

1先是能到2,并且长度为3,所以我们先画出这样一个节点

image-20200719111527005

这样就表示1 => 2 ,权值(长度)为3

同理,1 => 3 就这样表示

image-20200719111807245

那么起点为1的这一系列边我们怎么表示呢?

image-20200719112048994

对于起点为2的,也是这样表示

image-20200719112232547

其余同理

但是这样写的话就太过复杂了,有没有简单的方法呢?

链式前向星

前向星我就不讲了,反正也没人傻到去用那个100%超时的玩意儿

链式前向星其实就是邻接表的简化版本,其本质是一样的

首先我们需要一个结构体来存储边信息

struct node{
    int to;    // 终点(不是链表末尾的那个点,别误会了)
    int w;    // 边长
    int next;    // 下一个点
}Edge[MAXN];
int cnt = 0, Head[MAXN];    // head 用于记录起始点

同时,有了结构体,也得要存数据吧,

void AddEdge(int bg, int ed, int weight)
{
    Edge[cnt].to = ed;
    Edge[cnt].w = weight;
    Edge[cnt].next = Head[bg];
    Head[bg] = cnt++
}

使用AddEdge函数就可以添加一个新的边(单向)了

注意:AddEdge是将数据添加到链表的最前面

Archives Tip
QR Code for this page
Tipping QR Code