1. Undirected Graphs
Main points
- A variety of fundamental graph algorithms.
- Some basic graph theory
To do research in graph, there is always have a question to be solved that Is vertex v connected to w? or Is this graph connected? we begin in algorithm Depth First Search which may solve this question in an intuitive way.
“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.” 1
Java implementation of DFS [2]
1 |
public class () |
C++ implementation of DFS
1 |
|
BFS
definiton of BFS:
Java implementation of BFS [3]
1 |
|
C++ implementation of BFS
1 |
|
References
- Depth-first search. Retrieved April 10th, 2019, from: WIKIPEDIA https://en.wikipedia.org/wiki/Depth-first_search
- Robert Sedgewick & Kevin Wayne. (2016). Algorithms (4th Edition) (pp. 531).
近期评论