What is a Graph?
A graph is a particular kind of data structure composed of the following two components:
A collection of finite vertices makes up a node.
A pair of ordered, finite pairs of the type (u, v). The pair is ordered because (u, v) in the situation of a directed graph differs from (v, u), (di-graph). According to the pair of the shape, there is an edge from vertex u to vertex v. (u, v). The margins may be expensive, valuable, or both.
Graphs are used as models in a wide variety of real-world applications: Graphs can represent networks. It could be a telephone network, a circuit network, or a citywide route network. Graphs are also employed in social media sites like Facebook and LinkedIn. For instance, each user on Facebook.
The next two are the types of graph representations that are most frequently employed.
Adjacency Matrix, first
Adjacency List
Several visualizations exist as well, such as the incidence matrix and incidence list. The graph representation to choose depends on the circumstance. It fully depends on the type of procedures to be performed and the convenience of use.
Matrix of Adjacency:
Adjacency Matrix is a 2D array with the dimensions V x V, where V is the total number of graph vertices. The 2D array adj[][], where adj[i][j] = 1 denotes the existence of an edge connecting vertex I to vertex j, will be discussed. The adjacency matrix for undirected networks is always symmetric. Adjacency matrices are another representational tool for weighted networks. There is an edge from vertex I if adj[i][j] = w.
If there is an edge from vertex I to vertex j in a directed graph, we simply assign adj[i][j]=1.
Linked lists are arranged in an array. The amount of vertices affects the array's size. The array should be an array[]. The linked list of vertices next to the ith vertex is represented by an entry array[i].
A weighted graph can also be represented using this method. Edge weights can be represented as lists of pairs. The above graph is represented by an adjacency list in the paragraph that follows.
C Program Example
// A C Program to demonstrate adjacency list
// representation of graphs
#include <stdio.h>
#include <stdlib.h>
// A structure to represent an adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// A structure to represent an adjacency list
struct AdjList {
struct AdjListNode* head;
};
// A structure to represent a graph. A graph
// is an array of adjacency lists.
// Size of array will be V (number of vertices
// in graph)
struct Graph {
int V;
struct AdjList* array;
};
// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode
= (struct AdjListNode*)malloc(
sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph
= (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of
// array will be V
graph->array = (struct AdjList*)malloc(
V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by
// making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is
// added to the adjacency list of src. The node
// is added at the beginning
struct AdjListNode* check = NULL;
struct AdjListNode* newNode = newAdjListNode(dest);
if (graph->array[src].head == NULL) {
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
else {
check = graph->array[src].head;
while (check->next != NULL) {
check = check->next;
}
// graph->array[src].head = newNode;
check->next = newNode;
}
// Since graph is undirected, add an edge from
// dest to src also
newNode = newAdjListNode(src);
if (graph->array[dest].head == NULL) {
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
else {
check = graph->array[dest].head;
while (check->next != NULL) {
check = check->next;
}
check->next = newNode;
}
// newNode = newAdjListNode(src);
// newNode->next = graph->array[dest].head;
// graph->array[dest].head = newNode;
}
// A utility function to print the adjacency list
// representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
// Driver program to test above functions
int main()
{
// create the graph given in above figure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// print the adjacency list representation of the above
// graph
printGraph(graph);
return 0;
}
Output
Adjacency list of vertex 0
head -> 1-> 4
Adjacency list of vertex 1
head -> 0-> 2-> 3-> 4
Adjacency list of vertex 2
head -> 1-> 3
Adjacency list of vertex 3
head -> 1-> 2-> 4
Adjacency list of vertex 4
head -> 0-> 1-> 3
C++ Program Example
// A simple representation of graph using STL
#include <bits/stdc++.h>
using namespace std;
// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
cout<<endl;
}
}
// Driver code
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}
Output
Adjacency list of vertex 0
head -> 1-> 4
Adjacency list of vertex 1
head -> 0-> 2-> 3-> 4
Adjacency list of vertex 2
head -> 1-> 3
Adjacency list of vertex 3
head -> 1-> 2-> 4
Adjacency list of vertex 4
head -> 0-> 1-> 3
Types of Graphs: Directed and Undirected Graph
Undirected graphs are those in which the edges have no orientation. An undirected graph is the one displayed above.
A directed graph is one in which each edge has a direction assigned to it.
Each edge in the directed graph above represents a particular route from one vertex to another vertex, forming an ordered pair. The "Initial Node" refers to the vertex from which the path begins, while the "Terminal Node" refers to the vertex into which the path comes to an end.
In the aforementioned graph, the vertices are A, B, C, D, and E, and the edges are (A, B), (A, D), (B, C), (B, E), (D, E), and (E, C).
We shall talk about the phrases commonly used about the graph below, or the graph terminology.
What is a Graph Terminology?
Each node in a graph is referred to as a vertex. A, B, C, and D are the vertices of the graph in the example above.
Edge: An edge is a connection or route that connects two vertices. It joins two or more vertices together. The graph above has four distinct edges: AB, BC, AD, and DC.
Adjacent node: In a graph, two nodes are referred to as adjacent nodes or neighbors if they are connected by an edge. Vertices A and B in the graph above are connected by edge AB. A and B are hence adjacent nodes.
Degree of the node: The degree of a node is simply the total number of edges that connect it to other nodes. In the graph shown above, node A.
Path: In a graph, the set of nodes we must follow to move from one vertex to another is referred to as the path. If we were to move from node A to node C in our example graph, the path would be A->B->C.
Closed path: This path is referred to as a closed path if the initial node and the terminal node are the same.
Simple path: A simple path is a closed path in which every other node is distinct.
Cycle: A path with the same first and last vertex and no repeating edges or vertices are referred to as a cycle. The cycle seen in the graph above is A->B->C->D->A.
Connected Graph: A connected graph has a path connecting each of its vertices. Thus, not a single vertex is isolated or without a connecting edge. The aforementioned graph is a linked graph.
Complete Graph: A graph is said to be complete if every node is connected to every other node. If N is the total number of nodes in a graph, then N(N-1)/2 edges make up the entire graph.
Weighted graph: The length of each edge (the separation between the vertices it connects) is indicated by a positive number, which is given to each edge. A weighted graph has edges that have different weights. The cost of traversing an edge is represented by the symbol w(e), which stands for the weight of an edge.
A digraph is a graph in which each edge is connected to a particular direction, and traversal is only possible in that direction.
Representation in Graphs
"Representation of a Graph" refers to how a graph data structure is kept in memory. Both a connected form and a sequential representation of the graph can be kept.
1. The representation of the sequence
We use the adjacency matrix to display graphs sequentially. A matrix of size n x n, where n is the number of graph vertices, is referred to as an adjacency matrix.
The interactions of the vertices, which are matrix entries that are set to 1 whenever the edge is present and to 0 when the edge is absent, are visible in the adjacency matrix.
The adjacency list is simpler to use and adhere to. It takes O(1) time to traverse or determine whether there is an edge from one vertex to another, and O time to remove an edge (1).
Graphs always require more space, regardless of how sparse (fewer edges) or thick they are.
2. Representation Connected
For the connected form of the graph, we use the adjacency list. Each node of the graph and a link to the nodes that are next to it are maintained by the adjacency list representation. When we travel through all the nearby.
To represent the weight of an edge in a weighted graph, we add a field to the adjacency list node, as seen above.
It is simpler to add a vertex to the adjacency list. Due to the introduction of linked lists, space is also saved. The operation is inefficient when we need to determine whether there is an edge from one vertex to another.
They will specify whether it is a directed or undirected graph in the query. The first line comprises the numbers n and m, which stand for the number of nodes and edges, respectively. Two integers u and v, which represent an edge between u and v, are found in the next m lines.
If there is an edge between u and v in an undirected graph, then it follows that there is also an edge between v and u. The question of whether there is a limit on the number of edges or the value of m now emerges. No, is the answer. The amount of m will rise as we add additional edges.
Basic Graph Operations
The fundamental operations that we can carry out on the graph data structure are as follows:
Vertex addition: The graph gains a new vertex.
Add an edge: Adds an edge connecting two graph vertices.
Display the graph vertices: Show the graph's vertices.
Where Can We Apply These Graphs
In computer science, graphs are frequently used to represent network networks, semantic graphs, or even the progression of computation.
Graphs are frequently used in compilers to represent data flow analysis, depict resource allocation to processes, etc.
With some specialist compilers, graphs are also utilized for query optimization in database languages.
Graphs are the primary structures used in social networking sites to represent the network of users.
The construction of the transportation system, particularly the road network, makes considerable use of graphs. Google Maps is a well-known example, which makes heavy use of graphs to provide directions around the globe.
Link your journey from the beginning to the end using Google Maps.
Friends are connected using an edge in social networks, where each user is a vertex.
Recommendation System: Graphs are used to connect related data amongst user recommendations.
Features of Graphs
In the world of computers, science Graphs are among the most powerful data structures in C/C++. C and C++ are the most popular programming languages for learning and implementing graph algorithms to develop applications.
There are various features of using graphs in C++ and hence it makes it an ideal solution for solving complicated problems. In the following section of the article, we will have a look at the key features of graphs in C/C++. Let us have a look at them.
Flexibility: If you are using graphs in C/C++ then you will experience greater flexibility. You will get various libraries and data structures, depending on your requirements. Some of the renowned libraries for graph algorithms in C/C++ are Boost and STL algorithms.
Easy Implementation: We all know C++ comes under the high-level programming language section and one can learn and implement it easily. Implementing graph algorithms in C/C++ is very easy and with simple practice, you can understand and implement it easily in your complex problems.
Increases Speed: C++ is a compiled language, which means whenever you write code in C++ its execution is faster as compared to code written which is written in interpreted languages such as Python. Hence, graph algorithms are an ideal choice for programmers which helps them in computations and data processing.
Memory Management: If you are working in a C++ environment then it will provide you complete control over memory management. As a result, it is beneficial for working with massive datasets. One can use data structures like vectors or arrays for storing graph data. You will also be having the owner allocate and deallocate memory as per requirement.
Visualization: C++ offers several libraries for visualizing graphs, which makes it helpful while debugging or analyzing graph algorithms. Some of the most popular visualization libraries in C/C++ are GraphViz and SFML.
Standardization: C++ is a standardized language, which means there are several sets of well-defined rules and guidelines for writing code. This will help learners who are new to the world of programming to write strong and error-free code. It will also help the developers to collaborate with other developers.
Conclusion
According to their structures, the properties of graphs are primarily used to characterize graphs. We provided precise definitions of these features that are relevant to the field of graph theory.
In essence, it is the number of edges that are present along the shortest path connecting vertex A and vertex B. When connecting two vertices with more than one edge, the distance between them is essentially determined by the shortest path.
A graph is a well-liked and frequently used data structure that, aside from other subjects, has many uses in the field of computer science itself. Vertices and edges linking two or more vertices make up a graph.
Both directed and undirected graphs exist. Graphs can be represented using both an adjacency-linked list and an adjacency matrix, which is a linear representation.
Also, Read - What is Priority Queue? | Queue - 2
Comments