Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Using Sets
4.1.
C++ Code
4.2.
Java Code
4.3.
Output
5.
Using Hash
5.1.
C++ Code
5.2.
Output
6.
Complexities
6.1.
Time complexity 
6.2.
Space complexity
7.
Frequently Asked Questions
7.1.
What is the graph's set representation?
7.2.
What is the load factor of a hash table?
7.3.
What technique is employed to depict a graph in relation?
7.4.
What do you mean by depth of a vertex?
7.5.
What memory representation does a graph have?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Representing a Graph using Set and Hash

Author Manan Singhal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

A graph is a type of non-linear data structure that can be defined as a group of vertices where edges help to connect these vertices. Graphs can be classified as directed, undirected, weighted, unweighted, cyclic, acyclic, etc.

In the article, we will look at one of the popular implementations in a graph representing a graph using sets and hash.

Problem Statement

In this problem, we need to find all the vertex adjacent to the particular vertex. Assume a vertex v we need to find all the adjacent or neighbor vertex of this given vertex v. We can find out all the adjacent vertex have a standard edge.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Input

Example

Output

Adjacency List of vertex: 0
3 2 1

Adjacency List of vertex: 1
2 0 

Adjacency List of vertex: 2
1 0 

Adjacency List of vertex: 3
4 0 

Adjacency List of vertex: 4
3

Explanation

  1. For vertex: 0, we see three edge passes to vertex 1, 2, and 3.
  2. For vertex: 1, we can see a total of 2 edge passes to vertex 0 and 2.

 

Let’s start with the implementation of the code using set and hash.

Implementation

Using Sets

A set differs from a vector in two ways: duplicate elements are not permitted and keep elements ordered. As a result, this method cannot be applied to graphs with parallel edges. An edge between two vertices can be searched in O(log V) time because sets are internally implemented as binary search trees. Python sets are not indexed and are not ordered. Therefore, for Python, we will use a dictionary where the source vertex serves as the key, and the adjacency list is kept as the value for that key in a set format.

C++ Code

/* C++ program: Graph representations using set and hash */
#include <bits/stdc++.h>

using namespace std;

struct Graph {
	int vertices;
	set<int, greater<int>>* adjList;
};

/* this function creates a graph with 'vertices' vertices */
Graph* createGraphWithVertices(int vertices) {
    
	Graph* graph = new Graph;
	graph->vertices = vertices;
	graph->adjList = new set<int, greater<int> >[vertices];

	return graph;
}

/* this function created/adds an edge to the created graph */
void addEdgeToGraph(Graph* graph, int source, int destination) {

	/* adding edge from source to destination */
	graph->adjList[source].insert(destination);

	/* adding edge from destination to source */
	graph->adjList[destination].insert(source);
}

/* this function prints the adjList of a graph */
void printGraph(Graph* graph) {
    
	for (int i = 0; i<graph->vertices; ++i) {
		set<int, greater<int>> lst = graph->adjList[i];
		cout << endl << "Adjacency List of vertex: " << i << endl;

		for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
			cout << *itr << " ";
		}
		cout << endl;
	}
}

/* this function search for the given edge */
void searchEdgeInGraph(Graph* graph, int source, int destination) {
    
	auto itr = graph->adjList[source].find(destination);
	if (itr == graph->adjList[source].end()) {
		cout << endl << "Edge from " << source << " to " << destination << " not found." << endl;
	}
	else {
		cout << endl << "Edge from " << source << " to " << destination << " found." << endl;    
	}
}

/* Main Program */
int main() {
    
	/* Creating a graph as shown in the above figure */
	int vertices = 5;
	struct Graph* graph = createGraphWithVertices(vertices);

	addEdgeToGraph(graph, 0, 2);
	addEdgeToGraph(graph, 0, 3);
	addEdgeToGraph(graph, 1, 0);
	addEdgeToGraph(graph, 2, 1);
	addEdgeToGraph(graph, 3, 4);

	printGraph(graph);

	/* searching for the given edge */
	searchEdgeInGraph(graph, 2, 0);
	searchEdgeInGraph(graph, 1, 0);
	searchEdgeInGraph(graph, 1, 3);

	return 0;
}

Java Code

/* Java program: Graph representations using set and hash */
import java.util.*;

class Main {

    HashMap < Integer, TreeSet < Integer >> graph;
    static int vertices;

    /* this function creates a graph with 'vertices' vertices */
    public Main() {
        graph = new HashMap < > ();
        for (int i = 0; i < vertices; i++) {
            graph.put(i, new TreeSet < > ());
        }
    }

    /* this function created/adds an edge to the created graph */
    public void addEdgeToGraph(int source, int destination) {

        /* adding edge from source to destination */
        graph.get(source).add(destination);

        /* adding edge from destination to source */
        graph.get(destination).add(source);
    }

    /* this function prints the adjList of a graph */
    public void printGraph() {

        for (int i = 0; i < vertices; i++) {
            System.out.println("Adjacency List of vertex: " + i);
            Iterator set = graph.get(i).iterator();

            while (set.hasNext()) {
                System.out.print(set.next() + " ");
            }

            System.out.println();
            System.out.println();
        }
    }

    /* this function search for the given edge */
    public void searchEdgeInGraph(int source, int destination) {

        Iterator set = graph.get(source).iterator();

        if (graph.get(source).contains(destination)) {
            System.out.println("Edge from " + source + " to " + destination + " found");
        } else {
            System.out.println("Edge from " + source + " to " + destination + " not found");
        }

        System.out.println();
    }

    /* Main Program */
    public static void main(String[] args) {

        /* Creating a graph as shown in the above figure */
        vertices = 5;
        Main graph = new Main();

        graph.addEdgeToGraph(0, 2);
        graph.addEdgeToGraph(0, 3);
        graph.addEdgeToGraph(1, 0);
        graph.addEdgeToGraph(2, 1);
        graph.addEdgeToGraph(3, 4);

        graph.printGraph();

        /* searching for the given edge */
        graph.searchEdgeInGraph(2, 0);
        graph.searchEdgeInGraph(1, 0);
        graph.searchEdgeInGraph(1, 3);
    }
}

Output

Adjacency List of vertex: 0
3 2 1 

Adjacency List of vertex: 1
2 0 

Adjacency List of vertex: 2
1 0 

Adjacency List of vertex: 3
4 0 

Adjacency List of vertex: 4
3 

Edge from 2 to 0 found.

Edge from 1 to 0 found.

Edge from 1 to 3 not found.
Coding


Using Hash

We can optimize edge search operation to O(1) using unordered_set which uses hashing internally.

C++ Code

/* C++ program: Graph representations using set and hash */
#include <bits/stdc++.h>

using namespace std;

struct Graph {
	int vertices;
	unordered_set<int>* adjList;
};

/* this function creates a graph with 'vertices' vertices */
Graph* createGraphWithVertices(int vertices) {
	Graph* graph = new Graph;
	graph->vertices = vertices;
	graph->adjList = new unordered_set<int>[vertices];

	return graph;
}

/* this function created/adds an edge to the created graph */
void addEdgeToGraph(Graph* graph, int source, int destination) {

	/* adding edge from source to destination */
	graph->adjList[source].insert(destination);

	/* adding edge from destination to source */
	graph->adjList[destination].insert(source);
}

/* this function prints the adjList of a graph */
void printGraph(Graph* graph) {

	for (int i = 0; i<graph->vertices; ++i) {
		unordered_set<int> lst = graph->adjList[i];
		cout << endl << "Adjacency List of vertex: " << i << endl;

		for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
			cout << *itr << " ";
		}
		cout << endl;
	}
}

/* this function search for the given edge */
void searchEdgeInGraph(Graph* graph, int source, int destination) {

	auto itr = graph->adjList[source].find(destination);
	if (itr == graph->adjList[source].end()) {
		cout << endl << "Edge from " << source << " to " << destination << " not found." << endl;
	}
	else {
		cout << endl << "Edge from " << source << " to " << destination << " found." << endl;
	}
}

/* Main Program */
int main() {

	/* Creating a graph as shown in the above figure */
	int vertices = 5;
	struct Graph* graph = createGraphWithVertices(vertices);

	addEdgeToGraph(graph, 0, 2);
	addEdgeToGraph(graph, 0, 3);
	addEdgeToGraph(graph, 1, 0);
	addEdgeToGraph(graph, 2, 1);
	addEdgeToGraph(graph, 3, 4);

	printGraph(graph);

	/* searching for the given edge */
	searchEdgeInGraph(graph, 2, 0);
	searchEdgeInGraph(graph, 1, 0);
	searchEdgeInGraph(graph, 1, 3);

	return 0;
}

Output

Adjacency List of vertex: 0
1 3 2 

Adjacency List of vertex: 1
2 0 

Adjacency List of vertex: 2
1 0 

Adjacency List of vertex: 3
4 0 

Adjacency List of vertex: 4
3 

Edge from 2 to 0 found.

Edge from 1 to 0 found.

Edge from 1 to 3 not found.

Complexities

Time complexity 

O(V * V), where V is the vertex in a graph.

Reason: We need to iterate all the v vertices while printing the adjacent vertices. Then if each element is connected to another, in this worst case, the time complexity will be O(V * V).

Space complexity

O(V), where V is the vertex in a graph

Reason: The complexity of space is of order V because auxiliary space is utilized when building arrays.

Frequently Asked Questions

What is the graph's set representation?

G represents a graph with a set of V vertices and a set of E edges (V, E). Additional properties that are utilized to characterize the entities and relationships are both possible for vertices and edges.

What is the load factor of a hash table?

The load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased, and n is the overall size of the hash table.

What technique is employed to depict a graph in relation?

The adjacency matrix is used to achieve this type of representation. The adjacency matrix shows which nodes are close on a graph or whether an edge connects two nodes.

What do you mean by depth of a vertex?

The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.

What memory representation does a graph have?

A graph can be kept in memory in three ways: Edges act as pointers and nodes as objects. A matrix that includes each edge weight that connects nodes x and y. edges between numbered nodes, listed.

Conclusion

In the article, we have implemented a graph that is representing using set and hash. We hope that this article will help you understand the concept of a graph, sets, and hash, and if you want to learn more about the graph, check out our other blogs on graphs:

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Implementation of Graph in Python
Next article
Construct a Graph from the size of components of each node
Live masterclass