[数据结构与算法]图的模板 总结

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<string, priority_queue<sting, greater<string>>> ump; //用优先队列来找字典序最小的节点
vector<string> 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<string, int> 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 < ans1.size() - 1; ++i) {
    ans2.push_back(vector<int>{ans1[i], ans1[i + 1]});
}

2.求有向无环图的拓扑排序 ---------------------------------------------------O(顶点数+边数)
思路：
用indegree[]数组存每个结点的入度，将入度为0的节点放入队列，每出队一个结点u，就将它所能到的所有节点v的入度-1（用vector v[indegree.size()]来存），如果v的入度为0，则入队。
如果要求按照节点递增的顺序拓扑排序，则将队列改为：优先队列
step1：先得到邻接表+入度数组
step2：队列写个循环

//可以用来判断是否是有向无环图  v为vector<vector<int>>，存储所有的边
unordered_map<string, int> indegree; //节点->入度数
for (auto& each : v) { //v存起点->终点的vector<vector<string>>
	indegree[each[1]]++;
}
vector<string> v[indegree.size()]; //邻接表存储
for (auto& each : v) {
	v[each[0]].push_back(each[1]);
}
queue<string> q;
//priority_queue<string, vector<string>, greater<string>> q;
for (auto& each : indegree) {
	if (!each.second) q.push(each.first);
}
int cnt = 0;
while (!q.empty()) {
	string frt = q.front();
	//cout << frt << endl;
	q.pop();
	cnt++;
	for (auto& each : v[frt]) {
		indegree[each]--;
		if (!indegree[each]) q.push(each);
	}
}
if (cnt == indegree.size()) return true; //是有向无环图
return false; //不是有向无环图