GRAPHS
Here, we discuss another nonlinear data structure, graphs.
Graph representations have found application in almost all subjects like
geography, engineering, and solving games and puzzles.
A graph G consists of
1. Set of vertices V (called nodes), (V = {v1, v2, v3,
v4......}) and
2. Set of edges E (i.e., E {e1, e2, e3......cm} A graph can
be represented as G = (V, E), where V is a finite and non-empty set at vertices
and E is a set of pairs of vertices called edges. Each edge ‘e’ in E is
identified with a unique pair (a, b) of nodes in V, denoted by e = [a, b].
Fig. 1
Consider a graph, G in Fig. 1. Then the vertex V and edge E
can be represented as: V = {v1, v2, v3, v4, v5, v6} and E = {e1, e2, e3, e4,
e5, e6} E = {(v1, v2) (v2, v3) (v1, v3) (v3, v4), (v3, v5) (v5, v6)}. There are
six edges and vertex in the graph.
BASIC TERMINOLOGIES
A directed graph G is characterized as an ordered pair (V,
E), where V denotes a set of vertices and the ordered pairs within E are
referred to as edges on V. Geometrically, a directed graph can be illustrated
as a collection of marked points (known as vertices) V, connected by a set of
arrows (termed edges) E between selected pairs of points (vertices or nodes),
such that there is a maximum of one arrow from a single vertex to another
vertex. For instance, Fig 2 illustrates a directed graph, represented as G =
{a, b, c, d}, {(a, b), (a, d), (d, b), (d, d), (c, c)}.
Fig 2
An edge (a, b) is said to be incident with the vertices it
connects, specifically a and b. Additionally, we can state that the edge (a, b)
is incident from a to b. The vertex a is referred to as the initial vertex,
while the vertex b is known as the terminal vertex of the edge (a, b). If an
edge connects to the same vertex from both ends, such as (d, d) or (c, c) in
Fig. 2, it is termed a loop. Two vertices are said to be adjacent if there
exists an edge connecting them. In the case of the edge (a, b), vertex a is
considered adjacent to vertex b, and vertex b is regarded as adjacent to vertex
a. A vertex is classified as an isolated vertex if no edge is incident to it.
In Fig. 2, vertex C is depicted as an isolated vertex. An undirected graph G is
conceptually defined as a pair (V, E), where V represents a collection of
vertices and E consists of a collection of edges. Geometrically, an undirected
graph can be illustrated as a series of marked points (known as vertices) V
interconnected by lines (referred to as edges) E. An undirected graph G is
illustrated in Fig. 3.
Fig. 3
Two graphs are considered isomorphic if there exists a
one-to-one mapping between their vertices and their edges, ensuring that
incidences are avoided. Figure 4 illustrates an example of an isomorphic
undirected graph.
Fig. 4
Let G = (V, E) represent a graph. A graph G1 = (V1, E1) is
classified as a sub-graph of G if E1 is a subset of E and V1 is a subset of V,
ensuring that the edges in E1 are only connected to the vertices in V1. For
instance, Figure 5(b) illustrates a sub-graph of Figure 5(a). A sub-graph of G
is referred to as a spanning sub-graph if it includes all the vertices from G.
For example, Figure 5(c) depicts a spanning sub-graph of Figure 5(a).
Fig. 5
The number of edges connected to a vertex represents its
degree. The degree of vertex a is denoted as degree(a). If vertex a has a
degree of zero, it is referred to as an isolated vertex. For instance, in Fig.
5, the degree of vertex a is 3. Graph G is referred to as a weighted graph if
each edge and/or vertex is assigned a specific weight or value. A weighted
graph can be described as G = (V, E, We, Wv), where V signifies the set of
vertices, E denotes the set of edges, We represent the weights assigned to the
edges, and Wv indicates the weights assigned to the vertices. Consider a graph.
Fig.
6
In Figure 6, the distances in kilometers between four major
cities in India are illustrated. Here, V = {N, K, M, C}, E = {(N, K), (N, M),
(M, K), (M, C), (K, C)}, We = {55, 47, 39, 27, 113}, and Wv = {N, K, M, C}. The
weights at the vertices are not essential to retain, resulting in Wv and V
being identical. A graph is defined as undirected and connected if there is a
route from any vertex to every other vertex; if not, it is classified as
disconnected. Figure 9.7 presents a disconnected graph, where vertex C is
isolated from the rest of the graph. Conversely, Figure 9.8 depicts a connected
graph, where all the vertices are interlinked.
Fig 7
& 8
A graph G is considered complete (or fully connected or
strongly connected) if there exists a path connecting every vertex to every
other vertex. For two vertices, a and b, in a directed graph, it is termed a
complete graph if there is a path from a to b and also a path from b to a. A
complete graph with n vertices contains n(n – 1)/2 edges. Figure 9 depicts the
complete undirected graph, while Figure 10 illustrates the complete directed
graph.
Fig
9
Fig
10
In a directed graph, a path consists of a sequence of edges
(e1, e2, e3, ... , en) where the edges are connected to one another (i.e., the
ending vertex of en coincides with the starting vertex of e1). A path is termed
elementary if it does not visit any vertex more than once. A path is classified
as simple if it does not traverse the same edges more than once. Refer to the
graph in Fig. 11.
Fig. 11
Where (e1, e2, d3, e4, e5) represents a path; (e1,
e3, e4, e5, e12, e9, e11, e6, e7, e8, e11) denotes a path but is not simple;
(e1, e3, e4, e5, e6, e7, e8, e11, e12) is categorized as a simple path, though
it is not elementary; (e1, e3, e4, e5, e6, e7, e8) qualifies as an elementary
path. A circuit is defined as a path (e1, e2, .... en) where the terminal
vertex of en coincides with the initial vertex of e1. A circuit is considered
simple if it does not traverse the same edge more than once. A circuit is deemed
elementary if it does not pass through the same vertex multiple times. In Fig.
9:11, (e1, e3, e4, e5, e12, e9, e10) exemplifies a simple circuit but is not
elementary; (e1, e3, e4, e5, e6, e7, e8, e10) represents an elementary circuit.
REPRESENTATION OF GRAPH
A graph is a mathematical construct that has applications in
various fields, particularly where problems need to be addressed by computers.
To tackle issues concerning graph G, it's essential to represent them in a
computer's memory utilizing an appropriate data structure. There are two
conventional methods for storing a graph G in a computer's memory.
1. Sequential representation of a graph using adjacent
2. Linked representation of a graph using a linked list.
ADJACENCY MATRIX
REPRESENTATION
The s A of a graph G = (V, E) consisting of n vertices is
represented as an n × n matrix. In this section, we will examine how a directed
graph can be illustrated using an adjacency matrix. Refer to the directed graph
shown in Fig 12, where every vertex is labeled with numbers (1, 2, 3, 4, etc.).
Fig 12
The directed graph G = (V, E) can have its adjacency matrix A
represented (as shown in Fig 13) with these specifications: Aij = 1 if there
exists an edge from vertex Vi to vertex Vj or if the edge (i, j) is included in
E. Conversely, Aij = 0 if there is no edge from vertex Vi to vertex Vj.
Fig
13
We have observed how a directed graph can be depicted using
an adjacency matrix. Now, let's explore the representation of an undirected
graph with an adjacency matrix. Consider the undirected graph illustrated in
Fig. 14.
Fig.
14
The adjacency matrix A for an undirected graph G = (V, E) can
be depicted (in Fig 9.15) with these specifications: Aij = 1 {if there exists
an edge connecting Vi to Vj or if the edge (i, j) is part of E} Aij = 0 {if
there is no edge linking Vi to Vj or if the edge (i, j) is not included in E}.
Fig.
15
To illustrate a weighted graph using an adjacency matrix, the
weight of the edge connecting vertices (i, j) is recorded in the i-th row and
j-th column of the matrix. In situations where a zero weight could be a
possibility for an edge, it's necessary to use a sentinel value for edges that
do not exist, which can be a negative number, as edge weights are always
positive. Consider the weighted graph shown in Fig. 16.
Fig.
16
The adjacency matrix A
of a directed weighted graph G = (V, E, We) can be displayed (as shown in Fig.
17) as Aij = Wij, where Wij denotes the weight of the edge from Vi to Vj if
such an edge exists. Aij = –1 indicates that there is no edge connecting Vi to
Vj.
Fig.
17
In this model, n² memory locations are needed to depict a
graph with n vertices. The adjacency matrix is a straightforward method for
graph representation, but it has two main drawbacks.
1. It utilizes n² space to represent a graph with n vertices,
even when dealing with a sparse graph.
2. It requires O(n²) time to address graph problems.
LINKED LIST REPRESENTATION
In this structure (commonly known as adjacency list
representation), a graph is organized as a linked structure. Initially, we keep
a list of all the vertices in the graph, and then each vertex's adjacent
vertices are represented through linked list nodes. The endpoint of an edge is
stored in a node structure, which is connected to the corresponding starting
vertex in the list. For instance, a directed graph depicted in Fig. 12 can be
illustrated using a linked list as shown in Fig. 18.
Fig. 18
A weighted graph can be illustrated with a linked list by
keeping track of the weights along with the endpoint vertex of each edge.
Looking at the weighted graph in Fig. 16, it can be depicted with a linked list
as shown in Fig. 19.
Fig. 19
While the linked list representation consumes significantly
less memory than the adjacency matrix, the ease of use of the adjacency matrix
makes it a preferred choice for smaller graphs.
OPERATIONS ON GRAPH
Imagine a graph G stored in memory using a linked list
structure. This part covers various operations like graph creation, searching,
and the removal of vertices or edges.
CREATING A GRAPH
To construct a graph, an adjacency list array is first
established to hold the names of the vertices, allocating memory dynamically at
runtime. Next, a node is created and connected to the list array if there is an
edge leading to the vertex.
Step 1: Enter the total number of vertices in the graph,
denoted as n.
Step 2: Dynamically allocate memory for the vertices to be
stored in the list array.
Step 3: Input the first vertex and the vertices that have
edges connected to it by linking the nodes from the list array.
Step 4: Continue this process by incrementing the list array
to incorporate additional vertices and edges.
Step 5: Conclude the process.
SEARCHING AND DELETING FROM
A GRAPH
If an edge (1, 2) needs to be removed from the graph G, we
will first check the list array to see if the starting vertex of the edge
exists by progressing through the list array index. Once the starting vertex is
located in the list array, we will then look through the corresponding linked
list to find the ending vertex.
Step 1: Enter the edge that needs to be searched.
Step 2: Traverse the list arrays by increasing the array
index to locate the starting vertex of the edge.
Step 3: After it is found, search the linked list for the
endpoint of the edge.
Step 4: If the endpoint is located, display "the edge is
present in the graph."
Step 5: Next, remove the node where the endpoint is found and
reorganize the linked list.
Step 6: Exit.
Below is a C program that demonstrates how to add and remove
nodes and edges in a graph using an adjacency matrix. The code is designed for
compilation in Turbo C.
Explanation:
1. displayMatrix(): Outputs the adjacency matrix.
2. addNode(): Inserts a new node (increases n).
3. addEdge(): Creates an edge between two nodes.
4. deleteEdge(): Removes an edge between two nodes.
5. deleteNode(): Eliminates a node and adjusts the adjacency
matrix.
|
//PROGRAM TO IMPLEMENT
ADDITION AND DELETION OF NODES
//AND EDGES IN A GRAPH
USING ADJACENCY MATRIX
//CODED AND COMPILED IN
TURBO C
|
|
#include <stdio.h>
|
|
#include <conio.h>
|
|
|
|
#define MAX 10
|
|
|
|
int adj[MAX][MAX]; //
Adjacency matrix
|
|
int n = 0; // Number of
nodes
|
|
|
|
void displayMatrix();
|
|
void addNode();
|
|
void addEdge();
|
|
void deleteEdge();
|
|
void deleteNode();
|
|
|
|
void main() {
|
|
int choice;
|
|
clrscr();
|
|
while (1) {
|
|
printf("\nGraph Operations using
Adjacency Matrix\n");
|
|
printf("1. Add Node\n");
|
|
printf("2. Add Edge\n");
|
|
printf("3. Delete Edge\n");
|
|
printf("4. Delete Node\n");
|
|
printf("5. Display Adjacency
Matrix\n");
|
|
printf("6. Exit\n");
|
|
printf("Enter your choice:
");
|
|
scanf("%d", &choice);
|
|
|
|
switch (choice) {
|
|
case 1: addNode(); break;
|
|
case 2: addEdge(); break;
|
|
case 3: deleteEdge(); break;
|
|
case 4: deleteNode(); break;
|
|
case 5: displayMatrix(); break;
|
|
case 6: exit(0);
|
|
default: printf("Invalid
choice!\n");
|
|
}
|
|
}
|
|
getch();
|
|
}
|
|
|
|
void displayMatrix() {
|
|
int i, j;
|
|
printf("\nAdjacency
Matrix:\n");
|
|
for (i = 0; i < n; i++) {
|
|
for (j = 0; j < n; j++) {
|
|
printf("%d ",
adj[i][j]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
void addNode() {
|
|
if (n == MAX) {
|
|
printf("Maximum nodes
reached!\n");
|
|
return;
|
|
}
|
|
n++;
|
|
printf("Node %d added
successfully!\n", n);
|
|
}
|
|
|
|
void addEdge() {
|
|
int u, v;
|
|
printf("Enter nodes (u v) to add an
edge: ");
|
|
scanf("%d %d", &u, &v);
|
|
if (u >= n || v >= n || u < 0 ||
v < 0) {
|
|
printf("Invalid nodes!\n");
|
|
return;
|
|
}
|
|
adj[u][v] = 1;
|
|
adj[v][u] = 1; // For undirected graph
|
|
printf("Edge added
successfully!\n");
|
|
}
|
|
|
|
void deleteEdge() {
|
|
int u, v;
|
|
printf("Enter nodes (u v) to delete
the edge: ");
|
|
scanf("%d %d", &u, &v);
|
|
if (u >= n || v >= n || u < 0 ||
v < 0) {
|
|
printf("Invalid nodes!\n");
|
|
return;
|
|
}
|
|
adj[u][v] = 0;
|
|
adj[v][u] = 0;
|
|
printf("Edge deleted
successfully!\n");
|
|
}
|
|
|
|
void deleteNode() {
|
|
int v, i, j;
|
|
printf("Enter node number to delete:
");
|
|
scanf("%d", &v);
|
|
if (v >= n || v < 0) {
|
|
printf("Invalid node!\n");
|
|
return;
|
|
}
|
|
for (i = v; i < n - 1; i++) {
|
|
for (j = 0; j < n; j++) {
|
|
adj[i][j] = adj[i + 1][j];
|
|
}
|
|
}
|
|
for (j = v; j < n - 1; j++) {
|
|
for (i = 0; i < n; i++) {
|
|
adj[i][j] = adj[i][j + 1];
|
|
}
|
|
}
|
|
n--;
|
|
printf("Node %d deleted
successfully!\n", v);
|
|
}
|
|
|
TRAVERSING A GRAPH
Many applications of graph requires a structured system to
examine the vertices and edges of a graph G. That is a graph traversal, which
means visiting all the nodes of the graph. There are two graph traversal
methods.
(a) Breadth First Search (BFS)
(b) Depth First Search (DFS)
BREADTH FIRST SEARCH
Given a graph G = (V, E) and a designated starting vertex S,
breadth first search initiates a systematic exploration of the edges in G to
reach every vertex accessible from S. We then analyze all the vertices adjacent
to the source vertex S. Following this, we explore all the neighbors of the
neighbors of the source vertex S, and continue this process. A queue is
utilized to monitor the status of the traversal through the neighboring nodes.
Further discussion of BFS can be illustrated with an example, using the graph G
depicted in Fig. 20.
Fig. 20.
The representation of the graph in Fig. 20 using a linked
list (or adjacency list) is provided as well. Let’s assume that the source
vertex is A. The following steps will demonstrate the BFS process. Step 1:
Begin by adding A (the source vertex) to the queue.
Step 2: Pop (or remove) the front element A from the queue
(by incrementing front = front +1) and display it. Then push (or add) the
neighboring vertices of A to the queue, (by incrementing Rear = Rear +1) if it
is not in the queue. 
Step 3: Pop the front element B from the queue and display
it. Then add the neighboring vertices of B to the queue, if it is not in the queue.
One of the neighboring elements C of B is preset in the queue,
So C is not added to the queue.
Step 4: Remove the
front element C and display it. Add the neighboring vertices of C, if it is not
present in queue.
One of the neighboring elements E of C is present in the
queue. So E is not added. Step 5: Remove the front element D, and add the
neighboring vertex if it is not present in the queue.
Step 6: Again the process is repeated (until Front >
Rear). That is remove the front element E of the queue and add the neighboring
vertex if it not present in queue.
So A, B, C, D, E, F, G, H is the BFS traversal of the graph
in Fig. 20.
ALGORITHM
1. Input the vertices of the graph and its edges G = (V, E)
2. Input the source vertex and assign it to the variable S.
3. Add or push the source vertex to the queue.
4. Repeat the steps 5 and 6 until the queue is empty (i.e.,
front > rear)
5. Pop the front element of the queue and display it as
visited.
6. Push the vertices, which is neighbors to just, the popped
element, if it is not in the queue and displayed (i.e., not visited).
7. Exit.
Here's a C program to implement Breadth-First Search
(BFS) in a graph, written in a way that is compatible with Turbo C.
Key Features:
- Uses an adjacency
matrix to represent the graph.
- Implements
BFS using a queue.
- Works
with Turbo C, avoiding modern C features.
1.
#include <stdio.h>
2.
#include <conio.h>
. #define MAX 10
.
int adj[MAX][MAX], visited[MAX], queue[MAX],
front = 0, rear = -1, n;
void BFS(int start) {
6.
int i, node;
7.
printf("BFS Traversal: ");
8.
// Add starting node to queue and mark it as
visited
9.
queue[++rear] = start;
10. visited[start]
= 1;
11. while
(front <= rear) {
12. node
= queue[front++]; // Dequeue
13. printf("%d
", node);
14. for
(i = 0; i < n; i++) {
15. if
(adj[node][i] == 1 && !visited[i]) {
a.
queue[++rear] = i; // Enqueue
b.
visited[i] = 1;
16. }
17. }
18. }
19. }
20. void
main() {
21. int
i, j, start;
22. clrscr(); // Clear screen (Turbo C function)
23. //
Input: Number of vertices
24. printf("Enter
number of vertices: ");
25. scanf("%d",
&n);
26. //
Input: Adjacency matrix
27. printf("Enter
adjacency matrix:\n");
28. for
(i = 0; i < n; i++)
29. for
(j = 0; j < n; j++)
30. scanf("%d",
&adj[i][j]);
31. //
Initialize visited array
32. for
(i = 0; i < n; i++)
33. visited[i]
= 0;
34. //
Input: Starting node for BFS
35. printf("Enter
starting node: ");
36. scanf("%d",
&start);
37. //
Call BFS function
38. BFS(start);
39. getch(); // Wait for user input before closing (Turbo
C function)
40. }
Explanation:
- Graph
Representation: Uses an adjacency matrix (adj[MAX][MAX]).
- Queue
Implementation: Uses an array (queue[MAX]) with front and rear
pointers.
- BFS
Algorithm:
- Start
from the given node.
- Visit
all adjacent unvisited nodes, mark them as visited, and enqueue them.
- Continue
until the queue is empty.
- User
Input:
- Number
of vertices.
- Adjacency
matrix values.
- Starting
node.
Enter number of vertices: 4
Enter adjacency matrix:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Enter starting node: 0
BFS Traversal: 0 1 2 3
============
DEPTH FIRST SEARCH
The graph shown in Fig. 20 also has a representation in the
form of a linked list (or adjacency list). Let's consider vertex A as the
source. The following steps will demonstrate the process of BFS. Step 1: Begin
by adding A (the source vertex) to the queue. The depth-first search (DFS), as
indicated by its name, aims to delve deeper into the graph whenever feasible.
Given an input graph G = (V, E) and a source vertex S from where the search
initiates, we first explore the starting node. Then we proceed through each
node along a route that starts at S. This means we check a neighboring vertex
of S and then a neighbor of that neighbor of S, continuing in this fashion. The
implementation of BFS is quite similar, except that a stack is utilized in
place of the queue. DFS can be further elaborated with a practical example.
Take the graph in Fig. 9.20 along with its linked list representation. Assuming
the source vertex is I, the ensuing steps will outline the DFS process.
Step 1: Initially push I on to the stack.
STACK: I
DISPLAY:
Step 2: Pop and display the top element, and then push all
the neighbors of popped element (i.e., I) onto the stack, if it is not visited
(or displayed or not in the stack.
STACK: G, H
DISPLAY: I
Step 3: Pop and display the top element and then push all the
neighbors of popped the element (i.e., H) onto top of the stack, if it is not
visited.
STACK: G, E
DISPLAY: I, H
The popped element H has two neighbors E and G. G is already
visited, means G is either in the stack or displayed. Here G is in the stack.
So only E is pushed onto the top of the stack.
Step 4: Pop and display the top element of the stack. Push
all the neighbors of the popped element on to the stack, if it is not visited.
STACK: G, D, F
DISPLAY: I, H, E
Step 5: Pop and display the top element of the stack. Push
all the neighbors of the popped element onto the stack, if it is not visited.
STACK: G, D
DISPLAY: I, H, E, F
The popped element (or vertex) F has neighbor(s) H, which is
already visited. Then H is displayed, and will not be pushed again on to the
stack.
Step 6: The process is repeated as follows.
STACK: G DISPLAY: I, H, E, F, D
STACK: //now
the stack is empty
DISPLAY: I, H, E, F, D, G So I, H, E, F, D, G is the DFS
traversal of graph Fig 20 from the source vertex I.
Algorithm
1. Input the vertices and edges of the graph G = (V, E).
2. Input the source vertex and assign it to the variable S.
3. Push the source vertex to the stack.
4. Repeat the steps 5 and 6 until the stack is empty.
5. Pop the top element of the stack and display it.
6. Push the vertices which is neighbor to just popped
element, if it is not in the queue and displayed (ie; not visited).
7. Exit.
Explanation:
- Graph
Representation: Uses an adjacency matrix (adj[MAX][MAX]).
- DFS
Algorithm:
- Start
from the given node.
- Visit
it, mark it as visited.
- Recursively
visit all connected unvisited nodes.
- User
Input:
- Number
of vertices.
- Adjacency
matrix values.
- Starting
node.
1.
#include <stdio.h>
2.
#include <conio.h>
3.
#define MAX 10
4.
int adj[MAX][MAX], visited[MAX], n;
5.
void DFS(int start) {
6.
int i;
7.
printf("%d ", start);
8.
visited[start] = 1; // Mark node as visited
9.
for (i = 0; i < n; i++) {
10. if
(adj[start][i] == 1 && !visited[i]) {
11. DFS(i); // Recursive DFS call
12. }
13. }
14. }
void
main() {
16. int
i, j, start;
17. clrscr(); // Clear screen (Turbo C function)
18. //
Input: Number of vertices
19. printf("Enter
number of vertices: ");
20. scanf("%d",
&n);
21. //
Input: Adjacency matrix
22. printf("Enter
adjacency matrix:\n");
23. for
(i = 0; i < n; i++)
24. for
(j = 0; j < n; j++)
25. scanf("%d",
&adj[i][j]);
26. //
Initialize visited array
27. for
(i = 0; i < n; i++)
28. visited[i]
= 0;
29. //
Input: Starting node for DFS
30. printf("Enter
starting node: ");
31. scanf("%d",
&start);
32. //
Call DFS function
33. printf("DFS
Traversal: ");
34. DFS(start);
35. getch(); // Wait for user input before closing (Turbo
C function)
36. }
==============
MINIMUM SPANNING TREE
A minimum spanning tree (MST) for a graph G = (V, E) is a
subgraph G1 = (V1, E1) of G that includes all the vertices of G. 1. The vertex
set V1 is identical to the one in graph G. 2. The edge set E1 is a subset of E
in graph G. 3. Additionally, there are no cycles present. If graph G is not
connected, it cannot possess any spanning tree. In such scenarios, it will
instead have a spanning forest. If a graph G consists of n vertices, the MST
will contain (n – 1) edges, provided the graph is connected. A minimum spanning
tree (MST) for a weighted graph is a spanning tree that has the least overall
weight. This means all the vertices in the weighted graph will be linked using
edges with the minimum weights. Figure 22 displays the minimum spanning tree of
the weighted graph shown in Figure 21.
Fig.
22
Three different famous algorithms can be used to obtain a
minimum spanning tree of a connected weighted and undirected graph.
1. Kruskal’s Algorithm
2. Prim’s Algorithm
3. Sollin’s Algorithm
All three algorithms are using a design strategy called the
greedy methods that seeks maximum gain at each step.
Questions of the Day:
1. Describe what a graph is. Discuss the depth-first search
technique for traversing a graph.
2. Provide an algorithm for performing a depth-first search
on a graph. Mention its benefits and drawbacks.
3. Compare and contrast adjacency matrices with adjacency
lists.
4. Describe how graphs can be represented using
matrices.
5. Discuss the role of graphs in data structures.
6. Describe the two techniques for traversing graphs.
OR
1. Define a graph. Explain depth first search of traversing?
2. Write an algorithm for the depth first search of a graph?
State its advantages and disadvantages?
3. Distinguish between adjacency matrix and adjacency list?
4. Explain the method of representing graphs by using
matrices?
5. Explain the use of graph in data structures?
6. Explain the two methods of graph traversing?
***
· Keywords:
G Graph Data Structure
·
Graph Representation
·
Adjacency Matrix
·
Adjacency List
·
Graph Traversal
·
Breadth-First Search (BFS)
·
Depth-First Search (DFS)
·
Directed vs Undirected Graphs
·
Graph Algorithms
·
Shortest Path Algorithm
******************
Share, Like, and
Comment
*********************
