Graphs

less than 1 minute read

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