How do we search a graph?
At a particular vertices, where shall we go next?
Two common framework:
In DFS, go as far as possible along a single path until reach a dead end (a vertex with no edge out or no neighbor unexplored) then backtrack
In BFS, one explore a graph level by level away (explore all neighbors first and then move on)
At a particular vertices, where shall we go next?
Two common framework:
- the depth-first search (DFS)
- the breadth-first search (BFS) and
In DFS, go as far as possible along a single path until reach a dead end (a vertex with no edge out or no neighbor unexplored) then backtrack
In BFS, one explore a graph level by level away (explore all neighbors first and then move on)
Color Scheme
- Vertices initially colored white
- Then colored gray when discovered
- Then black when finished
Time Stamp
- Discover time d[u]: when u is first discovered
- Finish time f[u]: when backtrack from u
- d[u] < f[u]
Application
- Topological Sort
- Strongly Connected Component
Soft computing is based on some biological induced methods such as genetics, development, ant ehavior, the warm of particles, the human nervous system, etc.
ReplyDeleteBest of Policy is committed to providing of best solutions to the customer amidst the very dynamic and highly competitive of the insurance market. With credible information and comprehensive knowledge that best suits your interest.
ReplyDeleteAlso read-Insurance