图的存储之邻接表

title: 图的存储
date: 2022-10-16 周日
mindmap-plugin: basic
摘要: 本文记录了yxc提供的简易版邻接表的相关内容，并将其与严蔚敏中的链表进行了类比学习。
tags:

• 邻接表
• 图论

更新：用《数据结构》里的链表的视角来看下面的邻接表

书本里的链表：

typedef ... elemType;

typedef struct LNode{
    elemType data;
    LNode *next;
}LNode, *LinkList;

LinkList L = new LNode;

这里不使用哨兵节点。

基本量：

LinkList L = new LNode; // 为方便说明，设立一个链表节点 x ，头指针 L
LNode *x = new LNode;	// 记 x 的地址为 xAddr

int idx;	// 链表序号，相当于指向节点的指针，相当于 xAddr；每个序号唯一确定一个节点
			// idx ++ 相当于 new 一个节点
int h[N];	// 头指针数组，每个元素都相当于一个 L，指向某一个 x（ x 又指向其它链表节点）
int ne[N];	// 存储下一个节点的地址，相当于 LNode 里的 *next；ne[x_idx]，相当于xAddr->next, x.next 
int e[N];	// 链表节点的值, 相当于 LNode 里的 data，相当于 xAddr->data, x.data 
			// 这里节点的值为节点的序号

初始化

memset(h, -1, sizeof(h));

相当于

for (int i = 0; i < n; i ++ ) {
	h[i] = new LNode;
	h[i]->next = NULL;
}

加边

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

加边可以理解为

• （首先 idx 初始化为0，相当于已经分配了一个LNode指针，假设为p）
• e[idx] = b: p->data = b
• ne[idx] = h[a]: p->next = L
• h[a] = idx: L = p
• idx ++: p = new LNode

遍历

遍历每个点相邻的点

for (int u = h[i]; ~u; u = ne[u]){
	...
}

遍历可以理解为

for (LNode *s = L; s != NULL; s = s->next ){
    ...
}

基础：手写链表

以下为原内容：

基本量：

int h[N];	// 头指针，括号里填图节点的序号，初始为-1，代表指向空集
int ne[N];	// 链表节点的下一个节点的链表序号，括号里填链表序号
int e[N];	// 链表节点的值, 括号里填链表序号，将链表序号一一对应到图的序号 
int idx;	// 链表序号，链表节点的序号

基本操作

加边

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

遍历每个点相邻的点

for (int u = h[i]; ~u; u = ne[u]){
	...
}

例子

#include<iostream>
#include<cstring>
using namespace std;

const int N = 110, M = 310;                     // 点数，边数

int h[N], e[M], ne[M], idx;                     // 头指针，点权，下一个，标记
int n, m;                                       // m条边，n个点

void add(int a, int b){                         // 新建a → b的边
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main(void){
    cin >> n >> m;
    memset(h, -1, sizeof h);                    // 必要！初始化头指针数组，-1相当于空集
    for (int i = 0; i < m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);                   // 无向图即每个点之间有两条不同方向的边
    }

    for (int i = 1; i <= n; i ++ ){
    //    cout << h[i] << endl;
    //    cout << ne[h[i]] << endl;
        for (int u = h[i]; ~u; u = ne[u]){      // ~u等价于 u != -1
            // cout << e[u] << endl;            
        }
    }

    
    return 0;
}	

5 6	// 五个点，六条边，双向边
4 1	// idx: 2 1
4 2	// 4 3 
4 3 // 6 5
2 5	// 8 7
1 2	// 10 9
1 5 // 12 11

对应的数组

h[N]
10
9
5
4
11

e[h[N]]
5
1
4
3
1

e[N]
5 2 4 
1 5 4 
4 
3 2 1 
1 2

ne[h[N]]
8
6
-1
2
7