> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/graph/topology-sort.md).

# Topology Sort

## Topology Sort

1. BFS
   1. Use Map to store the flowing times of each node
   2. Use Queue to store the initial node of graph
   3. A node is added when its all sources are traversed

```java
/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

public class Solution {
    /*
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Integer> map = new HashMap<>();

        // Count the flow in number of each node 
        for (DirectedGraphNode node: graph){
            for (DirectedGraphNode neighbor: node.neighbors){
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }

        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        // Find the heads of graph
        for (DirectedGraphNode node: graph){
            if (!map.containsKey(node)){
                queue.add(node);
                ans.add(node);
            }
        }

        // start to put node to ans
        while(!queue.isEmpty()){
            DirectedGraphNode curNode = queue.poll();
            for (DirectedGraphNode node: curNode.neighbors){
                map.put(node , map.get(node) - 1);
                if (map.get(node) == 0){
                   queue.add(node);
                   ans.add(node);
                }
            }
        }
        return ans;
    }
}
```

1. DFS
   1. Use map to record the flowing in times of each node
   2. Find out the initial node of graph and put them into stack
   3. A boolean array to record "traversed"
   4. Use dfs and a stack to push leaf node first, parent node last

```java
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Integer> map = new HashMap<>();

        // Count the flow in number of each node 
        for (DirectedGraphNode node: graph){
            for (DirectedGraphNode neighbor: node.neighbors){
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }

        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        Stack<DirectedGraphNode> stack = new Stack<>();
        boolean[] traversed = new boolean[graph.size()];

        for (DirectedGraphNode node: graph){
            if (!map.containsKey(node)){
                dfs(stack, traversed, node);
            }
        }

        while(!stack.isEmpty()){
            ans.add(stack.pop());
        }

        return ans;
    }

    private void dfs(Stack<DirectedGraphNode> stack, boolean[] traversed, DirectedGraphNode node){
        traversed[node.label] = true;
        for (DirectedGraphNode neighbor: node.neighbors){
            if (traversed[neighbor.label] == false){
                dfs(stack, traversed, neighbor);
            }
        }
        stack.push(node);
    }
```

## 210 Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: \[0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

```python
from collections import defaultdict
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(set)
        degree = defaultdict(int)
        
        for c1, c2 in prerequisites:
            graph[c2].add(c1)
            degree[c1]+=1    
        
        q = []
        ans = []
        for i in range(numCourses):
            if i not in degree:
                q.append(i)
                
        while q:
            c = q.pop(0)
            ans.append(c)
            for nei in graph[c]:
                degree[nei]-=1
                if degree[nei] == 0:
                    q.append(nei)
                    
        return ans if len(ans) == numCourses else []
```

## 269 Alien Dictionary

E.g.

```
Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"
```

* 1. Similar to topology sort, 但比較對象變成word to word 第一個發生變化的char
  2. 若char已經比較過則不允許增加degree，注意 if condition 後break的時機

```python
from collections import defaultdict
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)
        degree = defaultdict(int)
        
        for word in words:
            for ch in word:
                graph[ch] = set()
           
        for i in range(1, len(words)):
            pre = words[i-1]
            cur = words[i]
            size = min(len(pre), len(cur))
            getOrder = False
            for j in range(size):
                c1 = pre[j]
                c2 = cur[j]
                if c1 != c2:
                    getOrder = True
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        degree[c2] += 1
                    break
                    
            # invalid  ['abc', 'ab']
            if not getOrder and len(pre) > len(cur):
                return ''          
        
        q = []
        for k in graph.keys():
            if k not in degree:
                q.append(k)

                
        build = ''
        
        while q:
            w = q.pop(0)
            build += w
            for nxt in graph[w]:
                degree[nxt] -= 1
                if degree[nxt] == 0:
                    q.append(nxt)
        print(build)
        return build if len(build) == len(graph) else ''
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/graph/topology-sort.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.