Q14: There are flight paths between cities. If there is a flight between city A and city B then there is an edge between the cities. The cost of the edge can be the time that flight takes to reach city B from A, or the amount of fuel used for the journey. Represent this as a graph. The node can be represented by the airport name or name of the city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Check whether the graph is connected or not. Justify the storage representation used.

Flight Graph

Solution and implementation for Q14 from Data Structures and Algorithms Laboratory (dsal).

14_flight_graph.cpp Download

// Code is Updated and simplified.
// Previous code: github.com/AlbatrossC/sppu-codes/commits/main/answers/dsal/14_flight_graph.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class Graph {
private:
    unordered_map<string, vector<pair<string, int>>> adjList;

public:
    void addEdge(string u, string v, int weight) {
        adjList[u].push_back({v, weight});
        adjList[v].push_back({u, weight});
    }

    void display() {
        cout << "Adjacency list:\n";
        for (auto &pair : adjList) {
            cout << pair.first << " -> ";
            for (auto &nb : pair.second) {
                cout << "(" << nb.first << ", " << nb.second << ") ";
            }
            cout << endl;
        }
    }

    void DFSHelper(const string &node, unordered_map<string, bool> &visited) {
        visited[node] = true;
        for (auto &nb : adjList[node]) {
            if (!visited[nb.first]) {
                DFSHelper(nb.first, visited);
            }
        }
    }

    bool isConnected() {
        if (adjList.empty()) {
            return false;
        }

        unordered_map<string, bool> visited;
        DFSHelper(adjList.begin()->first, visited);

        return visited.size() == adjList.size();
    }
};

int main() {
    Graph g;

    g.addEdge("Pune", "Mumbai", 180);
    g.addEdge("Pune", "Nashik", 210);
    g.addEdge("Mumbai", "Nagpur", 480);
    g.addEdge("Nashik", "Nagpur", 450);

    g.display();

    if (g.isConnected()) {
        cout << "The graph is connected.\n";
    } else {
        cout << "The graph is not connected.\n";
    }

    return 0;
}

Group C

Flight Graph

Other Questions in Data Structures and Algorithms Laboratory