图的模板总结

2023-04-21 19:13| 来源: 网络整理| 查看: 265

1.求有向图的欧拉路---------------------------------------------------O(边数)

了解几个概念：欧拉通路：通过图中所有边，但构不成回路->有向半欧拉图无向半欧拉图的特点：当且仅当连通且仅有两个奇度节点有向半欧拉图的特点：当且仅当强连通且恰有一个顶点的出度=入度+1；（起点）恰有一个顶点的入度=出度+1；（重点）所有其他顶点的入度和出度相同。欧拉回路：通过图中所有边，且可以构成回路->有向欧拉图无向欧拉图的特点：当且仅当连通且无奇度节点有向欧拉图的特点：当且仅当强连通且每个顶点的入度和出度相同

求有向图欧拉路的流程： 1.从起点出发，进行深度优先搜索。 2.每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。 3.如果没有可移动的路径，则将所在节点加入到栈中，并返回。注意：当遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈），我们只要将栈中的内容反转，即可得到答案。详解：leetcode332：https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/模板如下：

题目：给定起点，找欧拉通路。要求：针对同一条边，终点优先选字典序较小的节点->优先队列实现 unordered_map ump; //用优先队列来找字典序最小的节点 vector ans; void dfs(string str) { while (ump.size()) { string tmp = ump[str].top(); //得到字典序最小的边 ump[str].pop(); //删边 dfs(tmp); } v.push_back(str); } for (auto& each : tickets) { ump[each[0]].push(each[1]); } dfs(起点); reverse(ans.begin(), ans.end()); return ans;

重点： 1.对于半欧拉图，找欧拉通路，从起点开始dfs

如果不知道起点，先找起点：对每条边，对起点度数--，终点度数++，最终起点的度数为-1. unordered_map ump; for (auto& each : tickets) { ump[each[0]]--; ump[each[1]]++; } for (auto& each : ump) { if (each.second == -1) dfs(each.first); }

2.对于欧拉图，找欧拉通路，从任意节点开始dfs 3.如果最后需要得到pair对

for (int i = 0; i [1]） nums为节点个数（节点取值为0->nums-1） */ vector indegree(nums); //节点->入度数 vector bian(nums); //邻接表存储 for (auto& each : v) { indegree[each[0]]++; bian[each[1]].push_back(each[0]); } queue q; //priority_queue q; for (int i = 0; i

【本文地址】

图的模板总结

图的模板总结

今日新闻

推荐新闻

图的模板 总结

图的模板 总结

今日新闻

推荐新闻

图的模板总结

图的模板总结