# Topological sort



* It is an ordering of vertices in a directed acyclic graph in which each node comes before all the nodes to which **it has outgoing edges**
*   Topological sort for this graph will be : A, C, E, B, D\


    ![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LKg0T0Ja_o3vaOhZdJJ%2F-LKg2B_2GjWAzvEdtDI2%2F2018082401.jpg?alt=media\&token=9e223ae7-f31a-408a-b2d5-53a7c83fa3c2)
* We first find a vertex which has no incoming edge (Indegree = 0)
* Remove A, reduce the indegree of all its neighbors
* The next vertex in this sort the one with indegree 0

### Indegree

* Number of inward directed graph edges for a given vertex
* If there were no vertices with 0 indegree, then there would have been no topological sort
  * A = 0
  * B = 2
  * C = 1
  * E = 1
  * D = 2

### Complexity

* Running time for topological sort is O(V + E)
* Each edge and every vertex visited once

## Implementation

### Indegree of adjacency list

```
public int getIndegree(int v) {
    if (v < 0 || v >= numVertices) {
        throw new IllegalArgumentException("Vertex number is not valid");
    }
    int indegree = 0;
    for (int i = 0; i < numVertices; i++) {
        if (getAdjacentVertices(i).contains(v)) {
            indegree++;
        }
    }
    return indegree;
}

override
public int getIndegree(int v) {
    if (v < 0 || v >= numVertices) {
        throw new IllegalArgumentException("Vertex number is not valid");
    }
    int indegree = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if (getAdjacentMatrix[i][v] != 0) {
            indegree++;
        }
    }
    return indegree;
}

public static List<Integer> sort(Graph graph) {
    LinkedList<Integer> queue = new LinkedList<>();
    Map<Integer, Integer> indegreeMap = new HashMap<>();
    
    for (int vertex = 0; vertex < graph.getNumVertices(); vertex++) {
        int indegree = graph.getIndegree(vertex);
        indegreeMap.put(vertex, indegree);
        if (indegree == 0) {
            queue.add(vertex);
        }
    }
    
    List<Integer> sortedList = new ArrayList<>();
    while (!queue.isEmpty()) {
        int vertex = queue.pollLast();
        sortedList.add(vertex);
        
        List<Integer> adjancentVertices = graph.getAdjancentVertices(vertex);
        for (int adjancentVertex : adjancentVertices) {
            int updatedIndegree = indegreeMap.get(adjancentVertex) - 1;
            indegreeMap.remove(adjancentVertex);
            indegreeMap.put(adjancentVertex, updatedIndegree);
            if (updatedIndegree == 0) {
                queue.add(adjancentVertex);
            }
        }
    }
    
    if (sortedList.size() != graph.getNumVertices()) {
        throw new RuntimeException("Vertex number is not valid");
    }
    return sortedList;
}
```

## Student schedule

* We have 2 lists
  * List of courses
  * List od pre-reqs for each course
* Pre-reqs are edges from one course to another - it is a relationship
* All nodes with indegree = 0 are potential courses the student could start with
  * There are many schedule possible



```
public static List<String> order(List<String> courseList, Map<String, List<String>> prereqs) {
    Graph courseGraph = new AdjancentMatrixGraph(courseList.size(), Graph.GraphType.DIRECTED);
    
    Map<String, Integer> courseMap = new HashMap<>();
    Map<Integer, String> idCourseMap = new HashMap<>();
    
    for (int i = 0; i < courseList.size(); i++) {
        courseMap.put(courseList.get(i), i);
        idCourseMap.put(i, courseList.get(i));
    }
    
    for (Map.Entry<String, List<String>> prereq : prereq.entrySet()) {  
        for (String course : prereq.getValue()) {
            courseGraph.addEdge(courseMap.get(prereq.getKey()),
                courseMap.get(course));
        }
    }
    
    List<Integer> courseIdList = TopologicalSort(courseGraph);
    List<Integer> courseScheduleList = new ArrayList<>();
    
    
    for (int courseId : courseIdList) {
        courseScheduleList.add(idCourseMap.get(courseId));
    }
    return courseScheduleList;
}
```
