图的邻接表存储

发布于 2018-08-10  293 次阅读


邻接表作用

为神魔药学图的邻接表存储呢?邻接矩阵多好!

有时,当图很稀疏时,用邻接矩阵就会产生不必要的内存浪费。

如下图:

它的邻接矩阵大概是这样:

0 5 ∞ ∞ ∞

5 0 3 ∞ ∞

∞ 3 0 1 ∞

∞ ∞ 1 0 3

∞ ∞ ∞ 3 0

我们发现,这样的图用邻接表存储很浪费时空。这样的图我们可以用邻接表来存。

邻接表原理

邻接矩阵表示的是点与点的关系,而邻接表表示的是边和点的关系。

我们有一个数组,head[i],存的是i点发出的第一条边编号。

同时,每一条边还有next,to,data变量,用来存储这条边的一个兄弟边的编号,即存储这条边的一个相邻的边的编号,to代表这条边到哪,data代表边权。

首先,我们添加从 1->2 的边,当前边的编号为1,把head[1]发出的第一条边的编号设为1(这里1->2边的编号是1,所以是1)。

因为是无向图,所以我们也要添加一条从 2->1的边,这条边的编号为2,我们把把head[2]发出的第一条边的编号设为2。

我们添加从 2->3 的边,当前边的编号为3,把head[2]发出的第一条边的编号设为3,把原先的head[2]=2设为3的next。

我们也添加一条从 3->2的边,这条边的编号为4,我们把把head[3]发出的第一条边的编号设为4。

我们添加从 3->4 的边,当前边的编号为5,把head[3]发出的第一条边的编号设为5,把原先的head[3]=4设为5的next。

我们也添加一条从 4->3的边,这条边的编号为6,我们把把head[4]发出的第一条边的编号设为6。


我们添加从 4->5 的边,当前边的编号为7,把head[4]发出的第一条边的编号设为6,把原先的head[4]=6设为7的next。

我们也添加一条从 5->4的边,这条边的编号为8,我们把把head[5]发出的第一条边的编号设为8。

代码实现

const int maxn=1000;

struct node
{
    int to;
    int data;
    int next;
}edge[maxn];

int head[maxn],num=0;

void add_edge(int from,int to,int data)
{
    num++;
    edge[num].next = head[from];
    head[from] = num;
    edge[num].to = to;
    edge[num].data = data;
}

// add_edge(1,2,5);    //有向图

/*
add_edge(1,2,5);
add_edge(2,1,5);    //无向图
*/