In academic institutions, courses often have prerequisite dependencies. For instance, a course like Data Structures may require students to complete Introduction to Programming and Discrete Mathematics first. The challenge is to determine a valid sequence for scheduling all courses such that no course is taken before its prerequisites.

This problem can be modeled using an AOV (Activity On Vertex) network, where each vertex represents a course, and a directed edge from vertex A to vertex B indicates that course A must be completed before course B.

Design Requirements

1. Cycle Detection: If the input course relationships contain a cycle, the program must detect and report the error without terminating, allowing the user to re-enter valid data.
2. Topological Ordering: Given the courses and their prerequisite relationships, compute and output a valid topological sequence for the curriculum.
3. Input Validation: When entering edge relationships (prerequisite → dependent), verify that both endpoints exist in the course list. Report errors for invalid vertices and allow re-entry.
4. Network Visualizasion: After constructing the AOV network, display its structure including vertex count, vertex names, edge count, and edge details (source → destination).
5. Result Output: Display the computed course sequence or appropriate error messages.

Data Structure Design

The implementation uses an adjacency list representation for the directed graph:

#define MAX_COURSES 100

// Edge node structure
typedef struct EdgeNode {
    int targetVertex;           // Index of the destination vertex
    struct EdgeNode *nextEdge;  // Pointer to the next edge
} EdgeNode;

// Vertex node structure
typedef struct VertexNode {
    int courseLabel;            // Course identifier
    int inDegree;               // Number of incoming edges
    EdgeNode *firstEdge;        // Pointer to the first outgoing edge
} VertexNode;

// Graph structure
typedef struct {
    VertexNode vertices[MAX_COURSES];
    int vertexCount;
    int edgeCount;
} CourseGraph;

Topological Sort Algorithm

The algorithm uses a stack to track vertices with zero in-degree:

int performTopologicalSort(CourseGraph *graph) {
    EdgeNode *edgePtr;
    int currentVertex, nextVertex, stackTop;
    int processedCount = 0;
    int zeroInDegreeStack[MAX_COURSES];
    
    stackTop = -1;
    
    // Initialize stack with vertices having zero in-degree
    for (int i = 0; i < graph->vertexCount; i++) {
        if (graph->vertices[i].inDegree == 0) {
            zeroInDegreeStack[++stackTop] = i;
        }
    }
    
    // Process vertices until stack is empty
    while (stackTop != -1) {
        currentVertex = zeroInDegreeStack[stackTop--];
        
        printf("Course%d -> ", graph->vertices[currentVertex].courseLabel + 1);
        processedCount++;
        
        // Traverse all outgoing edges and reduce in-degree of neighbors
        for (edgePtr = graph->vertices[currentVertex].firstEdge; edgePtr != NULL; edgePtr = edgePtr->nextEdge) {
            nextVertex = edgePtr->targetVertex;
            graph->vertices[nextVertex].inDegree--;
            
            // If in-degree becomes zero, push to stack
            if (graph->vertices[nextVertex].inDegree == 0) {
                zeroInDegreeStack[++stackTop] = nextVertex;
            }
        }
    }
    
    // Check for cycles
    if (processedCount < graph->vertexCount) {
        printf("\nError: Cycle detected in the course prerequisites!\n");
        return ERROR_CODE;
    }
    
    return SUCCESS_CODE;
}

Main Program Flow

int main(void) {
    int userChoice;
    
    while (1) {
        printf("\n========== Course Scheduling System ==========\n");
        printf("1. Build Course Dependency Network\n");
        printf("2. Exit Program\n");
        printf("Enter your choice: ");
        
        scanf("%d", &userChoice);
        
        if (userChoice == 1) {
            CourseGraph courseNetwork;
            int result = initializeGraph(&courseNetwork);
            
            if (result == INVALID_EDGE_ERROR) {
                printf("Invalid edge detected. Please try again.\n");
            } else if (result == CYCLE_DETECTED) {
                printf("Cycle found in prerequisites. Please revise inputs.\n");
            } else if (result == USER_CANCEL) {
                printf("Returning to main menu...\n");
            }
        } else if (userChoice == 2) {
            printf("Program terminated successfully.\n");
            break;
        } else {
            printf("Invalid option. Please select 1 or 2.\n");
        }
    }
    
    return 0;
}

Graph Initialization

int initializeGraph(CourseGraph *graph) {
    int numCourses, numEdges;
    int source, destination;
    EdgeNode *newEdge;
    
    printf("Enter the number of courses: ");
    scanf("%d", &numCourses);
    graph->vertexCount = numCourses;
    
    // Initialize vertices
    for (int i = 0; i < numCourses; i++) {
        graph->vertices[i].courseLabel = i;
        graph->vertices[i].inDegree = 0;
        graph->vertices[i].firstEdge = NULL;
    }
    
    printf("Enter the number of prerequisite relationships: ");
    scanf("%d", &numEdges);
    graph->edgeCount = numEdges;
    
    // Input edges
    for (int i = 0; i < numEdges; i++) {
        printf("Enter prerequisite pair (source destination): ");
        scanf("%d %d", &source, &destination);
        
        // Validate vertices
        if (source < 0 || source >= numCourses || destination < 0 || destination >= numCourses) {
            printf("Error: Vertex index out of bounds!\n");
            return INVALID_EDGE_ERROR;
        }
        
        // Create new edge
        newEdge = (EdgeNode *)malloc(sizeof(EdgeNode));
        newEdge->targetVertex = destination;
        newEdge->nextEdge = graph->vertices[source].firstEdge;
        graph->vertices[source].firstEdge = newEdge;
        
        // Increment in-degree of destination
        graph->vertices[destination].inDegree++;
    }
    
    return SUCCESS_CODE;
}

Sample Output

Input Example:

• Courses: 6 (C0, C1, C2, C3, C4, C5)
• Prerequisites: C0→C2, C0→C3, C1→C3, C1→C4, C2→C5, C3→C5

Topological Order Output:

Course1 -> Course2 -> Course3 -> Course4 -> Course5 -> Course6 ->

Cycle Detection Output:

Error: Cycle detected in the course prerequisites!