11 Graphs Flashcards
Dense Graphs
If E is around V^2
Sparse Graphs
If E is Around V
How must storage does Adjacency lists take?
O(V+E)
Two Approaches to Graph Tranversal
Breadth-first
Depth-first Traversal
Breadth-First Search
Find shortest paths in graph
Depth-First Search
Discover various structural properties of graph
Total Running Time of DFS
Big Theta (V+E)
Forest
An acyclic graph G that may be disconnected.
Tree Edge
Found by exploring (u, v).
Back Edge
Where u is a descendant of v
Forward Edge
Where v is a descendant of u.
Cross Edge
Any other edge. Can go between vertices in same depth-first tree or in different depth-first trees.
In DFS of an undirected graph, we get:
Only tree and back edges. No forward or cross edges.
A graph is acyclic if :
a DFS yeilds no back edges.
How to find whether a graph has a cycle or not?
Run DFS