Assignment: Graphs | DSA in C++ - Software Development PDF Download

Instructions

• Attempt all questions.
• Each question carries equal marks.
• Write your answers neatly and legibly.
• Marks will be deducted for incorrect or incomplete answers.
• For programming questions, write the code in C++.

Multiple Choice Questions (MCQs)

Q.1. Which of the following is not a basic property of a graph?
(a) Vertices
(b) Edges
(c) Cycles
(d) Weights
Ans. (d)

Q.2. Which algorithm is used to find the shortest path in a graph with non-negative edge weights?
(a) Depth First Search (DFS)
(b) Breadth First Search (BFS)
(c) Dijkstra's Algorithm
(d) Bellman-Ford Algorithm

Ans. (c)

Q.3. Which algorithm is used to detect cycles in a directed graph?
(a) Depth First Search (DFS)
(b) Breadth First Search (BFS)
(c) Bellman-Ford Algorithm
(d) Kruskal's Algorithm

Ans. (a)

Q.4. Which algorithm is used to find the minimum spanning tree of a graph?

(a) Dijkstra's Algorithm
(b) Bellman-Ford Algorithm
(c) Kruskal's Algorithm
(d) Topological Sorting

Ans. (c)

Q.5. Which algorithm is used to perform a topological sorting of a directed acyclic graph (DAG)?
(a) Depth First Search (DFS)
(b) Breadth First Search (BFS)
(c) Bellman-Ford Algorithm
(d) Kahn's Algorithm

Ans. (d)

High Order Thinking Questions (HOTS)

Q.1. Write the C++ code to implement a Breadth First Search (BFS) algorithm for a graph. Explain the major steps involved.

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void bfs(vector<vector<int>>& graph, int start) {

    vector<bool> visited(graph.size(), false);

    queue<int> q;

    visited[start] = true;

    q.push(start);

    while (!q.empty()) {

        int vertex = q.front();

        q.pop();

        cout << vertex << " ";

        for (int i = 0; i < graph[vertex].size(); i++) {

            int neighbor = graph[vertex][i];

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                q.push(neighbor);

            }

        }

    }

}

int main() {

    int vertices, edges;

    cout << "Enter the number of vertices: ";

    cin >> vertices;

    cout << "Enter the number of edges: ";

    cin >> edges;

    vector<vector<int>> graph(vertices);

    cout << "Enter the edges (u v):" << endl;

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

        int u, v;

        cin >> u >> v;

        graph[u].push_back(v);

        graph[v].push_back(u);

    }

    int startVertex;

    cout << "Enter the starting vertex: ";

    cin >> startVertex;

    cout << "BFS traversal order: ";

    bfs(graph, startVertex);

    return 0;

}

Explanation: The code above implements the Breadth First Search (BFS) algorithm in C++. It takes the number of vertices and edges as input, and then accepts the edges of the graph. It uses a queue to keep track of the vertices to be visited. The algorithm starts with a given start vertex, marks it as visited, and adds it to the queue. Then it continues visiting the neighbors of the current vertex, marking them as visited and adding them to the queue if they haven't been visited before. The process continues until the queue becomes empty.

Q.2. Explain the difference between Breadth First Search (BFS) and Depth First Search (DFS) algorithms in terms of traversal order and the data structures used.

Breadth First Search (BFS) and Depth First Search (DFS) differ in terms of traversal order and the data structures used.

• BFS visits the vertices in a level-by-level manner, exploring all the vertices at the same depth before moving to the next level. It uses a queue data structure to maintain the order of traversal.
• DFS, on the other hand, explores as far as possible along each branch before backtracking. It uses a stack or recursion to maintain the order of traversal. DFS often results in a depth-first traversal where deeper vertices are explored before shallower ones.

Q.3. Write the C++ code to implement a Depth First Search (DFS) algorithm for a graph. Explain the major steps involved.

#include <iostream>

#include <vector>

using namespace std;

void dfs(vector<vector<int>>& graph, int vertex, vector<bool>& visited) {

    visited[vertex] = true;

    cout << vertex << " ";

    for (int i = 0; i < graph[vertex].size(); i++) {

        int neighbor = graph[vertex][i];

        if (!visited[neighbor]) {

            dfs(graph, neighbor, visited);

        }

    }

}

int main() {

    int vertices, edges;

    cout << "Enter the number of vertices: ";

    cin >> vertices;

    cout << "Enter the number of edges: ";

    cin >> edges;

    vector<vector<int>> graph(vertices);

    cout << "Enter the edges (u v):" << endl;

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

        int u, v;

        cin >> u >> v;

        graph[u].push_back(v);

        graph[v].push_back(u);

    }

    int startVertex;

    cout << "Enter the starting vertex: ";

    cin >> startVertex;

    vector<bool> visited(vertices, false);

    cout << "DFS traversal order: ";

    dfs(graph, startVertex, visited);

    return 0;

}

Explanation: The code above implements the Depth First Search (DFS) algorithm in C++. It takes the number of vertices and edges as input, and then accepts the edges of the graph. It uses a recursive approach to traverse the graph. The algorithm starts with a given start vertex, marks it as visited, and prints its value. Then it recursively visits the unvisited neighbors of the current vertex, marking them as visited and printing their values. The process continues until all reachable vertices are visited.

Q.4. Write the C++ code to detect whether a given directed graph contains a cycle. Explain the algorithm used and its time complexity.

#include <iostream>

#include <vector>

using namespace std;

bool isCyclicUtil(vector<vector<int>>& graph, int vertex, vector<bool>& visited, vector<bool>& recStack) {

    visited[vertex] = true;

    recStack[vertex] = true;

    for (int i = 0; i < graph[vertex].size(); i++) {

        int neighbor = graph[vertex][i];

        if (!visited[neighbor]) {

            if (isCyclicUtil(graph, neighbor, visited, recStack))

                return true;

        }

        else if (recStack[neighbor])

            return true;

    }

    recStack[vertex] = false;

    return false;

}

bool isCyclic(vector<vector<int>>& graph) {

    int vertices = graph.size();

    vector<bool> visited(vertices, false);

    vector<bool> recStack(vertices, false);

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

        if (!visited[i]) {

            if (isCyclicUtil(graph, i, visited, recStack))

                return true;

        }

    }

   return false;

}

int main() {

    int vertices, edges;

    cout << "Enter the number of vertices: ";

    cin >> vertices;

    cout << "Enter the number of edges: ";

    cin >> edges;

    vector<vector<int>> graph(vertices);

    cout << "Enter the edges (u v):" << endl;

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

        int u, v;

        cin >> u >> v;

        graph[u].push_back(v);

    }

    bool hasCycle = isCyclic(graph);

    if (hasCycle)

        cout << "The graph contains a cycle.";

    else

        cout << "The graph does not contain a cycle.";

    return 0;

}

Q.5. Write the C++ code to find the minimum weight cycle in an undirected graph. Explain the algorithm used and its time complexity.

#include <iostream>

#include <vector>

#include <climits>

#include <queue>

using namespace std;

struct Edge {

    int source, destination, weight;

};

void addEdge(vector<vector<Edge>>& graph, int source, int destination, int weight) {

    Edge edge = {source, destination, weight};

    graph[source].push_back(edge);

}

vector<int> findShortestPath(vector<vector<Edge>>& graph, int startVertex) {

    int vertices = graph.size();

    vector<int> distance(vertices, INT_MAX);

    distance[startVertex] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0, startVertex));

    while (!pq.empty()) {

        int u = pq.top().second;

        pq.pop();

        for (const auto& edge : graph[u]) {

            int v = edge.destination;

            int weight = edge.weight;

            if (distance[v] > distance[u] + weight) {

                distance[v] = distance[u] + weight;

                pq.push(make_pair(distance[v], v));

            }

        }

    }

    return distance;

}

int main() {

    int vertices, edges;

    cout << "Enter the number of vertices: ";

    cin >> vertices;

    cout << "Enter the number of edges: ";

    cin >> edges;

    vector<vector<Edge>> graph(vertices);

    cout << "Enter the edges (u v w):" << endl;

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

        int u, v, w;

        cin >> u >> v >> w;

        addEdge(graph, u, v, w);

        addEdge(graph, v, u, w);

    }

    int startVertex;

    cout << "Enter the starting vertex: ";

    cin >> startVertex;

    vector<int> shortestPath = findShortestPath(graph, startVertex);

    cout << "Shortest path from vertex " << startVertex << " to each vertex:" << endl;

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

        cout << "Vertex " << i << ": " << shortestPath[i] << endl;

    }

    return 0;

}

Explanation: The code above implements Dijkstra's Algorithm in C++ to find the shortest path in a graph with non-negative edge weights. It takes the number of vertices and edges as input, and then accepts the edges of the graph with their respective weights. The algorithm starts with a given start vertex and initializes the distance of all vertices to infinity except for the start vertex, which is set to 0. It uses a priority queue to store the vertices based on their tentative distance. The algorithm repeatedly selects the vertex with the minimum tentative distance, updates the distances of its neighbors if a shorter path is found, and continues until all vertices are visited. Finally, it prints the shortest path from the start vertex to each vertex in the graph.

Fill in the Blanks

1. In a graph, a __________ is a collection of vertices connected by edges.

In a graph, a path is a collection of vertices connected by edges.

2. The __________ of a graph refers to the number of vertices it contains.

The order of a graph refers to the number of vertices it contains.

3. The __________ of a graph refers to the number of edges it contains.

The size of a graph refers to the number of edges it contains.

4. Dijkstra's Algorithm uses the __________ property to find the shortest path in a graph.

Dijkstra's Algorithm uses the greedy property to find the shortest path in a graph.

5. Kruskal's Algorithm uses the __________ property to find the minimum spanning tree of a graph.

Kruskal's Algorithm uses the minimum weight property to find a minimum spanning tree in a graph.

True or False

1. Breadth First Search (BFS) can be used to find the shortest path in a graph with negative edge weights. (True/False)

True

2. Depth First Search (DFS) can be used to detect cycles in an undirected graph. (True/False)

True

3. Bellman-Ford Algorithm is used to find the shortest path in a directed graph with negative edge weights. (True/False)

True

4. Kruskal's Algorithm can be used to find the minimum spanning tree of a graph with negative edge weights. (True/False)

True

5. Topological Sorting can be applied to a graph that contains cycles. (True/False)

False

Hands-On Questions

Q.1. Implement the Breadth First Search (BFS) algorithm in C++ to traverse a graph and print the order of visited vertices.
Given the following directed graph, perform a Depth First Search (DFS) starting from vertex 0 and write down the order of visited vertices.

     0

    / \

   V   V

   1-->2

    \ /

     V

     3

Order of visited vertices: 0 1 2 3

Q.2. Implement the Depth First Search (DFS) algorithm in C++ to traverse a graph and print the order of visited vertices.

Given the following directed graph, determine whether it contains a cycle using Depth First Search (DFS).

     0

    / \

   V   V

   1-->2

    \ /

     V

     3

The graph contains a cycle.

Q.3. Given a directed graph, write a C++ code to detect whether it contains a cycle or not.

Given the following undirected graph with positive edge weights, find the minimum weight cycle in the graph using appropriate algorithm.

     1

    / \

   V   V

   0<--2

    \ /

     V

     3

Minimum weight cycle: 0 -> 2 -> 1 -> 0

Q.4. Given an undirected graph with positive edge weights, write a C++ code to find the minimum weight cycle in the graph.

Given the following undirected graph with positive edge weights, find the shortest path from vertex 0 to all other vertices using Dijkstra's Algorithm.

     4

    / \

   V   V

   0---2

    \ /

     V

     1

Shortest path from vertex 0 to each vertex:

• Vertex 0: 0
• Vertex 1: 3
• Vertex 2: 1
• Vertex 3: Infinity (Not reachable from vertex 0)

Q.5. Implement the Dijkstra's Algorithm in C++ to find the shortest path in a graph with non-negative edge weights.

Given the following undirected graph, find the minimum spanning tree using Kruskal's Algorithm.

     4

    / \

   V   V

   0---2

    \ /

     V

     1

Minimum spanning tree:

• Edge 0-1 with weight 3
• Edge 0-2 with weight 4