拓扑排序

题目

有向图(具有单向边的图)的拓扑排序是其顶点的线性排序，这样对于从顶点U到顶点V的每一条有向边(U, V)，在排序中U排在V之前。给出一个有向图，求其顶点的拓扑顺序。

示例1：

输入：Vertices=4, Edges=[3,2], [3,0], [2,0], [2,1]
输出：3,2,0,1 和 3,2,1,0

解答

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);
      }
    }

    if (sortedOrder.size() != vertices) // 排序了的list的大小和图的节点数不一致，则图中存在环
      return new ArrayList<>();

    return sortedOrder;
  }

  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);
  }
}

function topologicalSort(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, child] = edges[i];
    graph.get(parent).push(child); // 将孩子添加到父结点的数组中
    inDegree.set(child, inDegree.get(child) + 1); // 增加孩子的入度
  }

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

  // d. 对于每一个源节点，添加它到已排序数组中，同时将它的所有孩子节点入度减一
  // 如果一个孩子节点的入度变成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);
    }
  }

  if (sortedOrder.length !== vertices) return [];

  return sortedOrder;
}

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

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

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

from collections import defaultdict, deque

def topological_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
        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)

    if len(sorted_order) != vertices:  # 排序了的列表的大小和图的节点数不一致，则图中存在环
        return []

    return sorted_order

result = topological_sort(4, [
    [3, 2],
    [3, 0],
    [2, 0],
    [2, 1]
])
print(result)

result = topological_sort(5, [
    [4, 2],
    [4, 3],
    [2, 0],
    [2, 1],
    [3, 1]
])
print(result)

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

package main

import (
	"fmt"
)

type Queue []int

func (q *Queue) Push(item int) {
	*q = append(*q, item)
}

func (q *Queue) Pop() int {
	item := (*q)[0]
	*q = (*q)[1:]
	return item
}

func topologicalSort(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 i := 0; i < len(edges); i++ {
		parent, child := edges[i][0], edges[i][1]
		graph[parent] = append(graph[parent], child) // 将孩子添加到父结点的切片中
		inDegree[child]++                             // 增加孩子的入度
	}

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

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

	if len(sortedOrder) != vertices { // 排序了的切片的大小和图的节点数不一致，则图中存在环
		return []int{}
	}

	return sortedOrder
}

func main() {
	result := topologicalSort(4, [][]int{
		{3, 2},
		{3, 0},
		{2, 0},
		{2, 1},
	})
	fmt.Println(result)

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

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