图的邻接表

单链表笔记：

数组模拟单链表-acwing-CSDN博客

邻接表

图的邻接表其实就是多个单链表，下面是自己的理解输出笔记。

图的邻接表还得从数据结构本质出发，首先有几个顶点N，几条边M

head数组所有单链表的头结点，初始值为-1，代表单链表为空。

其中head[u] 表示单链表的u头结点索引。e[2*M] 因为无向图是边的两倍，互为邻接点。e[i]，某条单链表头结点的邻接点。ne[i] 索引i指向的下一个邻接点的索引。通过索引通过索引可访问结点。

单边表的头插法

赋值idx:e[idx] = a;指向头结点ne[idx]=head，更新头结点head

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

准备工作

const int N = 1010; // 顶点个数
const int M = 10100; // 边的条数

int h[N]; //链表头结点 or 某顶点为头结点链表入口，其实是指向哪一个索引的意思 or 狐尾
int e[2*M]; // 无向图的存边存了两次，两倍的M。// 其实是邻接点 or 弧头的意思 // 某一条弧头对应的弧尾顶点的意思
int ne[2*M]; // 指向作用，指向下一个邻结点索引。
int idx = 0; // 索引编号从0开始

//初始化头结点
memset(h,-1,sizeof h); 

搭建邻接表存数据

边的添加=> 将b头插法插到链表h[a]，h[a]是链表入口，也是头结点。指向头结点，更新头结点。更新idx。

h[a] 代表顶点 a邻接点链表 对应索引， 该索引是该链表入口。

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

邻接表的遍历

一条条链表遍历

void tableTravel() {
for(int k = 0; k < n; k ++) {
if(h[k]!=-1) {
cout <<"头结点编号" << h[k] << "邻接点：" ;
//遍历h[k]链表的所有邻接点
for(int i = h[k]; i != -1; i = ne[i]) {
cout << e[i] << " ";
cout << endl;
} 
}//if

}
}

图的遍历 dfs

h[u] 存顶点头结点的索引， e[i] 存邻接点结点，ne[i] 存下一个邻接点索引

void dfs(int u) {
// u 是当前顶点 
vis[u] = true; // 搜索标记 
cout << u << " ";
// 从当前顶点 开始遍历到该单链表表尾
// 同时不断先 dfs 往下搜索 

// 遍历索引 
for(int i = h[u]; i != -1; i = ne[i]) {
// 索引对应e[i] 标记 
if(!vis[e[i]]) dfs(e[i]); 
}
}

 

 

原文地址：https://blog.csdn.net/2401_87338545/article/details/143981151

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！