BFS实现拓扑排序

46 阅读 0 评论 31 点赞

我是靠谱客的博主刻苦砖头，最近开发中收集的这篇文章主要介绍BFS实现拓扑排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题连接
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围
1≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

ac代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] map = new int[m][2];
        for (int i = 0 ; i < m; i ++) {
            map[i][0] = sc.nextInt();
            map[i][1] = sc.nextInt();
        }
//        初始化map 为 图结构
        Graph graph = GetGraph(map);
        getTopoSort(graph);
    }

    private static void getTopoSort(Graph graph) {


        Set<Integer> nodeInt = graph.nodeMaP.keySet();
//        zeroNode
//        zero queue
        Deque<Node> zeroQueue = new LinkedList<>();

        int count = 0;
        for (Integer integer : nodeInt) {
            Node node = graph.nodeMaP.get(integer);
            count ++;
            if (node.in == 0) {
                zeroQueue.addLast(node);
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        Node cur;
        while (!zeroQueue.isEmpty()) {
            cur = zeroQueue.removeFirst();
            ans.add(cur.val);

            for (Node node : cur.nodes) {
                node.in--;
        
                if (node.in == 0) {
                    zeroQueue.addLast(node);
                }
            }
        }
        if (count != ans.size()) {
            System.out.println(-1);
            return;
        }
        for (int i : ans) {
            System.out.print(i + " ");
        }

    }

    private static Graph GetGraph(int[][] map) {
        Graph graph = new Graph();
        for (int[] i : map) {
            int from = i[0];
            int to = i[1];
            Node fromNode;
            if (!graph.nodeMaP.containsKey(from)) {
                fromNode = new Node(from);
                graph.nodeMaP.put(from,fromNode);
            }
            else fromNode  = graph.nodeMaP.get(from);
            Node toNode;
            if (!graph.nodeMaP.containsKey(to)) {
                toNode = new Node(to);
                graph.nodeMaP.put(to,toNode);
            }
            else toNode = graph.nodeMaP.get(to);
//            建边
            fromNode.nodes.add(toNode);

            toNode.in ++;
           

        }
            return  graph;
    }

    private static class Node {
        // 入度
         int in;
         ArrayList<Node> nodes;
         int val;
        public Node(int val) {
            nodes = new ArrayList<>();
            this.val = val;
        }
    }
    
    private static class Graph {
        Map<Integer,Node> nodeMaP ;

        public Graph() {
            nodeMaP = new HashMap<>();
        }
    }
}