Data Structures Graphs

 

Contents

Define and classify the Graph

In data structures, a graph is a non-linear data structure that consists of a set of vertices (also known as nodes) connected by edges. Graphs are used to represent relationships or connections between different elements. They are fundamental in solving problems related to networks, routing, scheduling, and optimization.

A graph G is typically defined as G = (V, E), where:

  • V represents the set of vertices (nodes) in the graph.
  • E represents the set of edges, which are the connections between vertices.

Classification of Graphs in Data Structures:

  1. Directed vs. Undirected Graphs:
    • In an undirected graph, the edges have no specific direction. The connection between two vertices is bi-directional.
    • In a directed graph, the edges have a specific direction. The connection between vertices is one-way, indicating a specific flow or relationship.
  2. Weighted vs. Unweighted Graphs:
    • In an unweighted graph, each edge is assigned the same weight or value. The edges represent only the presence of a connection.
    • In a weighted graph, each edge is assigned a weight or value that represents a specific property or cost associated with the connection.
  3. Cyclic vs. Acyclic Graphs:
    • In a cyclic graph, there exists at least one cycle, which is a path that starts and ends at the same vertex.
    • In an acyclic graph, there are no cycles present.
  4. Connected vs. Disconnected Graphs:
    • In a connected graph, there is a path between any two vertices. Every vertex can be reached from any other vertex.
    • In a disconnected graph, there are one or more components or subgraphs that are not connected to the rest of the graph.
  5. Bipartite Graphs:
    • In a bipartite graph, the set of vertices can be divided into two disjoint sets such that there are no edges connecting vertices within the same set. This property allows the graph to be represented as a two-colorable graph.
  6. Complete Graphs:
    • In a complete graph, every pair of vertices is connected by an edge. There are no missing connections between vertices.

These are some common classifications of graphs in the context of data structures. Each type of graph has its own properties and characteristics, which can be utilized to solve specific problems efficiently.

Recall various Terminologies used in the Graph

Here are some common terminologies used in graph theory:

  1. Vertex (Plural: Vertices or Nodes):
    • A vertex represents a single element or entity in a graph. It can be represented by a unique identifier or label.
  2. Edge:
    • An edge represents a connection or relationship between two vertices. It can be directed (with a specific direction) or undirected (without a specific direction). In an undirected graph, the edge is typically represented by an unordered pair of vertices.
  3. Adjacent Vertices:
    • Two vertices are said to be adjacent if there exists an edge connecting them.
  4. Degree:
    • The degree of a vertex is the number of edges incident to that vertex. In a directed graph, the degree is further classified into in-degree (number of incoming edges) and out-degree (number of outgoing edges).
  5. Path:
    • A path is a sequence of vertices where each consecutive pair is connected by an edge. The length of a path is the number of edges in the path.
  6. Cycle:
    • A cycle is a path in which the first and last vertices are the same, forming a closed loop.
  7. Connected Graph:
    • A connected graph is one in which there exists a path between every pair of vertices. There are no isolated or disconnected vertices.
  8. Disconnected Graph:
    • A disconnected graph is one that contains one or more components or subgraphs that are not connected to the rest of the graph. Each component is a connected subgraph.
  9. Subgraph:
    • A subgraph is a graph formed by a subset of the vertices and edges of an existing graph.
  10. Weighted Graph:
    • A weighted graph is a graph in which each edge is assigned a weight or value. These weights may represent distances, costs, or any other relevant attribute.
  11. Bipartite Graph:
    • A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no edge connects vertices within the same set.
  12. Spanning Tree:
    • A spanning tree of a graph is a subgraph that is a tree and includes all the vertices of the original graph while containing the minimum possible number of edges.

These are some common terminologies used in graph theory. Understanding these terms is crucial for working with graphs and solving graph-related problems efficiently.

Describe various representations of a Graph

There are several common ways to represent a graph data structure. Each representation has its own advantages and is suitable for different types of operations and algorithms.

Here are the main representations of a graph:

  1. Adjacency Matrix:
    • An adjacency matrix is a 2D matrix of size V x V, where V is the number of vertices in the graph. The entry (i, j) in the matrix represents whether there is an edge between vertices i and j. It can be a boolean value or store edge weights if the graph is weighted. In an undirected graph, the matrix is symmetric.
    • Advantages: Constant time access to check if there is an edge between two vertices. Suitable for dense graphs.
    • Disadvantages: Consumes more memory, especially for sparse graphs. Inefficient for operations involving vertex degrees or adjacency list traversal.
  2. Adjacency List:
    • An adjacency list represents a graph as an array of linked lists or arrays. Each vertex in the graph has an associated list that contains its adjacent vertices or edges. It can be implemented using arrays, linked lists, or hash maps.
    • Advantages: Efficient memory usage for sparse graphs. Suitable for graphs with varying degrees. Allows easy traversal of adjacent vertices.
    • Disadvantages: Accessing specific edges or checking for the presence of an edge takes linear time. Not as efficient for dense graphs.
  3. Incidence Matrix:
    • An incidence matrix represents a graph as a 2D matrix of size V x E, where V is the number of vertices and E is the number of edges. Each row represents a vertex, and each column represents an edge. The entry (i, j) in the matrix indicates whether vertex i is incident to edge j.
    • Advantages: Suitable for graphs with many edges. Allows efficient edge-related operations.
    • Disadvantages: Consumes more memory, especially for graphs with many vertices. Inefficient for vertex-related operations.
  4. Edge List:
    • An edge list representation maintains a list of all edges in the graph. Each edge is represented as a tuple or object containing the source vertex, destination vertex, and optional weight.
    • Advantages: Simple and compact representation. Suitable for algorithms that iterate over all edges.
    • Disadvantages: Inefficient for vertex-related operations. Finding the adjacency of a vertex requires iterating through all edges.

These are the main representations of a graph. The choice of representation depends on factors such as the nature of the graph, the type of operations to be performed, memory constraints, and algorithmic requirements. It’s important to consider the trade-offs between memory usage, time complexity, and ease of implementation when selecting a graph representation.

Compare various representations of a Graph

Here’s a comparison of various representations of a graph in tabular form:

Representation Space Complexity Edge Existence Check Vertex Adjacency Check Edge Addition/Removal Memory Usage for Sparse Graphs
Adjacency Matrix O(V^2) O(1) O(1) O(1) High
Adjacency List O(V + E) O(degree(V)) O(degree(V)) O(1) Low
Incidence Matrix O(V x E) O(E) O(E) O(E) High
Edge List O(E) O(E) O(E) O(1) Low

Note:

  • V represents the number of vertices.
  • E represents the number of edges.

Here’s a brief explanation of the comparison criteria:

  1. Space Complexity: Indicates the amount of memory required by the representation. It considers the worst-case scenario.
  2. Edge Existence Check: Time complexity to check if an edge exists between two vertices.
  3. Vertex Adjacency Check: Time complexity to check if two vertices are adjacent (connected by an edge).
  4. Edge Addition/Removal: Time complexity to add or remove an edge from the graph.
  5. Memory Usage for Sparse Graphs: Indicates whether the representation is suitable for sparse graphs, which have fewer edges compared to vertices.

Based on these criteria, you can choose the representation that best suits your specific requirements, such as the nature of the graph, the types of operations you need to perform, and the available memory resources.

Define Graph Traversing

Graph traversal refers to the process of visiting all the vertices and edges of a graph in a systematic and orderly manner. It involves exploring and accessing each element of the graph, typically starting from a specific vertex. Traversing a graph is an essential operation in graph algorithms and allows for the analysis and manipulation of graph data.

There are two commonly used methods for graph traversal:

  1. Depth-First Traversal (DFS):
    • DFS starts at a specific vertex and explores as far as possible along each branch before backtracking.
    • It uses a stack (or recursion) to keep track of the vertices to visit.
    • When visiting a vertex, it marks it as visited and recursively explores its adjacent vertices.
    • DFS is useful for applications such as finding connected components, detecting cycles, and traversing in a specific order.
    • Example algorithm:
      1. Start at a given vertex.
      2. Mark the current vertex as visited.
      3. Recursively visit all unvisited adjacent vertices.
      4. Backtrack if no unvisited vertices are left.
  2. Breadth-First Traversal (BFS):
    • BFS explores all the vertices at the current level before moving to the next level.
    • It uses a queue to keep track of the vertices to visit.
    • When visiting a vertex, it marks it as visited and enqueues its adjacent vertices.
    • BFS is useful for applications such as finding the shortest path, determining reachability, and discovering connected components.
    • Example algorithm:
      1. Start at a given vertex and enqueue it.
      2. Mark the current vertex as visited.
      3. Dequeue a vertex from the queue and visit it.
      4. Enqueue all unvisited adjacent vertices.
      5. Repeat steps 3-4 until the queue is empty.

Both DFS and BFS ensure that every vertex in a connected graph is visited once. The order in which vertices are visited depends on the chosen algorithm and data structures used (stack or queue). These traversal methods allow for various graph analysis and operations by systematically exploring the graph’s structure.

Describe BFS with Suitable example

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in a breadthward motion, starting from a specific vertex. It visits all the vertices at the current level before moving to the next level. BFS uses a queue data structure to keep track of the vertices to visit, ensuring that vertices closer to the starting point are visited before those farther away. This algorithm is particularly useful for finding the shortest path between two vertices and for exploring a graph in a level-by-level manner.

Here’s a step-by-step description of the BFS algorithm:

  1. Start with a specific vertex as the starting point.
  2. Enqueue the starting vertex into a queue and mark it as visited.
  3. Repeat the following steps until the queue becomes empty:

a. Dequeue a vertex from the front of the queue and visit it.

b. Enqueue all unvisited adjacent vertices of the current vertex into the queue and mark them as visited.

  1. If there are no more vertices in the queue, the BFS traversal is complete.

Here’s an example to illustrate the BFS algorithm:

Consider the following undirected graph:

A — B

/ \\

C — D — E

Starting with vertex A, we perform a BFS traversal. We enqueue vertex A and mark it as visited. Then, we dequeue A and visit it. We enqueue its adjacent vertices B and C. Next, we dequeue B and visit it. We enqueue vertex D, which is adjacent to B. Then, we dequeue C and visit it. We enqueue D, which is adjacent to C. Finally, we dequeue D and visit it. The graph exploration is complete, as there are no more vertices in the queue.

The order of visiting the vertices in this example is: A, B, C, D, E. This order represents the breadth-first exploration of the graph starting from vertex A. BFS ensures that vertices closer to the starting point are visited before exploring vertices farther away.

BFS is often used to solve problems such as finding the shortest path between two vertices, determining reachability in a graph, and exploring a graph in a level-by-level manner.

Describe DFS with suitable examples

Depth-First Search (DFS) is a graph traversal algorithm that explores all the vertices of a graph in a depthward motion, starting from a specific vertex. It explores as far as possible along each branch before backtracking. DFS uses either a stack or recursion to keep track of the vertices to visit, ensuring that vertices farther away from the starting point are explored before backtracking. This algorithm is useful for detecting cycles, finding connected components, and exploring a graph in a specific order.

Here’s a step-by-step description of the DFS algorithm:

  1. Start with a specific vertex as the starting point.
  2. Mark the starting vertex as visited.
  3. Visit the current vertex and explore its adjacent vertices recursively.
  4. For each unvisited adjacent vertex, repeat steps 2-3.
  5. If there are no more unvisited adjacent vertices, backtrack to the previous vertex and continue the exploration from there.
  6. Repeat steps 2-5 until all vertices have been visited.

Let’s consider the following undirected graph as an example:

A — B — C

| |

D —E

Starting with vertex A, we perform a DFS traversal. We mark A as visited and visit it. Then, we explore its adjacent vertices, visiting B and marking it as visited. From B, we explore its adjacent vertex C. Since C has no unvisited adjacent vertices, we backtrack to B. From B, we explore its remaining unvisited adjacent vertex E, marking it as visited. From E, we backtrack to B again. Then, from B, we backtrack to A and explore its remaining unvisited adjacent vertex D. We mark D as visited and backtrack to A. Finally, there are no unvisited adjacent vertices from A, and the DFS traversal is complete.

The order of visiting the vertices in this example is: A, B, C, E, D. This order represents the depth-first exploration of the graph starting from vertex A. DFS explores as far as possible along each branch before backtracking, and it ensures that all connected vertices are visited before backtracking.

DFS is often used to solve problems such as finding connected components, detecting cycles, and exploring a graph in a specific order.

Write an Algorithm or a C Function for BFS and DFS

BFS(G, s)

1. Mark the source vertex s as visited and enqueue it in the queue

2. While the queue is not empty, do the following:

3. Dequeue a vertex v from the queue

4. Mark v as visited

5. For each unvisited neighbour u of v, do the following:

– Mark u as visited

– Enqueue u in the queue

6. End loop

Algorithm for DFS:

DFS(G, s)

1. Mark the source vertex s as visited

2. For each unvisited neighbour u of s, do the following:

– DFS(G, u)

3. End loop

Here’s an example of both BFS and DFS algorithms implemented as C functions:

  1. Breadth-First Search (BFS)

#include <stdio.h>

#include <stdbool.h>

#define MAX_VERTICES 100

// Graph representation using adjacency list

struct Node {

int vertex;

struct Node* next;

};

struct Graph {

int numVertices;

struct Node* adjLists[MAX_VERTICES];

bool visited[MAX_VERTICES];

};

// Function to create a new graph

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->numVertices = vertices;

for (int i = 0; i < vertices; i++) {

graph->adjLists[i] = NULL;

graph->visited[i] = false;

}

return graph;

}

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {

// Add edge from src to dest

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->vertex = dest;

newNode->next = graph->adjLists[src];

graph->adjLists[src] = newNode;

// Add edge from dest to src (for undirected graph)

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->vertex = src;

newNode->next = graph->adjLists[dest];

graph->adjLists[dest] = newNode;

}

// BFS traversal from a given vertex

void BFS(struct Graph* graph, int startVertex) {

// Create a queue for BFS

int queue[MAX_VERTICES];

int front = 0, rear = 0;

// Mark the startVertex as visited and enqueue it

graph->visited[startVertex] = true;

queue[rear++] = startVertex;

printf(“BFS traversal: “);

while (front < rear) {

// Dequeue a vertex from the queue and visit it

int currentVertex = queue[front++];

printf(“%d “, currentVertex);

// Get all adjacent vertices of the dequeued vertex

struct Node* temp = graph->adjLists[currentVertex];

while (temp) {

int adjVertex = temp->vertex;

// If the adjacent vertex is not visited, mark it as visited and enqueue it

if (!graph->visited[adjVertex]) {

graph->visited[adjVertex] = true;

queue[rear++] = adjVertex;

}

temp = temp->next;

}

}

printf(“\\n”);

}

  1. Depth-First Search (DFS) C Function

// DFS traversal from a given vertex

void DFS(struct Graph* graph, int startVertex) {

// Mark the startVertex as visited and print it

graph->visited[startVertex] = true;

printf(“%d “, startVertex);

// Get all adjacent vertices of the startVertex

struct Node* temp = graph->adjLists[startVertex];

while (temp) {

int adjVertex = temp->vertex;

// If the adjacent vertex is not visited, recursively call DFS on it

if (!graph->visited[adjVertex]) {

DFS(graph, adjVertex);

}

temp = temp->next;

}

}

Note: The BFS and DFS algorithms assume that the graph is represented using an adjacency list. The createGraph() function is used to create a graph with a given number of vertices. The addEdge() function is used to add edges between vertices. The BFS() function performs a breadth-first traversal starting from a given vertex. The DFS() function performs a depth-first traversal starting from a given vertex. The visited[] array is used to keep track of visited vertices.

Make sure to include the necessary header files (#include <stdio.h> and #include <stdbool.h>) and allocate memory appropriately (malloc() and free()) for dynamic memory management.

These algorithms can be called from the main function by creating a graph, adding edges, and calling the respective traversal functions.

Describe Topological Sort of a Graph

Topological sort is an algorithm used to sort the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge (u, v), vertex u comes before vertex v in the sorted order. In other words, it provides a linear ordering of the vertices that respects the partial order defined by the edges of the graph.

The topological sort algorithm works as follows:

  1. Choose a vertex in the graph that has no incoming edges. If multiple vertices satisfy this condition, any one of them can be selected.
  2. Add the chosen vertex to the sorted order.
  3. Remove the chosen vertex and all its outgoing edges from the graph.
  4. Repeat steps 1-3 until all vertices have been processed.

If there are still remaining vertices in the graph after the above steps, it means that the graph contains cycles and a topological sort is not possible.

Topological sort can be performed using various algorithms, but one of the commonly used algorithms is based on depth-first search (DFS).

The algorithm is as follows:

  1. Perform a DFS traversal on the graph.
  2. When a vertex has no unvisited neighbors (outgoing edges), add it to the beginning of the sorted order.
  3. Reverse the resulting order to obtain the topological sort.

Example: Consider a graph with vertices A, B, C, D, and E, and edges between the vertices as shown below:

A topological sort of this graph would be: A, B, D, C, E. or A, B, C, D, E

It’s important to note that topological sort is only applicable to directed acyclic graphs. If the graph contains cycles, it’s not possible to obtain a valid topological ordering.

Topological sort has various applications, such as task scheduling, dependency resolution, and determining the order of execution in a directed graph.

Define Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices with the minimum possible total edge weight. In simpler terms, it is a tree that spans all the vertices of the graph with the least total edge weight.

Key properties of a Minimum Spanning Tree:

  1. It is a tree: An MST is a connected acyclic graph that does not contain any cycles. It connects all the vertices without forming loops.
  2. It spans all vertices: An MST includes all the vertices of the original graph, ensuring that every vertex is reachable from any other vertex through the tree’s edges.
  3. It has minimum total weight: The total weight of an MST is the sum of the weights of its edges. The goal of finding an MST is to minimize this total weight, making it the smallest possible among all possible spanning trees of the graph.

Minimum Spanning Tree algorithms, such as Kruskal’s algorithm and Prim’s algorithm, are used to find an MST in a given graph. These algorithms iteratively add edges to the MST while ensuring that the tree remains connected and acyclic.

Applications of Minimum Spanning Tree:

  1. Network design: MSTs are used to design efficient and cost-effective network infrastructures, such as laying cables, constructing highways, or connecting cities with minimum cost.
  2. Cluster analysis: MSTs are utilized in clustering algorithms to group related data points or objects together based on their proximity or similarity.
  3. Approximation algorithms: MSTs are used as building blocks in approximation algorithms for solving optimization problems, such as the traveling salesman problem and facility location problem.
  4. Image segmentation: MSTs have applications in image processing, where they can be used to segment images into coherent regions based on pixel similarity.

By finding the minimum spanning tree of a graph, we can identify the subset of edges that form the most efficient and cost-effective way to connect all the vertices.

Describe Kruskal’s Algorithm

Kruskal’s algorithm is a greedy algorithm used to find a minimum spanning tree (MST) in a connected, weighted graph. It starts with an empty set of edges and gradually adds edges to form the MST.

The algorithm works as follows:

  1. Create a set of all the edges in the graph.
  2. Sort the edges in non-decreasing order of their weights.
  3. Initialize an empty set to store the MST.
  4. Iterate through the sorted edges in increasing order of weights.
  5. For each edge, check if adding it to the MST creates a cycle. If not, add the edge to the MST.
    • To check for cycles, we can use a disjoint set data structure or union-find algorithm.
    • If the endpoints of the edge belong to different disjoint sets, add the edge to the MST and merge the sets.
    • If the endpoints belong to the same set, skip the edge to avoid creating a cycle.
  6. Continue this process until all vertices are included in the MST or until there are no more edges to consider.

OR

MST- KRUSKAL (G, w)

1. A ← ∅

2. for each vertex v ∈ V [G]

3. do MAKE – SET (v)

4. sort the edges of E into non decreasing order by weight w

5. for each edge (u, v) ∈ E, taken in non decreasing order by weight

6. do if FIND-SET (μ) ≠ if FIND-SET (v)

7. then A ← A ∪ {(u, v)}

8. UNION (u, v)

9. return A

Once the algorithm finishes, the resulting set of edges will form the minimum spanning tree of the graph.

Find Minimum Spanning Tree for the given Graph using Kruskal’s Algorithm

Example: Find the Minimum Spanning Tree of the following graph using Kruskal’s algorithm