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)

Adjacency List/Set (Map<Node, HashSet>)

AdjacencyList uses a LinkedLi st instead of Set thus increasing the complexity

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