Search Example : Course Prerequisites

Section 34.9 Search Example : Course Prerequisites

As a concrete example of using graph search, we will consider the problem of determining what classes are prerequisites (directly or indirectly) for a given class. For example, given the class prerequisite graph shown below, we would like to determine the prerequisites for CS205.

🔗

Figure 34.9.1. A prerequisite chart for a Computer Science major.

🔗

Visually,we can see that the direct prerequisite for CS205 is CS162, and the indirect prerequisites are CS161, CS160, and MTH111. To determine this in a program, we can set up a graph representation of the prerequisite relationships and then perform a search. We will start by considering the structure of the graph we will need.

🔗

We will represent vertices as strings (the course names). Edges will be directed and unweighted. Starting from CS205, we want to work backwards to find all the courses that are prerequisites for CS205. This means we will want our edges pointing in the opposite direction of the arrows in the diagram. So we will have an edge from CS205 to CS162, an edge from CS162 to CS161, an edge from CS161 to CS160, and an edge from CS160 to MTH111.

🔗

Graph<string> prereqGraph;
prereqGraph.addVertex("MTH111");
prereqGraph.addVertex("CS160");
prereqGraph.addVertex("CS161");
...
prereqGraph.addEdge("CS161", "CS160");
prereqGraph.addEdge("CS161", "MTH111");
...

Once the graph is set up, we can perform a search to find all the reachable vertices from a given vertex like CS205. Since we do not care about the path to each prerequisite or the length of the path, we can use either a breadth-first search or a depth-first search. We will use a recursive depth-first search.

🔗

Listing 34.9.2.

🔗

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>

import Graph;

using namespace std;

void dfs(Graph<string>& graph, 
         string vertex,
         unordered_set<string>& visited,
         unordered_map<string, string>& parentMap) {

if (visited.contains(vertex)) {
        return; // Already visited this vertex
    }
    visited.insert(vertex); // Mark this vertex as visited

// Recurse for all neighbors of this vertex
    for (const auto& neighbor : graph.getNeighbors(vertex)) {
        parentMap[neighbor] = vertex;
        dfs(graph, neighbor, visited, parentMap);
    }
}

int main() {
    Graph<string> graph;

graph.addVertex("MTH111");
    graph.addVertex("MTH112");
    graph.addVertex("CS160");
    graph.addVertex("CS161");
    graph.addVertex("CS162");
    graph.addVertex("CS205");

graph.addEdge("CS161", "CS160");
    graph.addEdge("CS161", "MTH111");
    graph.addEdge("MTH112", "MTH111");
    graph.addEdge("CS162", "CS161");
    graph.addEdge("CS205", "CS161");

// Find prerequisites for CS205
    unordered_set<string> visited;
    unordered_map<string, string> parentMap;
    dfs(graph, "CS205", visited, parentMap);
    cout << "Prerequisites for CS205:" << endl;
    for (const auto& prereq : parentMap) {
        cout << prereq.first << " is a prerequisite for " << prereq.second << endl;
    }
}

Checkpoint 34.9.1.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next