Graph

• Graph is a data structure that is like a network. (Non-Linear)
• Applications:
  • Shortest Paths in Google Maps
  • Social Networking
  • Circuit Design
  • Routing Algorithms
  • Resolving Dependencies
  • Graphs in Deep Learning
  • Web Document (DOM Tree)
  • Image Processing and Segmentation

---

Graphs Representation

1. 2D Array (Adjacency Matrix)

   • Directed egde
   • Undirected edge (Bidirected edge)
   • Advantages:
     • Searching: O(1)
   • Disadvantages:
     • To store all the edges it will take O(n^2).
     • Finding neighbours will take O(n) time.

2. Edge List (Edges and Vertices)

3. Adjacency List

   • Advantage:
     • Neighbours: O(neighbours) [Quite Fast]
     • Memory Efficient

4. Implicit Graph

Maximum edges: NC2

Minimum edges: 0

Minimum edges(connected graph): (N-1)edges (Example: tree)

---

Adjacency List Representation

• Array of list of size V
• For integer data.
• For generic data

---

Graph Traversal

1. Breadth First Search

   • Iterative way.
   • Level order Traversal.
   • Implemented using a queue and an array(to mark visited).

   • Single Source Shortest Path Using BFS.

   • Snake and Ladder Using BFS.

2. Depth First Search

   • Recursive way.
   • Implemented using a queue and an array(to mark visited).

   • Connected components using DFS

---

Directed acyclic graph

• Topological sort using DFS
• Topological sort using BFS
  • Indegree: Number of incoming edges.
  • Outdegree: Number of outgoing edges.
  • We can start with indegree of 0.

---

Undirected graph is a tree or not

Given an undirected graph, check if it is a tree or not.

• If the graph contains a cycle it is not a tree.
• If we are visiting a node more than one time, cycle is present. (Also check that the node is not the parent of the element).

• Cycle detection using DFS.

• Cycle detection using BFS.

---

Cycle detection in directed graph

Check for cycle in directed graph.

• If a graph has back edge, it contains cycle.
• We can maintain a stack(for path traversed, but implemented as array to make look up possible at O(1)) and a visited array.
• Using DFS.

---

Flood Fill Algorithm

• A simple variant of BFS/DFS that can be used to label(color) the various connected components present in a graph.
• It is generally performed on implicit graphs (2d matrices).
• Starting from a particular cell, we call DFS on the neighbouring cell to color them.

---

Dijkstra Algorithm

• An alogrithm that helps us to find the shortest path on the weighted graph.
• No negative weight cycle.
• Single source shortest path. (SSSP)
• Initially all the nodes have let infinite distance.
• Pick the node with minimum given weight. (use a priority queue or set, but since we can't update in a priority queue we will prefer set).

---

Disjoint Set Data Structure and Union Find Algo

Cycle detection using DSU

• If we add an edge within the connected components there will be cycle.

---

Kruskal's Concept (Minimum spanning tree)

• A spanning tree is a tree of graph that connects the graph into one connected components withput any cycle.
• A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
• Steps:
  • Sort all the edges according to their weights.
  • Add the edge in the graph such that it forms no cycle. (Greedy :P)

---

Prim's Concept (Minimum spanning tree)

• Active edge: If an edge is an active edge, then either of one vertex is a MST vertex. (points MST vertex to a non MST vertex).
• MST edge: Edge that is included in the MST.
• MST vertex: Vertex that is included in the MST.
• Prim's algorithm is greedy algorithm and similar to Dijkstra's.
• Steps: (We can make a priority queue for better time complexity).
  • Select source vertex (any vertex from the graph). (x)
  • Out of all the active edges choose the one with the smallest weight.(x---y) x:MST vertex, y: non MST vertex
  • Make all edges of y to be active edges.
  • Repeat steps 2 and 3.

---

Bellman Ford Algorithm

• Single source shortest path algorithm.
• Also handles negative weight edges.
• Why not Dijkstra? Because dijkstra works for only positive weighted edge.
• Directed graph, because if there'll be undirected graph then for negative weight it will creat a negative weight cycle.
• It works in a dynamic programming way.
• Relaxing the edge.
• Steps:
  • 1. dist[src]=0
       • dist[other]=inf
  • 2. relax all edges. (n-1) times
       • rep (n-1) ---> O(n-1)
       • rep (m) ---> O(m)
       • relax (u,v) ---> O(1)
  • 3. Check if we can relax an edge any furhter.
       • If yes, it contains a negative edge cycle.

---

Floyd-Warshall Algorithm

• Used to find shortest path between all pairs of vertcies (directed as well as undirected)
• Will work even if negative edges are present.
• Will also be able to detect negative cycles.
• Time complexity: O(V^3)
• Space complexity: O(V^2)

---

Travelling salesman problem

• DP with bitmasking (Top down)
• Hamiltonian cycle: Set of edges such that every node is visited once and reach back to starting node.
• This que will be a min weight Hamiltonian cycle.
• Brute force: Generate all n fact. of the given node and try to find the path of the cycle. O(n!)

---

Strongly connected components (Kosaraju's algorithm)

• Strongly conencted graph: Directed graph such that each of it's vertices can be visited from other vertices. (There is a path between every two vertices).
• If we can go from source to sink, and then reverse the graph and again go from source to sink then it is a strongly connected components.