建筑人才招聘网站,江西中耀建设集团有限公司网站,长安镇做网站,建立网站的方法文章目录 0#xff09;概述1#xff09;Kahn算法1#xff1a;数据结构2#xff1a;建图3#xff1a;Kanh算法 2#xff09;DFS染色1#xff1a;数据结构2#xff1a;建图3#xff1a;DFS 3#xff09;算法对比【例题】洛谷 B3644 推荐视频链接#xff1a;D01 拓扑排… 文章目录 0概述1Kahn算法1数据结构2建图3Kanh算法 2DFS染色1数据结构2建图3DFS 3算法对比【例题】洛谷 B3644 推荐视频链接D01 拓扑排序 0概述 给定一张有向无环图排出所有顶点的一个序列 A A A 满足对于图中的每条有向边 ( x , y ) (x,y) (x,y) x x x 在 A A A 中都出现在 y y y 之前则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环可以生成拓扑序列 对于下图 { 2 , 3 , 5 , 1 , 7 , 4 , 6 } \{2,3,5,1,7,4,6\} {2,3,5,1,7,4,6} 和 { 3 , 2 , 1 , 5 , 7 , 6 , 4 } \{3,2,1,5,7,6,4\} {3,2,1,5,7,6,4} 都是合法的拓扑序 复习一下链式前向星吧【C算法模板】图的存储-邻接表手撕链式前向星超详细代码注释-CSDN博客 1Kahn算法
算法核心用队列维护一个入度为 0 0 0 的节点的集合
初始化链式前向星建图建边队列 q q q 压入所有入度为 0 0 0 的点每次从 q q q 中取出队头 x x x 放入数组 t p tp tp t p tp tp 数组保存出队顺序也就是拓扑序然后将 x x x 的所有出边删除如删除边 ( x , y ) (x,y) (x,y) y y y 的入度则 − 1 -1 −1如果 y y y 的入度变为 0 0 0则将 y y y 压入 q q q 中其中每个顶点的入度用数组 d d d 维护不断重复 2 , 3 2,3 2,3 过程直到队列 q q q 为空若 t p tp tp 中的元素个数等于 n n n则有拓扑序否则有环
1数据结构
const int N1e55; // 最大顶点数
const int M1e510; // 题目中最大边数,拓扑排序是有向图建边,无需×2int d[N]; // 存储每个顶点的入度
queueint q; // 维护入度为0的顶点的队列
queueint tp; // 记录q中顶点的出队顺序(拓扑序)int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子2建图
// 链式前向星
void add(int a,int b) {e[idx]b;ne[idx]h[a]; // 头插法思想h[a]idx;
}3Kanh算法
// 拓扑序存储于tp队列中,如果能形成拓扑序返回true
bool tuopu() {for(int i1;in;i) {// 如果入度为0则加入队列if(d[i]0) q.push(i);}while(q.size()) {int xq.front();q.pop();tp.push(x); // 出队顺序即拓扑序// 遍历x的所有出边for(int ih[x];i-1;ine[i]) {int je[i];// 如果去掉边(i,j)后j的入度变为0,则加入队列if(--d[j]0) q.push(j);}}return tp.size()n; // 如果能形成一个拓扑序,返回true,否则false
}2DFS染色
算法核心在于染色法每次 d f s dfs dfs 搜索会给点变色如果有拓扑序每个点的颜色都会从 0 → − 1 → 1 0→-1→1 0→−1→1 经历三次变色
初始化将所有点染色为 0 0 0枚举每个点进入点 x x x将 x x x 染色为 − 1 -1 −1随后枚举 x x x 的所有儿子结点 y y y如果 y y y 的颜色仍为 0 0 0说明该点未被遍历过则递归到下一层如果 y y y 的颜色为 − 1 -1 −1说明遍历到祖先节点了即出现了环则直接 r e t u r n return return如果枚举完 x x x 的所有儿子节点都没有发现环则把 x x x 染色为 1 1 1并把 x x x 压入 t p tp tp 数组注意因为 D F S DFS DFS 是栈实现的回溯的时候才把点加入 t p tp tp 数组所以需要将 t p tp tp 数组逆序才能得到拓扑序
1数据结构
const int N1e55; // 最大顶点数
const int M1e510; // 题目中最大边数,拓扑排序是有向图建边,无需×2int c[N]; // 存储每个结点的颜色
vectorint tp; // 存储拓扑序int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子2建图
// 链式前向星
void add(int a,int b) {e[idx]b;ne[idx]h[a]; // 头插法思想h[a]idx;
}3DFS
// dfs
bool dfs(int x) {c[x]-1; // 先染色为-1// 遍历所有儿子节点for(int ih[x];i-1;ine[i]) {int je[i]; // 取出节点编号if(c[j]0) return false; // 遍历到祖先节点,有环,直接return// 如果没有遍历过else if(!c[j])// 继续往下搜,自然结束return 0if(!dfs(j))return false;}c[x]1; // 如果能够正常走掉dfs流程,则染色为1tp.push(x); // 进入拓扑序数组return true;
}bool toposort() {vectorint tp; // 用vector存储便于反转memset(c,0,sizeof c); // 染色初始化为0for(int i1;in;i) {// 如果c没有被走过if(!c[i])// 如果遇到环则说明无法形成拓扑序if(!dfs(i))return 0;}reverse(tp.begin(),tp.end());return 1;
}3算法对比
在实际使用拓扑排序时只需要掌握 K a h n Kahn Kahn 即可因为更好理解 D F S DFS DFS 染色和二分图中的匈牙利算法的思想比较类似这里只用了解即可 K a h n Kahn Kahn队列维护顺着拓扑序收集点 D F S DFS DFS系统栈维护逆着拓扑序收集点 二者时间复杂度都为 O ( E V ) O(EV) O(EV)其中 E E E 为边数 V V V 为点数
【例题】洛谷 B3644 题目链接B3644 【模板】拓扑排序 / 家谱树 - 洛谷 #includebits/stdc.h
#define x first
#define y secondusing namespace std;typedef long long ll;
typedef pairint,int PII;// 解题思路: const int N1e55; // 最大顶点数
const int M1e510; // 题目中最大边数,拓扑排序是有向图建边,无需×2int n; // 顶点数int d[N]; // 存储每个顶点的入度
queueint q; // 维护入度为0的顶点的队列
queueint tp; // 记录q中顶点的出队顺序(拓扑序)int h[N]; // 存储每个顶点起始边的编号,默认-1表示无边相连
int e[M]; // e[i]:编号为i的边可达的顶点编号
int ne[M]; // ne[i]:编号为i的边的下一条边的编号是ne[i]
int idx; // 边的编号,建边因子// 链式前向星
void add(int a,int b) {e[idx]b;ne[idx]h[a]; // 头插法思想h[a]idx;
}// 拓扑序存储于tp队列中,如果能形成拓扑序返回true
void tuopu() {queueint q;for(int i1;in;i) {// 如果入度为0则加入队列if(d[i]0) q.push(i);}while(q.size()) {int xq.front();q.pop();coutx ; // 直接输出拓扑序tp.push(x); // 出队顺序即拓扑序// 遍历x的所有出边for(int ih[x];i!-1;ine[i]) {int je[i];// 如果去掉边(i,j)后j的入度变为0,则加入队列if(--d[j]0) q.push(j);}}
}int main() {cinn;memset(h,-1,sizeof h); // 链式前向星邻接表初始化for(int i1;in;i) {int j;// 当j0时退出循环while(cinj j) {add(i,j);d[j]; // 节点j的入度}}tuopu();return 0;
}
