目录

拓扑排序

题目 有向图的拓扑排序

解题思路

Java代码

树的 广度优先遍历

题目 树中点的层次

思路

核心代码

代码

---

拓扑排序

含义：

一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。

一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序

题目 有向图的拓扑排序

给定一个 nn 个点 mm 条边的有向图，点的编号是 11 到 nn，图中可能存在重边和自环。

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

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

输入格式

第一行包含两个整数 nn 和 mm。

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

输出格式

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

否则输出 −1−1。

数据范围

1≤n,m≤105

解题思路

首先记录各个点的入度

然后将入度为 0 的点放入队列

将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。

如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。

Java代码

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main{
    static int N = 100010;
    static int[] h = new int[N];       //以第一个节点的编号为索引，存储所有单链表的头节点
    static int[] e = new int[N];       //以当前要操作的节点为索引，存储第二个节点的编号
    static int[] ne = new int[N];      //以当前操作的节点为索引，存储下一个节点
    static int[] d = new int[N];       //存储i号节点的入度
    static int[] top = new int[N];
    static Queue q = new LinkedList<>();
    static int idx,n,cnt = 1;         //cnt指的是top中有多少元素
 
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        int m = in.nextInt();
 
        for(int i = 0; i < N; i ++) h[i] = -1;
 
        for(int i = 0; i < m; i ++)
        {
            int a = in.nextInt();
            int b = in.nextInt();
            add(a,b);
            d[b]++;                    //入度+1
        }
 
        if(topsort())
        {
            for(int i = 1; i <= n; i ++) System.out.print(top[i] + " ");
        }
        else System.out.print("-1");
    }
 
    private static void add(int a ,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
 
    private static boolean topsort()
    {
        for(int i = 1; i <= n; i ++)             //因为是从1开始编号的，所以从1开始遍历
        {
            if(d[i] == 0) q.offer(i);            //遍历每个节点，入度为0就入栈
        }
 
        while(q.size() != 0)
        {
            int t = q.poll();
            top[cnt] = t;
            cnt++;
 
            for(int i =h[t]; i != -1; i = ne[i])  //遍历链表，删除1的所有出度
            {
                int j = e[i];                     //j找到第一个节点指向的点b
                if(--d[j] == 0) q.offer(j);       //删除边
            }
        }
 
        return cnt >= n;                          //注意这里一定是>=,因为cnt = 3以后会++等于4
    }
}

树的 广度优先遍历

题目 树中点的层次

给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 11，点的编号为 1∼n1∼n。

请你求出 11 号点到 nn 号点的最短距离，如果从 11 号点无法走到 nn 号点，输出 −1−1。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 mm 行，每行包含两个整数 aa 和 bb，表示存在一条从 aa 走到 bb 的长度为 11 的边。

输出格式

输出一个整数，表示 11 号点到 nn 号点的最短距离。

思路

用 dist 数组保存1号节点到各个节点的距离，初始时，都是无穷大。

用 st 数组标记各个节点有没有走到过。

从 1 号节点开始，广度优先遍历：

1 号节点入队列，dist[1] 的值更新为 0。

如果队列非空，就取出队头，找到队头节点能到的所有节点。如果队头节点能到走到的节点没有标记过，就将节点的dist值更新为队头的dist值+1，然后入队。

重复步骤 2 直到队列为空。

这个时候，dist数组中就存储了 1 号节点到各个节点的距离了。如果距离是无穷大，则不能到达，输出 -1，如果距离不是无穷大，则能到达，输出距离。

核心代码

for (int i = h[t]; i != -1; i = ne[i]) // ne[i]上的点都是与i节点距离为1的点
        {
            int j = e[i]; // 向外走一步
            if (d[j] == -1) // 如果j没有被遍历过
            {
                d[j] = d[t] + 1; // 因为路径长度都是1，所以直接在上一步的基础上加上1即可
                q.push(j); // 将j加到队列中
            }
        }

代码

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main{
    static int N = 100010;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] d = new int[N];                //储存每个节点距离起点的距离
    static Queue q = new LinkedList<>();
    static boolean[] st = new boolean[N];
    static int idx,n;
 
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        int m = in.nextInt();
 
        for(int i = 0; i < N; i ++)
        {
            h[i] = -1;
            d[i] = -1;
        }
 
        for(int i = 0; i < m; i ++)
        {
            int a = in.nextInt();
            int b = in.nextInt();
            add(a,b);
        }
 
        System.out.print(bfs(1));           //求的是1-n的最短距离，从1开始搜就可以了
    }
 
    private static void add(int a, int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
 
    private static int bfs(int u)
    {
        q.offer(u);
        d[1] = 0;                        //自己距离自己为0，在这里的作用相当于表示走过了
 
        while(q.size() != 0)
        {
            int t = q.poll();
            for(int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];           //j相当于当前节点的子节点,因为当前节点会不满足条件直接跳出循环
                if(d[j] == -1)
                {
                    q.offer(j);
                    d[j] = d[t] + 1;
                }
            }
        }
        return d[n];
    }
}