Detect cycle in a directed graph
2024-10-06 09:08:34
Question: Detect cycle in a directed graph
Answer:
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS.
The idea is to do DFS of given graph and while doing traversal, assign one of the below three colors to every vertex.
WHITE : Vertex is not processed yet. Initially all vertices are WHITE. GRAY : Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (ind DFS tree) of this vertex are not processed yet (or this vertex is in function call stack) BLACK : Vertex and all its descendants are processed. While doing DFS, if we encounter an edge from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle. https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
最新文章
- JavaScript call
- Node.js之NPM工具使用
- Grunt 使用记录
- 【转】根据中国气象局提供的API接口实现天气查询
- Nginx配置加入css缓存配置后，css等文件not found
- SSH 登录VPS解决 The directory media/wysiwyg is not writable by server.问题
- 温故而知新 clone
- 设置TextView控件的背景透明度和字体透明度
- mybatis使用时org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):的错误
- linux下ifconfig, DNS以及route配置
- A - FatMouse' Trade
- 「OC」 多态
- 身为运维的你，怎么掌握python才不会失业
- 利用DOS命令窗口进行Mail通信(二)
- jar包通过exe4j打包成exe可执行文件
- CEPH集群操作入门--部署和运维
- 微信小程序中如何使用WebSocket实现长连接(含完整源码)
- cf366C Dima and Salad (dp)
- Choose GitLab for your next open source project
- javascript的密封对象之seal(),isSealed()方法