Do you think IIT Guwahati certified course can help you in your career?
No
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.
Example
Input
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
For vertex: 0, we see three edge passes to vertex 1, 2, and 3.
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.
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;
}
You can also try this code with Online C++ Compiler
/* 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);
}
}
You can also try this code with Online Java Compiler
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.
/* 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;
}
You can also try this code with Online C++ Compiler
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: