欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 手游 > 图的邻接表

图的邻接表

2025/2/26 15:13:59 来源:https://blog.csdn.net/2401_87338545/article/details/143981151  浏览:    关键词:图的邻接表

单链表笔记:

数组模拟单链表-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]); }
}

 

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词