刷题：基于拓扑排序的图的环检测算法

川长思鸟来 2022-09-11 07:09 125阅读 0赞

有向图，环检测：  
给定一个有向图，检测里面是否存在环。  
有向图的环是指，存在一条路径，使得这条路径的起点和终点相同。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASWNvZGluZ19GMjAxNA_size_20_color_FFFFFF_t_70_g_se_x_16]

无向图，环检测：  
给定一个无向图，检测里面是否存在环。  
无向图的环是指，存在一条路径，使得这条路径的起点和终点相同。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASWNvZGluZ19GMjAxNA_size_20_color_FFFFFF_t_70_g_se_x_16 1]

方法：  
基于拓扑排序的方法：  
基于拓扑排序可以判断一个图是不是存在环，但是无法解决这个图里面环的个数、环里面节点元素是啥。

拓扑排序的算法为：  
对于有向图，  
首先将入度为0的节点入队。  
然后当队列不为空时：  
依次弹出队首元素；弹出过程中，将这个节点的所有邻居节点的入度都减一，如果在减一的过程中发现新的入度为0的节点，就将节点入队。

当队列空时，统计遇到过的节点数目和总节点数目。  
如果两个数相等则不存在环，否则存在。

数学原理：  
假设图里面存在一个环，那么对于整个环里面的任一节点，必定有一条入边、同时会有一条出边。在整个删除节点的过程中，整个环里面的任一节点的入度都至少为1。

对于无向图，只需要将入队的节点条件改为：节点的度小于等于1，即可。

leetcode 相关的题：  
Leetcode 207: Course Schedule https://leetcode.com/problems/course-schedule/

class _node{ 
    public:
    	int indegree=0;
    	vector<int> out_nodes;
    
    
    };
    class Solution { 
    public:
    	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { 
    		vector< _node> node_list;
    		for (int i = 0; i < numCourses; i++)
    		{ 
    			node_list.push_back(_node());
    		}
    		for (int i = 0; i < prerequisites.size(); i++)
    		{ 
    			node_list[prerequisites[i][1]].indegree++;
    			node_list[prerequisites[i][0]].out_nodes.push_back(prerequisites[i][1]);
    		}
    		int cnt = 0;
    		queue< _node> que;
    		for (int i = 0; i < numCourses; i++)
    		{ 
    			if (node_list[i].indegree == 0)
    			{ 
    				que.push(node_list[i]);
    			}
    		}
    		while (!que.empty())
    		{ 
    			_node n = que.front();
    			que.pop();
    			cnt++;
    			for (int i =0; i < n.out_nodes.size(); i++)
    			{ 
    				node_list[n.out_nodes[i]].indegree--;
    				if (node_list[n.out_nodes[i]].indegree == 0)
    				{ 
    					que.push(node_list[n.out_nodes[i]]);
    				}
    			}
    		}
    		return cnt == numCourses;
    	}
    };

Leetcode :210. Course Schedule II  
https://leetcode.com/problems/course-schedule-ii/  
输出路径，注意需要倒序输出。

class _node{ 
    public:
    	int indegree = 0;
    	int node_id = 0;
    	vector<int> out_nodes;
    	_node(int id)
    	{ 
    		node_id = id;
    	}
    };
    class Solution { 
    public:
    	vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { 
    		vector< _node> node_list;
    		vector<int> trace;
    		for (int i = 0; i < numCourses; i++)
    		{ 
    			node_list.push_back(_node(i));
    		}
    		for (int i = 0; i < prerequisites.size(); i++)
    		{ 
    			node_list[prerequisites[i][1]].indegree++;
    			node_list[prerequisites[i][0]].out_nodes.push_back(prerequisites[i][1]);
    		}
    		int cnt = 0;
    		queue< _node> que;
    		for (int i = 0; i < numCourses; i++)
    		{ 
    			if (node_list[i].indegree == 0)
    			{ 
    				que.push(node_list[i]);
    			}
    		}
    		while (!que.empty())
    		{ 
    			_node n = que.front();
    			que.pop();
    			trace.push_back(n.node_id);
    			cnt++;
    			for (int i = 0; i < n.out_nodes.size(); i++)
    			{ 
    				node_list[n.out_nodes[i]].indegree--;
    				if (node_list[n.out_nodes[i]].indegree == 0)
    				{ 
    					que.push(node_list[n.out_nodes[i]]);
    				}
    			}
    		}
    		reverse(trace.begin(), trace.end());
    		if (cnt == numCourses)
    			return trace;
    		else
    		{ 
    			return{ };
    		}
    	}
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASWNvZGluZ19GMjAxNA_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/74fb0e0f3e2945baaed4d6885dbb28f8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASWNvZGluZ19GMjAxNA_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/d70032fe201c49bcbd0db1e96f352799.png