🖥️
Sunil Notebook
Interview Preparation
  • 📒Notebook
    • What is this about ?
  • System Design
    • 💡Key Concepts
      • 🌐Scalability
      • 🌐Latency Vs Throughput
      • 🌐Databases
      • 🌐CAP Theorem
      • 🌐ACID Transactions
      • 🌐Rate limiting
      • 🌐API Design
      • 🌐Strong Vs eventual consistency
      • 🌐Distributed tracing
      • 🌐Synchronous Vs asynchronous Communication
      • 🌐Batch Processing Vs Stream Processing
      • 🌐Fault Tolerance
    • 💎Building Blocks
      • 🔹Message
      • 🔹Cache
      • 🔹Load Balancer Vs API Gateway
    • 🖥️Introduction to system design
    • ⏱️Step By Step Guide
    • ♨️Emerging Technologies in System Design
    • ☑️System design component checklist
      • 🔷Azure
      • 🔶AWS
      • ♦️Google Cloud
    • 🧊LinkedIn feed Design
    • 🏏Scalable Emoji Broadcasting System - Hotstar
    • 💲UPI Payment System Design
    • 📈Stock Broker System Design - Groww
    • 🧑‍🤝‍🧑Designing Instagram's Collaborative Content Creation - Close Friends Only
    • 🌳Vending Machines - Over the air Systems
    • Reference Links
  • DSA
    • Topics
      • Introduction
      • Algorithm analysis
        • Asymptotic Notation
        • Memory
      • Sorting
        • Selection Sort
        • Insertion Sort
        • Merge Sort
        • Quick Sort
        • Quick'3 Sort
        • Shell Sort
        • Shuffle sort
        • Heap Sort
        • Arrays.sort()
        • Key Points
        • Problems
          • Reorder Log files
      • Stacks and Queues
        • Stack Implementations
        • Queue Implementations
        • Priority Queues
        • Problems
          • Dijkstra's two-stack algorithm
      • Binary Search Tree
        • Left Leaning Red Black Tree
          • Java Implementations
        • 2-3 Tree
          • Search Operation - 2-3 Tree
          • Insert Operation - 2-3 Tree
        • Geometric Applications of BST
      • B-Tree
      • Graphs
        • Undirected Graphs
        • Directed Graphs
        • Topological Sort
      • Union Find
        • Dynamic Connectivity
        • Quick Find - Eager Approach
        • Quick Find - Lazy Approach
        • Defects
        • Weighted Quick Union
        • Quick Union + path comparison
        • Amortized Analysis
      • Convex Hull
      • Binary Heaps and Priority Queue
      • Hash Table vs Binary Search Trees
  • Concurrency and Multithreading
    • Introduction
    • Visibility Problem
    • Interview Questions
    • References
      • System design
  • Design Patterns
    • ℹ️Introduction
    • 💠Classification of patterns
    • 1️⃣Structural Design Patterns
      • Adapter Design Pattern
      • Bridge Design Pattern
      • Composite Design Pattern
      • Decorator Design Pattern
      • Facade Design Pattern
      • Flyweight Design Pattern
      • Private Class Data Design Pattern
      • Proxy Design Pattern
    • 2️⃣Behavioral Design Patterns
      • Chain Of Responsibility
      • Command Design Pattern
      • Interpreter Design Pattern
      • Iterator Design Pattern
      • Mediator Design Pattern
      • Memento Design Pattern
      • Null Object Design Pattern
      • Observer Design Pattern
      • State Design Pattern
      • Strategy Design Pattern
      • Template Design Pattern
    • 3️⃣Creational Design Patterns
      • Abstract Factory Design Pattern
      • Builder Design Pattern
      • Factory Method Design Pattern
      • Object Pool Design Pattern
      • Prototype Design Pattern
      • Singleton Design Pattern
    • Java Pass by Value or Pass by Reference
  • Designing Data-Intensive Applications - O'Reilly
    • Read Me
    • 1️⃣Reliable, Scalable, and Maintainable Applications
      • Reliability
      • Scalability
      • Maintainability
      • References
    • 2️⃣Data Models and Query Languages
      • Read me
      • References
    • Miscellaneous
  • Preparation Manual
    • Disclaimer
    • What is it all about?
    • About a bunch of links
    • Before you start preparing
    • Algorithms and Coding
    • Concurrency and Multithreading
    • Programming Language and Fundementals
    • Best Practices and Experience
  • Web Applications
    • Typescript Guidelines
  • Research Papers
    • Research Papers
      • Real-Time Data Infrastructure at Uber
      • Scaling Memcache at Facebook
  • Interview Questions
    • Important links for preparation
    • Google Interview Questions
      • L4
        • Phone Interview Questions
      • L3
        • Interview Questions
      • Phone Screen Questions
  • Miscellaneous
    • 90 Days Preparation Schedule
    • My Preparation for Tech Giants
    • Top Product Based Companies
  • Links
    • Github
    • LinkedIn
Powered by GitBook
On this page
  • Glossary
  • Adjacency Matrix Representations
  • Adjacency List Representation
  • Java Implementation
  • Depth First Search
  • Algorithm
  • Java Implementation
  • Bredth First Search
  • Algorithm
  • Java Implementation
  • Connected Components
  • Algorithm
  • Java Implementation
  • Undirected Graph Applications

Was this helpful?

Edit on GitHub
  1. DSA
  2. Topics
  3. Graphs

Undirected Graphs

Glossary

  • A self-loop is an edge that connects a vertex to itself.

  • Two edges are parallel if they connect the same pair of vertices.

  • When an edge connects two vertices, we say that the vertices are adjacent to one another and that the edge is incident on both vertices.

  • The degree of a vertex is the number of edges incident on it.

  • A subgraph is a subset of a graph's edges (and associated vertices) that constitutes a graph.

  • A path in a graph is a sequence of vertices connected by edges, with no repeated edges.

  • A simple path is a path with no repeated vertices.

  • A cycle is a path (with at least one edge) whose first and last vertices are the same.

  • A simple cycle is a cycle with no repeated vertices (other than the requisite repetition of the first and last vertices).

  • The length of a path or a cycle is its number of edges.

  • We say that one vertex is connected to another if there exists a path that contains both of them.

  • A graph is connected if there is a path from every vertex to every other vertex.

  • A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs.

  • An acyclic graph is a graph with no cycles.

  • A tree is an acyclic connected graph.

  • A forest is a disjoint set of trees.

  • A spanning tree of a connected graph is a subgraph that contains all of that graph's vertices and is a single tree. A spanning forest of a graph is the union of the spanning trees of its connected components.

  • A bipartite graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.

Graph having two directions from any vertex in a path to another verted.

Adjacency Matrix Representations

Algorithm

Maintain a two dimensional v∗vv * vv∗v matrix boolean array

for each edge v−wv - wv−w in graph: adj[v][w]=adj[w][v]=trueadj[v][w] = adj[w][v] = trueadj[v][w]=adj[w][v]=true

Note: Adjacency matrix consumes more space.

  • Space Complexity : v2v^{2}v2

  • Add Edge: 1

  • Edge between vv vand www is 1

  • Iterate over vertices adjacent to vvv : VVV

Adjacency List Representation

In this representation , If there is path exists between any two vertices, vertices are added to vertex list.

Java Implementation

public class Graph {
  private final int V;
  private List<Integer>[] adj;

  public Graph(int v) {
    this.V = v;
    adj = new List[v];
    for (int i = 0; i < V; i++) {
      adj[i] = new ArrayList<>();
    }
  }

  public void addEdge(int v, int w) {
    adj[v].add(w);
    adj[w].add(v);
  }

  public Iterable<Integer> adj(int v) {
    return adj[v];
  }

  public static void main(String[] args) {}
}
  • Space Complexity : E+VE + VE+V

  • Add Edge: 1

  • Edge between vv vand www is degree(v)degree(v)degree(v)

  • Iterate over vertices adjacent to vvv - degree(v)degree(v)degree(v)

Depth First Search

Algorithm

To visit a vertex vvv :

  • Mark vertex vvv as visited.

  • Recursively visit all unmarked vertices adjacent to vvv.

Java Implementation

public class DepthFirstPaths
{
   // marked[v] = true if v connected to s
   private boolean[] marked;
   
   // edgeTo[v] = previous vertex on path from s to v
   private int[] edgeTo;
   private int s;
   
   public DepthFirstPaths(Graph G, int s)
   {
      // Initialize all the constructors
      ..............
      
      dfs(G, s); 
   }
      
   private void dfs(Graph G, int v)
   {
      marked[v] = true;
      for (int w : G.adj(v)){
         if (!marked[w])
         {
            dfs(G, w);
            edgeTo[w] = v;
         }
      }
   } 
   
   public boolean hasPathTo(int v)
   {  
      return marked[v];  
   }
   
   public Iterable<Integer> pathTo(int v)
   {
      if (!hasPathTo(v)) return null;
      Stack<Integer> path = new Stack<Integer>();
      for (int x = v; x != s; x = edgeTo[x])
         path.push(x);
      path.push(s);
      return path;
   }

}

Bredth First Search

Algorithm

Repeat until queue is empty

  • Remove vertex vvv from queue.

  • Add to queue all unmarked vertices adjacent to vvv and mark them.

Java Implementation

public class BreadthFirstPaths
{
   private boolean[] marked;
   private int[] edgeTo;
   
   private void bfs(Graph G, int s)
   {
      
 Queue<Integer> q = new Queue<Integer>();
       q.enqueue(s);
       marked[s] = true;
       while (!q.isEmpty())
       {
          int v = q.dequeue();
          for (int w : G.adj(v))
          {
             if (!marked[w])
             {
                q.enqueue(w);
                marked[w] = true;
                edgeTo[w] = v;
             } 
          }
       }
   }
 }

Connected Components

A connected component is a maximal set of connected vertices.

Algorithm

To visit a vertex v :

  • Mark vertex v as visited.

  • Recursively visit all unmarked vertices adjacent to v.

Java Implementation

public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    
    public CC(Graph G){
        marked = new boolean[G.V()];
        id = new int[G.V()];
        
        for(int i=0;i<G.V();i++){
            if(!marked[i])
            {
                dfs(G, i);
                 count++;
            }
        }
    }
    
    public int count()
    {  
        return count;  
    }
    
    public int id(int v)
    {  
        return id[v];  
    }
    
    // All vertices discovered in same call of dfs have same id
    private void dfs(Graph G, int v)
    {
       marked[v] = true;
       id[v] = count;
       for (int w : G.adj(v))
          if (!marked[w])
              dfs(G, w);
    }
}

Undirected Graph Applications

PreviousGraphsNextDirected Graphs

Last updated 3 years ago

Was this helpful?

Representation of undirected Graph
Adjacency Matrix representation
Connected Components