算法题/拓扑排序：任务调度

题目

有N个任务，从0到N-1。每个任务都有一些先决条件任务，这些任务需要在调度之前完成。给定任务的数量和先决条件对的列表，找出是否有可能安排所有任务。

示例：

输入：Tasks=3, Prerequisites=[0,1], [1,2]
输出：[0, 1, 2]

解答

Java

import java.util.*;

class TopologicalSort {
  public static List<Integer> sort(int vertices, int[][] edges) {
    List<Integer> sortedOrder = new ArrayList<>();
    if (vertices <= 0)
      return sortedOrder;

    // a. 初始化图
    HashMap<Integer, Integer> inDegree = new HashMap<>(); // 计算每个节点的入度
    HashMap<Integer, List<Integer>> graph = new HashMap<>(); // 邻接链表图
    for (int i = 0; i < vertices; i++) {
      inDegree.put(i, 0);
      graph.put(i, new ArrayList<Integer>());
    }

    // b. 构建图
    for (int i = 0; i < edges.length; i++) {
      int parent = edges[i][0], child = edges[i][1];
      graph.get(parent).add(child); // 将孩子添加到父结点的list中
      inDegree.put(child, inDegree.get(child) + 1); // 增加孩子的入度
    }

    // c. 找到所有的源节点，源节点入度为0
    Queue<Integer> sources = new LinkedList<>();
    for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
      if (entry.getValue() == 0)
        sources.add(entry.getKey());
    }

    // d. 对于每一个源节点，添加它到已排序list中，同时将它的所有孩子节点入度减一
    // 如果一个孩子节点的入度变成1，添加它到源队列中
    while (!sources.isEmpty()) {
      int vertex = sources.poll();
      sortedOrder.add(vertex);
      List<Integer> children = graph.get(vertex); // 获取该节点的子节点，并将入度减1
      for (int child : children) {
        inDegree.put(child, inDegree.get(child) - 1);
        if (inDegree.get(child) == 0)
          sources.add(child);
      }
    }

    return sortedOrder.size() == vertices;
  }

  public static void main(String[] args) {
    List<Integer> result = TopologicalSort.sort(4,
        new int[][] { new int[] { 3, 2 }, new int[] { 3, 0 }, new int[] { 2, 0 }, new int[] { 2, 1 } });
    System.out.println(result);

    result = TopologicalSort.sort(5, new int[][] { new int[] { 4, 2 }, new int[] { 4, 3 }, new int[] { 2, 0 },
        new int[] { 2, 1 }, new int[] { 3, 1 } });
    System.out.println(result);

    result = TopologicalSort.sort(7, new int[][] { new int[] { 6, 4 }, new int[] { 6, 2 }, new int[] { 5, 3 },
        new int[] { 5, 4 }, new int[] { 3, 0 }, new int[] { 3, 1 }, new int[] { 3, 2 }, new int[] { 4, 1 } });
    System.out.println(result);
  }
}

JavaScript

class TopologicalSort {
  static sort(vertices, edges) {
    let sortedOrder = [];
    if (vertices <= 0)
      return sortedOrder;

    // a. 初始化图
    let inDegree = new Map(); // 计算每个节点的入度
    let graph = new Map(); // 邻接链表图
    for (let i = 0; i < vertices; i++) {
      inDegree.set(i, 0);
      graph.set(i, []);
    }

    // b. 构建图
    for (let i = 0; i < edges.length; i++) {
      let parent = edges[i][0], child = edges[i][1];
      graph.get(parent).push(child); // 将孩子添加到父结点的list中
      inDegree.set(child, inDegree.get(child) + 1); // 增加孩子的入度
    }

    // c. 找到所有的源节点，源节点入度为0
    let sources = [];
    for (let [key, value] of inDegree.entries()) {
      if (value === 0)
        sources.push(key);
    }

    // d. 对于每一个源节点，添加它到已排序list中，同时将它的所有孩子节点入度减一
    // 如果一个孩子节点的入度变成1，添加它到源队列中
    while (sources.length > 0) {
      let vertex = sources.shift();
      sortedOrder.push(vertex);
      let children = graph.get(vertex); // 获取该节点的子节点，并将入度减1
      for (let child of children) {
        inDegree.set(child, inDegree.get(child) - 1);
        if (inDegree.get(child) === 0)
          sources.push(child);
      }
    }

    return sortedOrder.length === vertices;
  }
}

let result = TopologicalSort.sort(4, [
  [3, 2],
  [3, 0],
  [2, 0],
  [2, 1]
]);
console.log(result);

result = TopologicalSort.sort(5, [
  [4, 2],
  [4, 3],
  [2, 0],
  [2, 1],
  [3, 1]
]);
console.log(result);

result = TopologicalSort.sort(7, [
  [6, 4],
  [6, 2],
  [5, 3],
  [5, 4],
  [3, 0],
  [3, 1],
  [3, 2],
  [4, 1]
]);
console.log(result);

Python

from collections import defaultdict, deque

class TopologicalSort:
    @staticmethod
    def sort(vertices, edges):
        sorted_order = []
        if vertices <= 0:
            return sorted_order

        # a. 初始化图
        in_degree = defaultdict(int) # 计算每个节点的入度
        graph = defaultdict(list) # 邻接链表图
        for i in range(vertices):
            in_degree[i] = 0
            graph[i] = []

        # b. 构建图
        for edge in edges:
            parent, child = edge[0], edge[1]
            graph[parent].append(child) # 将孩子添加到父节点的列表中
            in_degree[child] += 1 # 增加孩子的入度

        # c. 找到所有的源节点，源节点入度为0
        sources = deque()
        for key, value in in_degree.items():
            if value == 0:
                sources.append(key)

        # d. 对于每一个源节点，添加它到已排序列表中，同时将它的所有孩子节点入度减一
        # 如果一个孩子节点的入度变成0，添加它到源队列中
        while sources:
            vertex = sources.popleft()
            sorted_order.append(vertex)
            children = graph[vertex] # 获取该节点的子节点，并将入度减1
            for child in children:
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    sources.append(child)

        return sorted_order if len(sorted_order) == vertices else []

result = TopologicalSort.sort(4, [
    [3, 2],
    [3, 0],
    [2, 0],
    [2, 1]
])
print(result)

result = TopologicalSort.sort(5, [
    [4, 2],
    [4, 3],
    [2, 0],
    [2, 1],
    [3, 1]
])
print(result)

result = TopologicalSort.sort(7, [
    [6, 4],
    [6, 2],
    [5, 3],
    [5, 4],
    [3, 0],
    [3, 1],
    [3, 2],
    [4, 1]
])
print(result)

Go

package main

import (
	"fmt"
)

type TopologicalSort struct{}

func (ts *TopologicalSort) Sort(vertices int, edges [][]int) []int {
	sortedOrder := []int{}
	if vertices <= 0 {
		return sortedOrder
	}

	// a. 初始化图
	inDegree := make(map[int]int)         // 计算每个节点的入度
	graph := make(map[int][]int)          // 邻接链表图
	for i := 0; i < vertices; i++ {
		inDegree[i] = 0
		graph[i] = []int{}
	}

	// b. 构建图
	for _, edge := range edges {
		parent, child := edge[0], edge[1]
		graph[parent] = append(graph[parent], child) // 将孩子添加到父节点的切片中
		inDegree[child]++                             // 增加孩子的入度
	}

	// c. 找到所有的源节点，源节点入度为0
	sources := []int{}
	for key, value := range inDegree {
		if value == 0 {
			sources = append(sources, key)
		}
	}

	// d. 对于每一个源节点，添加它到已排序切片中，同时将它的所有孩子节点入度减一
	// 如果一个孩子节点的入度变成0，添加它到源切片中
	for len(sources) > 0 {
		vertex := sources[0]
		sources = sources[1:]
		sortedOrder = append(sortedOrder, vertex)
		children := graph[vertex] // 获取该节点的子节点，并将入度减1
		for _, child := range children {
			inDegree[child]--
			if inDegree[child] == 0 {
				sources = append(sources, child)
			}
		}
	}

	if len(sortedOrder) == vertices {
		return sortedOrder
	} else {
		return []int{}
	}
}

func main() {
	ts := &TopologicalSort{}

	result := ts.Sort(4, [][]int{
		{3, 2},
		{3, 0},
		{2, 0},
		{2, 1},
	})
	fmt.Println(result)

	result = ts.Sort(5, [][]int{
		{4, 2},
		{4, 3},
		{2, 0},
		{2, 1},
		{3, 1},
	})
	fmt.Println(result)

	result = ts.Sort(7, [][]int{
		{6, 4},
		{6, 2},
		{5, 3},
		{5, 4},
		{3, 0},
		{3, 1},
		{3, 2},
		{4, 1},
	})
	fmt.Println(result)
}