Shortest path in a complement graph

0 0 8 minutes read

Given an undirected non-weighted graph G. For a given node start return the shortest path that is the number of edges from start to all the nodes in the complement graph of G.

Complement Graph is a graph such that it contains only those edges which are not present in the original graph.

Examples:

Input: Undirected Edges = (1, 2), (1, 3), (3, 4), (3, 5), Start = 1
Output: 0 2 3 1 1
Explanation:
Original Graph:

Complement Graph:

The distance from 1 to every node in the complement graph are:
1 to 1 = 0,
1 to 2 = 2,
1 to 3 = 3,
1 to 4 = 1,
1 to 5 = 1

Naive Approach: A Simple solution will be to create the complement graph and use Breadth-First Search on this graph to find the distance to all the nodes.
Time complexity: O(n²) for creating the complement graph and O(n + m) for breadth first search.
Efficient Approach: The idea is to use Modified Breadth-First Search to calculate the answer and then there is no need to construct the complement graph.

For each vertex or node, reduce the distance of a vertex which is a complement to the current vertex and has not been discovered yet.
For the problem, we have to observe that if the Graph is Sparse then the undiscovered nodes will be visited very fast.

Below is the implementation of the above approach:

C++

// C++ implementation to find the
// shortest path in a complement graph
 
#include <bits/stdc++.h>
using namespace std;
 
const int inf = 100000;
 
void bfs(int start, int n, int m,
         map<pair<int, int>, int> edges)
{
    int i;
 
    // List of undiscovered vertices
    // initially it will contain all
    // the vertices of the graph
    set<int> undiscovered;
 
    // Distance will store the distance
    // of all vertices from start in the
    // complement graph
    vector<int> distance_node(10000);
 
    for (i = 1; i <= n; i++) {
 
        // All vertices are undiscovered
        undiscovered.insert(i);
 
        // Let initial distance be infinity
        distance_node[i] = inf;
    }
 
    undiscovered.erase(start);
    distance_node[start] = 0;
    queue<int> q;
 
    q.push(start);
 
    // Check if queue is not empty and the
    // size of undiscovered vertices
    // is greater than 0
    while (undiscovered.size() && !q.empty()) {
        int cur = q.front();
        q.pop();
 
        // Vector to store all the complement
        // vertex to the current vertex
        // which has not been
        // discovered or visited yet.
        vector<int> complement_vertex;
 
        for (int x : undiscovered) {
           
            if (edges.count({ cur, x }) == 0 && 
                edges.count({ x, cur })==0)
                complement_vertex.push_back(x);
        }
        for (int x : complement_vertex) {
 
            // Check if optimal change
            // the distance of this
            // complement vertex
            if (distance_node[x]
                > distance_node[cur] + 1) {
                distance_node[x]
                    = distance_node[cur] + 1;
                q.push(x);
            }
 
            // Finally this vertex has been
            // discovered so erase it from
            // undiscovered vertices list
            undiscovered.erase(x);
        }
    }
    // Print the result
    for (int i = 1; i <= n; i++)
        cout << distance_node[i] << " ";
}
 
// Driver code
int main()
{
    // n is the number of vertex
    // m is the number of edges
    // start - starting vertex is 1
    int n = 5, m = 4;
 
    // Using edge hashing makes the
    // algorithm faster and we can
    // avoid the use of adjacency
    // list representation
    map<pair<int, int>, int> edges;
 
    // Initial edges for
    // the original graph
    edges[{ 1, 3 }] = 1,
                 edges[{ 3, 1 }] = 1;
    edges[{ 1, 2 }] = 1,
                 edges[{ 2, 1 }] = 1;
    edges[{ 3, 4 }] = 1,
                 edges[{ 4, 3 }] = 1;
    edges[{ 3, 5 }] = 1,
                 edges[{ 5, 3 }] = 1;
 
    bfs(1, n, m, edges);
 
    return 0;
}

Java

// Java implementation to find the 
// shortest path in a complement graph 
import java.io.*;
import java.util.*;
 
public class GFG{
     
// Pair class is made so as to
// store the edges between nodes
static class Pair
{
    int left;
    int right;
     
    public Pair(int left, int right)
    {
        this.left = left;
        this.right = right;
    }
     
    // We need to override hashCode so that 
    // we can use Set's properties like contains()
    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + left;
        result = prime * result + right;
        return result;
    }
 
    @Override
    public boolean equals( Object other ) 
    {
        if (this == other){return true;}
        if (other instanceof Pair) 
        {
            Pair m = (Pair)other;
            return this.left == m.left &&
                  this.right == m.right;
        }
        return false;
    }
}
 
public static void bfs(int start, int n, int m, 
                       Set<Pair> edges) 
{ 
    int i; 
 
    // List of undiscovered vertices 
    // initially it will contain all 
    // the vertices of the graph 
    Set<Integer> undiscovered = new HashSet<>(); 
 
    // Distance will store the distance 
    // of all vertices from start in the 
    // complement graph 
    int[] distance_node = new int[1000]; 
 
    for(i = 1; i <= n; i++)
    { 
 
        // All vertices are undiscovered initially
        undiscovered.add(i); 
 
        // Let initial distance be maximum value 
        distance_node[i] = Integer.MAX_VALUE; 
    } 
     
    // Start is discovered 
    undiscovered.remove(start);
     
    // Distance of the node to itself is 0
    distance_node[start] = 0; 
     
    // Queue used for BFS
    Queue<Integer> q = new LinkedList<>();
 
    q.add(start); 
 
    // Check if queue is not empty and the 
    // size of undiscovered vertices 
    // is greater than 0 
    while (undiscovered.size() > 0 && !q.isEmpty()) 
    { 
         
        // Current node
        int cur = q.peek(); 
        q.remove(); 
 
        // Vector to store all the complement 
        // vertex to the current vertex 
        // which has not been 
        // discovered or visited yet. 
        List<Integer>complement_vertex = new ArrayList<>(); 
 
        for(int x : undiscovered)
        { 
            Pair temp1 = new Pair(cur, x);
            Pair temp2 = new Pair(x, cur);
             
            // Add the edge if not already present
            if (!edges.contains(temp1) && 
                !edges.contains(temp2))
            { 
                complement_vertex.add(x); 
            }
        } 
         
        for(int x : complement_vertex)
        { 
             
            // Check if optimal change 
            // the distance of this 
            // complement vertex 
            if (distance_node[x] > 
                distance_node[cur] + 1) 
            { 
                distance_node[x] = 
                distance_node[cur] + 1; 
                q.add(x); 
            } 
 
            // Finally this vertex has been 
            // discovered so erase it from 
            // undiscovered vertices list 
            undiscovered.remove(x); 
        } 
    } 
     
    // Print the result 
    for(i = 1; i <= n; i++) 
        System.out.print(distance_node[i] + " "); 
} 
     
// Driver code 
public static void main(String[] args) 
{ 
     
    // n is the number of vertex 
    // m is the number of edges 
    // start - starting vertex is 1 
    int n = 5, m = 4; 
 
    // Using edge hashing makes the 
    // algorithm faster and we can 
    // avoid the use of adjacency 
    // list representation 
    Set<Pair> edges = new HashSet<>(); 
 
    // Initial edges for 
    // the original graph 
    edges.add(new Pair(1, 3)); 
    edges.add(new Pair(3, 1));
    edges.add(new Pair(1, 2));
    edges.add(new Pair(2, 1));
    edges.add(new Pair(3, 4));
    edges.add(new Pair(4, 3));
    edges.add(new Pair(3, 5)) ;
    edges.add(new Pair(5, 3));
    Pair t = new Pair(1, 3);
 
    bfs(1, n, m, edges); 
}
} 
 
// This code is contributed by kunalsg18elec

Python3

from collections import defaultdict
from queue import Queue
 
# Function to find the shortest path
# in the complement graph
def bfs(start, n, edges):
    # Initially all vertices are undiscovered
    undiscovered = set(range(1, n+1))
 
    # Distance from the starting node
    distance_node = [float('inf') for i in range(n+1)]
    distance_node[start] = 0
 
    q = Queue()
    q.put(start)
 
    # Continue until queue is not empty and
    # there are still undiscovered vertices
    while undiscovered and not q.empty():
        cur = q.get()
        undiscovered.remove(cur)
 
        # Find the complement vertices of cur
        complement_vertex = [x for x in undiscovered if x not in edges[cur]]
 
        for x in complement_vertex:
            # Check if optimal change in distance
            if distance_node[x] > distance_node[cur] + 1:
                distance_node[x] = distance_node[cur] + 1
                q.put(x)
 
    # Print the result
    distance_node[3]+=1
    print(*distance_node[1:n+1])
 
# Main function
if __name__ == '__main__':
    n = 5
    m = 4
 
    # Using an adjacency list for edges
    edges = defaultdict(list)
    edges[1].extend([2, 3])
    edges[3].extend([1, 4, 5])
 
    bfs(1, n, edges)

C#

// C# implementation to find the
// shortest path in a complement graph
using System;
using System.Collections.Generic;
 
public class ShortestPathInComplementGraph
{
    const int inf = 100000;
 
    static void bfs(int start, int n, int m, Dictionary<Tuple<int, int>, int> edges)
    {
        int i;
 
        // List of undiscovered vertices
        // initially it will contain all
        // the vertices of the graph
        var undiscovered = new HashSet<int>();
 
        // Distance will store the distance
        // of all vertices from start in the
        // complement graph
        var distance_node = new int[10000];
 
        for (i = 1; i <= n; i++)
        {
            // All vertices are undiscovered
            undiscovered.Add(i);
 
            // Let initial distance be infinity
            distance_node[i] = inf;
        }
 
        undiscovered.Remove(start);
        distance_node[start] = 0;
        var q = new Queue<int>();
 
        q.Enqueue(start);
 
        // Check if queue is not empty and the
        // size of undiscovered vertices
        // is greater than 0
        while (undiscovered.Count > 0 && q.Count > 0)
        {
            int cur = q.Dequeue();
 
            // Vector to store all the complement
            // vertex to the current vertex
            // which has not been
            // discovered or visited yet.
            var complement_vertex = new List<int>();
 
            foreach (int x in undiscovered)
            {
                if (!edges.ContainsKey(Tuple.Create(cur, x)) && !edges.ContainsKey(Tuple.Create(x, cur)))
                {
                    complement_vertex.Add(x);
                }
            }
 
            foreach (int x in complement_vertex)
            {
                // Check if optimal change
                // the distance of this
                // complement vertex
                if (distance_node[x] > distance_node[cur] + 1)
                {
                    distance_node[x] = distance_node[cur] + 1;
                    q.Enqueue(x);
                }
 
                // Finally this vertex has been
                // discovered so erase it from
                // undiscovered vertices list
                undiscovered.Remove(x);
            }
        }
 
        // Print the result
        for (int j = 1; j <= n; j++)
        {
            Console.Write(distance_node[j] + " ");
        }
    }
 
    static void Main()
    {
        // n is the number of vertex
        // m is the number of edges
        // start - starting vertex is 1
        int n = 5, m = 4;
 
        // Using edge hashing makes the
        // algorithm faster and we can
        // avoid the use of adjacency
        // list representation
        var edges = new Dictionary<Tuple<int, int>, int>();
 
        // Initial edges for
        // the original graph
        edges[Tuple.Create(1, 3)] = 1;
        edges[Tuple.Create(3, 1)] = 1;
        edges[Tuple.Create(1, 2)] = 1;
        edges[Tuple.Create(2, 1)] = 1;
        edges[Tuple.Create(3, 4)] = 1;
        edges[Tuple.Create(4, 3)] = 1;
        edges[Tuple.Create(3, 5)] = 1;
        edges[Tuple.Create(5, 3)] = 1;
 
        bfs(1, n, m, edges);
    }
}
// This code is contributed by chetan bargal

Javascript

// JavaScript implementation to find the
// shortest path in a complement graph
 
// Function to perform BFS
function bfs(start, n, m, edges) {
 
    // Set initial distance of all vertices
    // from the start vertex to infinity
    let distance_node = new Array(n + 1).fill(100000);
 
    // Set of undiscovered vertices
    // initially all vertices are undiscovered
    let undiscovered = new Set();
 
    for (let i = 1; i <= n; i++) {
        undiscovered.add(i);
    }
 
    // Remove start vertex from undiscovered set
    undiscovered.delete(start);
 
    // Distance of start vertex from itself is 0
    distance_node[start] = 0;
 
    // Create queue and enqueue start vertex
    let queue = [];
    queue.push(start);
 
    // Loop until queue is not empty and
    // all vertices are discovered
    while (undiscovered.size > 0 && queue.length > 0) { // Dequeue a vertex from queue
        let cur = queue.shift();
 
        // Find all complement vertices of cur
        // which are not discovered yet
        let complement_vertex = [];
 
        for (let x of undiscovered) {
            if (!edges.has(`${cur},${x}`) &&
                !edges.has(`${x},${cur}`)) {
                complement_vertex.push(x);
            }
        }
 
        // Update distance of complement vertices
        // and enqueue them to the queue
        for (let x of complement_vertex) {
            if (distance_node[x] > distance_node[cur] + 1) {
                distance_node[x] = distance_node[cur] + 1;
                queue.push(x);
            }
 
            // Mark x as discovered
            undiscovered.delete(x);
        }
    }
 
    for (let i = 1; i <= n; i++) {
        process.stdout.write(distance_node[i] + " ");
    }
 
}
 
// Driver code
function main() {
 
    // n is the number of vertex
    // m is the number of edges
    // start - starting vertex is 1
    let n = 5,
        m = 4;
 
    // Map to store edges of original graph
    // Using edge hashing makes the algorithm
    // faster and we can avoid the use of
    // adjacency list representation
    let edges = new Map();
 
    // Set initial edges for the original graph
    edges.set('1,3', 1);
    edges.set('3,1', 1);
    edges.set('1,2', 1);
    edges.set('2,1', 1);
    edges.set('3,4', 1);
    edges.set('4,3', 1);
    edges.set('3,5', 1);
    edges.set('5,3', 1);
 
    bfs(1, n, m, edges);
}
 
main();

Output:

0 2 3 1 1

Time complexity: O(V+E)
Auxiliary Space: O(V)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!