图的邻接表存储

邻接表作用

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

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

如下图：

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

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);    //无向图
*/