Graph
Concept
How to avoid CYCLE while we are traversing the graph? Create a container to store visited elements.
An undirected graph is acyclic iff a DFS yields no back edges.
Deep Copy
A new oject is created without referencing the old one.
The copying process executes recursively.
Using "new" to deep copy every element.
![](images/shallow_cp.png)
(The above image is from http://en.wikipedia.org.)
Represent a graph
Adjacent List
save more space than adj matrix
Adjacent Matrix
Approach1: DFS
Time Complexity: O(N), where N is the number of nodes in the given graph.
Space Complexity: O(N), where N is the size of visited map. The stack would need O(H), where H is the maximum height of the graph. However, H <= N, overall, space complexity is O(N).
Approach2: BFS + queue
Time Complexity: O(N), where N is the number of nodes in the given graph.
Space Complexity: O(N), where N is the size of visited map. The queue would need O(W), where W is the maximum width of the graph. However, W <= N, overall, space complexity is O(N).
Template - BFS in exploring graph
time complexity: O(V+E)
space complexity: O(E)
![](images/bfs_graph.png)
(The above image is from ASU SER501.)
![](images/bfs_graph_demo.png)
(The above image is from ASU SER501.)
Template - DFS in exploring graph
time complexity: O(V+E)
space complexity: O(V+E)
![](images/dfs_graph.png)
(The above image is from ASU SER501.)
![](images/dfs_graph_demo.png)
(The above image is from ASU SER501.)
![](images/dfs_graph_edges.png)
(The above image is from ASU SER501.)
[Hard] No.1192 Critical Connections in a Network
Approach: DFS
Time Complexity: O(V+E), where V is the number of vertex in the given graph, E is the numbers of the given graph.
Space Complexity: O(V+E)
Topological Sorting
Key concept: execute the node which doesn't have an incoming edge.
Time complexity: O(V+E), V is total vertices, E is total edges.
Tsort is for DAG(directed Acyclic Graph). Example in real life is dressing clothes.
May not have a unique answer.
![](images/tsort_example.png)
(The above image is from wikipedia.org.)
Famous algorithm to implement tsort. Kahn's algo, DFS, Parallel algo.
Approach1 : BFS + indegree map + outdegree map
Approach2 : DFS + outdegree map