🖥️
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

Note: Adjacency matrix consumes more space.

  • Add Edge: 1

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) {}
}
  • Add Edge: 1

Depth First Search

Algorithm

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

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?

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

Space Complexity : v2v^{2}v2

Edge between vv vand www is 1

Iterate over vertices adjacent to vvv : VVV

Space Complexity : E+VE + VE+V

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

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

To visit a vertex vvv :

Mark vertex vvv as visited.

Recursively visit all unmarked vertices adjacent to vvv.

Remove vertex vvv from queue.

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

Representation of undirected Graph
Adjacency Matrix representation
Connected Components