上传文件的网站,网页设计与制作用什么软件做,建e网室内设计网母,网业车资格证怎么报名细说链式前向星存图法
首先要明白#xff0c;链式前向星的原理是利用存边来进行模拟图。 推荐左神的视频–建图、链式前向星、拓扑排序 比方说有这样一张图#xff0c;我们用链式前向星来进行模拟时#xff0c;可以将每一条边都进行编号#xff0c;其中#xff0c;红色的…细说链式前向星存图法
首先要明白链式前向星的原理是利用存边来进行模拟图。 推荐左神的视频–建图、链式前向星、拓扑排序 比方说有这样一张图我们用链式前向星来进行模拟时可以将每一条边都进行编号其中红色的数字就是对每一条边的编号蓝色的数字表示每一个结点编号。 准备三个数组head[], next[], to[] 数组名称下标含义值的含义head结点值结点指向的边next边的编号该边指向下一条边to边的编号边指向的结点值 idx:表示当前还没有分配的边编号 添加边
所以添加边的函数add()可以这样去设计:
//建立一个a-b的结点-结点,-表示边
inline void add(int a, int b) {to[idx] b, next[idx] head[a], head[a] idx;
}
//新建一条边编号为idx指向结点b然后在a结点的邻居边中增加idx边思想类似与头插法让这个新的边指向头边并修改头边为新的边。Code
#include iostream
#include cstring
using namespace std;const int N 10001; //最多生成N个结点,N-1个单边
int head[N], to[N], next[N], idx;// head[]头边号
// 点号 // next[] 下一条边号
// 边号// to[] 去往的点
// 边号// idx
inline void add(int a, int b) {to[idx] b, next[idx] head[a], head[a] idx;
}inline void dfs(int u) {cout u ;int i head[u]; //i为u结点第一条边for (; i ! -1; i next[i]) {//每次更新为下一条边dfs(to[i]); //去到 i 边指向的结点 }
}int main() {memset(head, -1, sizeof head);//head[i]为-1表示这个结点没有后继边add(1, 2);add(1, 5);add(1, 6);add(2, 6);add(5, 6);dfs(1);
}
