July 16, 2017
Plan to study the algorithm again.
It is the great to talk about the algorithm - topological sorting.
How to detect if there is a cycle in directed graph.
Using coloring to determine if there is a loop. Read the introduction of algorithm to figure out.
3 color scheme: white, gray, black
white - the node has not been visited before
gray - the node is visited by DFS search
black - it is visited before, and DFS is completed?
The basic idea is to visit white node using DFS, visit the white node and then mark it to be gray color. If the visit node is black, do not continue. However, it is a gray node, that means the loop is existing because it is second time to visit the same node.
If there is no loop in the graph, all nodes will be marked in black color.
Detail please read the blog written in Chinese, link is here.
Plan to study Java code implementation first. The study code is here.
No comments:
Post a Comment