Manav Goyal

Graph - C P P

  • Graph
    • A data structure made with combination of Nodes & Edges
  • Nodes => These are states or vertex, Entity to store data
    • Weighted nodes => Values are associated with nodes
    • Weighted edges => Values are associated with edges
  • Edges => Links between Nodes
    • Undirected => Two way
    • Directed => One way
  • Degree of a vertex
    • Indegree => Number of incoming edges to a node
    • Outdegree => Number of outgoing edges from a node
  • Vertices
    • Adjacent vertices => Two vertices with a direct edge connecting them
    • Path between 2 vertices => All vertices which come in path of two given vertices
  • Classification
    • Cycles in a graph => Path from a vertex to the same vertex
    • Cyclic Graph => Path forming a circle
    • Acyclic Graph => No Path forming a circle
    • Directed Acyclic Graph (DAG)
    • Connected graph => Each node has path from every other node
    • Disconnected graph
    • Connected Components => Each connected graph in a disconnected graph
    • Complete Graph => Each vertex is connected to every other vertex by a direct edge => Number of edge = nC2
    • Bipartite Graph => The graph is 2 colorable or it does not contain any odd-length cycles
  • Representation
    • Adjacency Matrix
      • Implementation using 2-D Array
    • Adjacency List
      • Implementation using map<dataType, list<dataType>> or vector<vector<int>>
  • Search
    • Breath First Search
      • Implemented using Queue
      • Traversing adjacent matrix first
      • Time/Space Complexity = O(V+E)
      • Equal to Levelorder in case of trees
    • Depth First Search
      • Implemented using Stack or Recursion
      • Time/Space Complexity = O(V+E)
      • Equal to Preorder in case of trees
      • Types
        • Preorder
        • Inorder
        • Postorder
  • Topological Sort
    • It is a linear ordering of vertices such that for every edge u to v, u always appearers before v
    • Applicable in DAG
    • Using DFS or Kahn's Algorithm (BFS)
    • Time Complexity = O(V+E)
    • Space Complexity = O(V)
  • Shortest Path
    • Dijkstra's Algorithm
    • Bellman Ford Algorithm
      • Can apply on Directed graph containing negative weights without negative cycles
      • Time Complexity = O(N*E)
  • Disjoint Set Union (DSU)
    • Leading Element / Parent
      • Element which is regarded as the leader element for that set
    • Operations
      • findParent() & unionSet()
    • Methods
      • Union by Size / Rank
        • Join lower rank node with higher rank node
      • Path Compression
        • Join set directly with its parent
  • Spanning Tree
    • When you convert a graph into a tree such that it contains n nodes and n-1 edges & every node is reachable by every other node
    • Minimum Spanning Tree
      • Minimum Cost / Weight
      • Algorithms
        • Prim's Algorithm
          • Time Complexity = O(nlogn)
        • Kruskal's Algorithm
          • Time Complexity = O(nlogn)
          • Space Complexity = O(n)
    • Cost of Spanning Tree = Sum of Weight of Edges
  • Bridge
    • That edge if remove will increase the number of connected components
    • Tarjan's Algorithm
      • Back Edge => Edge through which we reach a visited node but not parent
  • Articulation point
    • Node / Point if removed divides the graph into more than equal to 2 components
  • Strongly Connected Components
    • A component of a graph where you can reach any node from any other node
    • Kosaraju's Algorithm
Share: