Home - kumarpranav1987/Graph GitHub Wiki

Graph Implementation

  • Adjacency List.
  • Adjacency Matrix.

Graph Traversal

  • BFS
  • DFS

Undirected Graph

  • Every edge appears twice in Adjacency List. Edge v-w will appear in v's adjacency and w's adjacency.

Connected Component

  • Find the Number of connected components in an undirected graph. (BFS/DFS/Union Find Can be used to do this)
  • In the Directed graph the equivalent Concept is Strongly Connected Component.(Kosarajus Algorithm)

Weighted Graph

Equal Weighted Graph

General Weighted Graph

Minimum Spanning Tree

  • The minimum spanning tree of a graph is unique if all m edge weights in the graph are distinct. Otherwise the order in which Prim’s/Kruskal’s algorithm breaks ties determines which minimum spanning tree is returned.