Graphs
Directed Graph
Model a Graph using
- Adjancy Matrix (2D array of $$ V\times V $$)
- Adjacency List/Set/Map (weighted Graph)
Unweighted graph
- Adjacency List or set of neighbors
Weighted graph
- Each entry keeps track of neighbor and weight
- Easy to implement with maps
– Map of Maps (using HashMaps for efficiency)
Heap as a Priority Queue in java
Topological Ordering (Sort)
- In DAG (no cycles in Graph), it is a linear ordering of vertices such that for every directed (u -> v) edge u comes before v in the ordering
- Yields a valid sequence of the tasks.
- Any directed acyclic graph(DAG) has at least one topological order
- O(V+E) linear running time complexity
- Crucial in Project dependency management and Hamiltonian path(visits each vertex exactly once).
- a Hamiltonian path exits then the topological sort order is unique
- if a topological sort does not form a Hamiltonian path it means the DAG has more valid topological orderings
- Finding Hamiltonian path is NP-complete problem but we can decide whether such path exists in O(V+E) runing time with topological sort