判断有向图是否存在环
- 为什么同时需要onPath和visited
- 拓展
拓扑排序
- DFS后续遍历算法
- BFS+贪心算法（Kahn算法）
名流问题

数据结构相关的算法无非两点：遍历 + 访问。那么图的基本遍历方法也很简单，以前就讲过如何从多叉树的遍历框架扩展到图的遍历。

图这种数据结构还有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题。

不过以我的经验呢，像网络流这种问题，你又不是打竞赛的，除非自己特别有兴趣，否则就没必要学了；像最小生成树和最短路径问题，虽然从刷题的角度用到的不多，但它们属于经典算法，学有余力可以掌握一下；像拓扑排序这一类，属于比较基本且有用的算法，应该比较熟练地掌握。

本文就结合具体的算法题，来说说拓扑排序算法原理，因为拓扑排序的对象是有向无环图，所以顺带说一下如何判断图是否有环。

判断有向图是否存在环

先来看看力扣第 207 题「课程表」：

拓扑排序与名流问题 - 图1

函数签名如下：

int[] findOrder(int numCourses, int[][] prerequisites);

题目应该不难理解，什么时候无法修完所有课程？当存在循环依赖的时候。

其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

比如说必须修完课程1才能去修课程3，那么就有一条有向边从节点1指向3。

所以我们可以根据题目输入的prerequisites数组生成一幅类似这样的图：

拓扑排序与名流问题 - 图2

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

好，那么想解决这个问题，首先我们要把题目的输入转化成一幅有向图，然后再判断图中是否存在环。

如何转换成图呢？前文图论基础写过图的两种存储形式，邻接矩阵和邻接表。

以我刷题的经验，常见的存储方式是使用邻接表，比如下面这种结构：

List<Integer>[] graph;

**graph[s]**是一个列表，存储着节点**s**所指向的节点。

所以我们首先可以写一个建图函数：

List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1];
        int to = edge[0];
        // 修完课程 from 才能修课程 to
        // 在图中添加一条从 from 指向 to 的有向边
        graph[from].add(to);
    }
    return graph;
}

图建出来了，怎么判断图中有没有环呢？

先不要急，我们先来思考如何遍历这幅图，只要会遍历，就可以判断图中是否存在环了。

前文图论基础写了 DFS 算法遍历图的框架，无非就是从多叉树遍历框架扩展出来的，加了个visited数组罢了：

// 防止重复遍历同一个节点
boolean[] visited;
// 从节点 s 开始 BFS 遍历，将遍历过的节点标记为 true
void traverse(List<Integer>[] graph, int s) {
    if (visited[s]) {
        return;
    }
    /* 前序遍历代码位置 */
    // 将当前节点标记为已遍历
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    /* 后序遍历代码位置 */
}

那么我们就可以直接套用这个遍历代码：

// 防止重复遍历同一个节点
boolean[] visited;
boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
}
void traverse(List<Integer>[] graph, int s) {
    // 代码见上文
}

注意图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。

这样，就能遍历这幅图中的所有节点了，你打印一下visited数组，应该全是 true。

我曾经说过，图的遍历和遍历多叉树差不多，所以到这里你应该都能很容易理解。

那么如何判断这幅图中是否存在环呢？

你可以把递归函数看成一个在递归树上游走的指针，这里也是类似的：

你也可以把traverse看做在图中节点上游走的指针，只需要再添加一个布尔数组onPath记录当前traverse经过的路径：

boolean[] onPath;
boolean hasCycle = false;
boolean[] visited;
void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 发现环！！！
        hasCycle = true;
    }
    if (visited[s]) {
        return;
    }
    // 将节点 s 标记为已遍历
    visited[s] = true;
    // 开始遍历节点 s
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 节点 s 遍历完成
    onPath[s] = false;
}

这里就有点回溯算法的味道了，在进入节点s的时候将onPath[s]标记为 true，离开时标记回 false，如果发现onPath[s]已经被标记，说明出现了环。

PS：参考贪吃蛇没绕过弯儿咬到自己的场景。

这样，就可以在遍历图的过程中顺便判断是否存在环了，完整代码如下：

// 记录一次 traverse 递归经过的节点
boolean[] onPath;
// 记录遍历过的节点，防止走回头路
boolean[] visited;
// 记录图中是否有环
boolean hasCycle = false;
boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }
    // 只要没有循环依赖可以完成所有课程
    return !hasCycle;
}
void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 出现环
        hasCycle = true;
    }
    if (visited[s] || hasCycle) {
        // 如果已经找到了环，也不用再遍历了
        return;
    }
    // 前序遍历代码位置
    visited[s] = true;
    onPath[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历代码位置
    onPath[s] = false;
}
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 代码见前文
}

这道题就解决了，核心就是判断一幅有向图中是否存在环。

为什么同时需要onPath和visited

根据 DFS 算法遍历图框架，这里visited似乎多余，因为我们已经用onPath（即框架中的visited）控制遍历图时候环的处理，似乎不需要visited：

class Solution {
    // 记录一次 traverse 递归经过的节点
    vector<bool> visited;
    // 记录图中是否有环
    bool hasCycle = false;

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int> >  graph = buildGraph(numCourses, prerequisites);
        visited = vector(numCourses,false);
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
            if(hasCycle) return false;
        }
        // 只要没有循环依赖可以完成所有课程
        return true;

    }

    vector<vector<int> > buildGraph(int numCourses, vector<vector<int>> &prerequisites) {
    // 图中共有 numCourses 个节点
    vector<vector<int> > graph(numCourses,vector<int>());
    for (vector<int> edge : prerequisites) {
        int from = edge[1];
        int to = edge[0];
        // 修完课程 from 才能修课程 to
        // 在图中添加一条从 from 指向 to 的有向边
        graph[from].push_back(to);
    }
    return graph;
}
void traverse(vector<vector<int> >&  graph, int s) {
    if (visited[s]) {
        // 出现环
        hasCycle = true;
    }
    if(hasCycle)  return;
    // 前序遍历代码位置
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历代码位置
    visited[s] = false;
}


};

但是这样会超时！！！！这是因为在最外层遍历所有图节点时候

for (int i = 0; i < numCourses; i++) {
        // 遍历图中的所有节点
        traverse(graph, i);
    }

我们需要visited[s]筛选掉之前的循环已经遍历的节点！！！否则会有大量重复遍历！！所以这里只有visited[s] = true;,最终会把所有节点都打上true。

拓展

不过如果出题人继续恶心你，让你不仅要判断是否存在环，还要返回这个环具体有哪些节点，怎么办？

你可能说，onPath里面为 true 的索引，不就是组成环的节点编号吗？

不是的，假设下图中绿色的节点是递归的路径，它们在onPath中的值都是 true，但显然成环的节点只是其中的一部分：

拓扑排序与名流问题 - 图3

这个问题留给大家思考，我会在公众号留言区置顶正确的答案。

那么接下来，我们来再讲一个经典的图算法：拓扑排序。

拓扑排序

看下力扣第 210 题「课程表 II」：

拓扑排序与名流问题 - 图4

这道题就是上道题的进阶版，不是仅仅让你判断是否可以完成所有课程，而是进一步让你返回一个合理的上课顺序，保证开始修每个课程时，前置的课程都已经修完。

函数签名如下：

int[] findOrder(int numCourses, int[][] prerequisites);

这里我先说一下拓扑排序（Topological Sorting）这个名词，网上搜出来的定义很数学，这里干脆用百度百科的一幅图来让你直观地感受下：

拓扑排序与名流问题 - 图5

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

但是我们这道题和拓扑排序有什么关系呢？

其实也不难看出来，如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。

DFS后续遍历算法

首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数：

public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return new int[]{};
    }
    // ...
}

PS：简单起见，canFinish 直接复用了之前实现的函数，但实际上可以把环检测的逻辑和拓扑排序的逻辑结合起来，同时在 traverse 函数里完成，这个可以留给大家自己去实现。

那么关键问题来了，如何进行拓扑排序？是不是又要秀什么高大上的技巧了？

其实特别简单，将后序遍历的结果进行反转，就是拓扑排序的结果。

直接看解法代码：

boolean[] visited;
// 记录后序遍历结果
List<Integer> postorder = new ArrayList<>();

int[] findOrder(int numCourses, int[][] prerequisites) {
    // 先保证图中无环
    if (!canFinish(numCourses, prerequisites)) {
        return new int[]{};
    }
    // 建图
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 进行 DFS 遍历
    visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
    // 将后序遍历结果反转，转化成 int[] 类型
    Collections.reverse(postorder);
    int[] res = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        res[i] = postorder.get(i);
    }
    return res;
}

void traverse(List<Integer>[] graph, int s) {
    if (visited[s]) {
        return;
    }

    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历位置
    postorder.add(s);
}

// 参考上一题的解法
boolean canFinish(int numCourses, int[][] prerequisites);

// 参考前文代码
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites);

c++代码

class Solution {
    vector<bool> visited;
    vector<bool> onPath;
    bool cycle;
    vector<int> postOrder;
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        visited.resize(numCourses,false);
        onPath.resize(numCourses,false);
        cycle = false;

        vector<vector<int> > graph = buildGraph(numCourses,prerequisites);
        // 进行 DFS 遍历
        for(int i =0;i<numCourses;++i){
            travserse(graph,i);
        }
        // 先保证图中无环
        if(cycle) return vector<int>();
        // 将后序遍历结果反转
        std::reverse(postOrder.begin(), postOrder.end());

        return postOrder;
    }
    vector<vector<int> > buildGraph(int numCourses, vector<vector<int>>& prerequisites){
        vector<vector<int>> graph(numCourses,vector<int>());
        for(auto edge:prerequisites){
            int from = edge[1];
            int to = edge[0];
            graph[from].push_back(to);
        }
        return graph;
    }

    void travserse(vector<vector<int>> graph, int s){
        if(onPath[s]) cycle = true;
        if(visited[s]) return;

        visited[s] = true;
        onPath[s] = true;
        for(int t: graph[s]){
            travserse(graph,t);
        }
        // 后序遍历位置
        postOrder.push_back(s);
        onPath[s] = false;
    }
};

代码虽然看起来多，但是逻辑应该是很清楚的，只要图中无环，那么我们就调用traverse函数对图进行 DFS 遍历，记录后序遍历结果，最后把后序遍历结果反转，作为最终的答案。

那么为什么后序遍历的反转结果就是拓扑排序呢？

我这里也避免数学证明，用一个直观地例子来解释，我们就说二叉树，这是我们说过很多次的二叉树遍历框架：

void traverse(TreeNode root) {
    // 前序遍历代码位置
    traverse(root.left)
    // 中序遍历代码位置
    traverse(root.right)
    // 后序遍历代码位置
}

二叉树的后序遍历是什么时候？遍历完左右子树之后才会执行后序遍历位置的代码。换句话说，当左右子树的节点都被装到结果列表里面了，根节点才会被装进去。

后序遍历的这一特点很重要，之所以拓扑排序的基础是后序遍历，是因为一个任务必须在等到所有的依赖任务都完成之后才能开始开始执行。

你把每个任务理解成二叉树里面的节点，这个任务所依赖的任务理解成子节点，那你是不是应该先把所有子节点处理完再处理父节点？这是不是就是后序遍历？

下图是一个二叉树的后序遍历结果：

拓扑排序与名流问题 - 图6

结合这个图说一说为什么还要把后序遍历结果反转，才是最终的拓扑排序结果。

我们说一个节点可以理解为一个任务，这个节点的子节点理解为这个任务的依赖，但你注意我们之前说的依赖关系的表示：如果做完A才能去做B，那么就有一条从A指向B的有向边，表示B依赖A。

那么，父节点依赖子节点，体现在二叉树里面应该是这样的：

拓扑排序与名流问题 - 图7

是不是和我们正常的二叉树指针指向反过来了？所以正常的后序遍历结果应该进行反转，才是拓扑排序的结果。

以上，我简单解释了一下为什么「拓扑排序的结果就是反转之后的后序遍历结果」，当然，我的解释虽然比较直观，但并没有严格的数学证明，有兴趣的读者可以自己查一下。

总之，你记住拓扑排序就是后序遍历反转之后的结果，且拓扑排序只能针对有向无环图，进行拓扑排序之前要进行环检测，这些知识点已经足够了。

但是，这样写在LeetCode上会超时。这道题用 BFS 和 DFS 都可以完成，只需要掌握 BFS 的写法就可以了，BFS 的写法很经典。

BFS+贪心算法（Kahn算法）

拓扑排序实际上应用的是贪心算法，贪心算法简而言之：每一步最优，则全局最优。

先说最重要的部分：

删除结点的操作，通过「入度数组」体现，这个技巧要掌握；
「拓扑排序」的一个附加效果是：能够顺带检测有向图中是否存在环，这个知识点非常重要，如果在面试的过程中遇到这个问题，要把这一点说出来。具有类似附加功能的算法还有：Bellman-Ford 算法附加的作用是可以用于检测是否有负权环（在这里不展开了，我也不太熟）。

具体到拓扑排序，每一次都从图中删除没有前驱的顶点，这里并不需要真正的做删除操作，我们可以设置一个入度数组，每一轮都输出入度为 0 的结点，并移除它、修改它指向的结点的入度（−1即可），依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除，则说明“不能完成所有课程的学习”。

拓扑排序保证了每个活动（在这题中是“课程”）的所有前驱活动都排在该活动的前面，并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网，这里就不展开了。

算法流程：

1、在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。

2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。

3、当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。

（思考这里为什么要使用队列？如果不用队列，还可以怎么做，会比用队列的效果差还是更好？）

在代码具体实现的时候，除了保存入度为 0 的队列，我们还需要两个辅助的数据结构：

1、邻接表：通过结点的索引，我们能够得到这个结点的后继结点；

2、入度数组：通过结点的索引，我们能够得到指向这个结点的结点个数。

这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。

class Solution {
    vector<int> inDegree;//入度

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        if (numCourses <= 0) {
            return vector<int>();
        }
        inDegree.resize(numCourses,0);
        vector<vector<int> > graph = buildGraph(numCourses,prerequisites);
        queue <int> myQ;
        for(int i = 0;i<numCourses;++i){
            if(inDegree[i]==0) myQ.push(i); //从所有入度为0开始遍历
        }
        // 进行 BFS 遍历
        vector<int> res(numCourses);
        // 当前结果集列表里的元素个数，正好可以作为下标
        int count = 0;
        while(!myQ.empty()){
            // 当前入度为 0 的结点
            int head = myQ.front();
            myQ.pop();
            res[count] = head;
            count++;

            vector<int> successors = graph[head];
            for (int nextCourse : successors) {
                inDegree[nextCourse]--;
                // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                if (inDegree[nextCourse] == 0) {
                    myQ.push(nextCourse);
                }
            }
        }

        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        if (count == numCourses) {
            return res;
        }
        return vector<int>();
    }
    vector<vector<int> > buildGraph(int numCourses, vector<vector<int>>& prerequisites){
        vector<vector<int>> graph(numCourses,vector<int>());
        for(auto edge:prerequisites){
            int from = edge[1];
            int to = edge[0];
            inDegree[to]++;
            graph[from].push_back(to);
        }
        return graph;
    }
};

java版本

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }

        HashSet<Integer>[] adj = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new HashSet<>();
        }

        // [1,0] 0 -> 1
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj[p[1]].add(p[0]);
            inDegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] res = new int[numCourses];
        // 当前结果集列表里的元素个数，正好可以作为下标
        int count = 0;

        while (!queue.isEmpty()) {
            // 当前入度为 0 的结点
            Integer head = queue.poll();
            res[count] = head;
            count++;

            Set<Integer> successors = adj[head];
            for (Integer nextCourse : successors) {
                inDegree[nextCourse]--;
                // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }

        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        if (count == numCourses) {
            return res;
        }
        return new int[0];
    }
}

名流问题

再来讨论一个经典的「名流问题」：

给你n个人的社交关系（你知道任意两个人之间是否认识），然后请你找出这些人中的「名人」。

所谓「名人」有两个条件：1、所有其他人都认识「名人」。2、「名人」不认识任何其他人。

这是一个图相关的算法问题，社交关系嘛，本质上就可以抽象成一幅图。

如果把每个人看做图中的节点，「认识」这种关系看做是节点之间的有向边，那么名人就是这幅图中一个特殊的节点：

拓扑排序与名流问题 - 图8

这个节点没有一条指向其他节点的有向边；且其他所有节点都有一条指向这个节点的有向边。

或者说的专业一点，名人节点的出度为 0，入度为n - 1。

那么，这n个人的社交关系是如何表示的呢？

前文图论算法基础说过，图有两种存储形式，一种是邻接表，一种是邻接矩阵，邻接表的主要优势是节约存储空间；邻接矩阵的主要优势是可以迅速判断两个节点是否相邻。

对于名人问题，显然会经常需要判断两个人之间是否认识，也就是两个节点是否相邻，所以我们可以用邻接表来表示人和人之间的社交关系。

那么，把名流问题描述成算法的形式就是这样的：

给你输入一个大小为n x n的二维数组（邻接矩阵）graph表示一幅有n个节点的图，每个人都是图中的一个节点，编号为0到n - 1。

如果graph[i][j] == 1代表第i个人认识第j个人，如果graph[i][j] == 0代表第i个人不认识第j个人。

有了这幅图表示人与人之间的关系，请你计算，这n个人中，是否存在「名人」？

如果存在，算法返回这个名人的编号，如果不存在，算法返回 -1。

函数签名如下：

int findCelebrity(int[][] graph);

比如输入的领接矩阵长这样：

拓扑排序与名流问题 - 图9

那么算法应该返回 2，节点 2 符合名人的特性。

力扣第 277 题「搜寻名人」就是这个经典问题，不过并不是直接把邻接矩阵传给你，而是只告诉你总人数n，同时提供一个 APIknows来查询人和人之间的社交关系：

// 可以直接调用，能够返回 i 是否认识 j
boolean knows(int i, int j);

// 请你实现：返回「名人」的编号
int findCelebrity(int n) {
    // todo
}

很明显，knowsAPI 本质上还是在访问邻接矩阵。为了简单起见，我们后面就按力扣的题目形式来探讨一下这个经典问题。

暴力解法

我们拍拍脑袋就能写出一个简单粗暴的算法：

int findCelebrity(int n) {
    for (int cand = 0; cand < n; cand++) {
        int other;
        for (other = 0; other < n; other++) {
            if (cand == other) continue;
            // 保证其他人都认识 cand，且 cand 不认识任何其他人
            // 否则 cand 就不可能是名人
            if (knows(cand, other) || !knows(other, cand)) {
                break;
            }
        }
        if (other == n) {
            // 找到名人
            return cand;
        }
    }
    // 没有一个人符合名人特性
    return -1;
}

cand是候选人（candidate）的缩写，我们的暴力算法就是从头开始穷举，把每个人都视为候选人，判断是否符合「名人」的条件。

刚才也说了，knows函数底层就是在访问一个二维的邻接矩阵，一次调用的时间复杂度是 O(1)，所以这个暴力解法整体的最坏时间复杂度是 O(N^2)。

那么，是否有其他高明的办法来优化时间复杂度呢？其实是有优化空间的，你想想，我们现在最耗时的地方在哪里？

对于每一个候选人cand，我们都要用一个内层 for 循环去判断这个cand到底符不符合「名人」的条件。

这个内层 for 循环看起来就蠢，虽然判断一个人「是名人」必须用一个 for 循环，但判断一个人「不是名人」就不用这么麻烦了。

因为「名人」的定义保证了「名人」的唯一性，所以我们可以利用排除法，先排除那些显然不是「名人」的人，从而避免 for 循环的嵌套，降低时间复杂度。

优化解法

我再重复一遍所谓「名人」的定义：

1、所有其他人都认识名人。

2、名人不认识任何其他人。

这个定义就很有意思，它保证了人群中最多有一个名人。

这很好理解，如果有两个人同时是名人，那么这两条定义就自相矛盾了。

换句话说，只要观察任意两个候选人的关系，我一定能确定其中的一个人不是名人，把他排除。

至于另一个候选人是不是名人，只看两个人的关系肯定是不能确定的，但这不重要，重要的是排除掉一个必然不是名人的候选人，缩小了包围圈。

这是优化的核心，也是比较难理解的，所以我们先来说说为什么观察任意两个候选人的关系，就能排除掉一个。

你想想，两个人之间的关系可能是什么样的？

无非就是四种：你认识我我不认识你，我认识你你不认识我，咱俩互相认识，咱两互相不认识。

如果把人比作节点，红色的有向边表示不认识，绿色的有向边表示认识，那么两个人的关系无非是如下四种情况：

拓扑排序与名流问题 - 图10

不妨认为这两个人的编号分别是cand和other，然后我们逐一分析每种情况，看看怎么排除掉一个人。

对于情况一，cand认识other，所以cand肯定不是名人，排除。因为名人不可能认识别人。

对于情况二，other认识cand，所以other肯定不是名人，排除。

对于情况三，他俩互相认识，肯定都不是名人，可以随便排除一个。

对于情况四，他俩互不认识，肯定都不是名人，可以随便排除一个。因为名人应该被所有其他人认识。

综上，只要观察任意两个之间的关系，就至少能确定一个人不是名人，上述情况判断可以用如下代码表示：

if (knows(cand, other) || !knows(other, cand)) {
    // cand 不可能是名人
} else {
    // other 不可能是名人
}

如果能够理解这一个特点，那么写出优化解法就简单了。

我们可以不断从候选人中选两个出来，然后排除掉一个，直到最后只剩下一个候选人，这时候再使用一个 for 循环判断这个候选人是否是货真价实的「名人」。

这个思路的完整代码如下：

int findCelebrity(int n) {
    if (n == 1) return 0;
    // 将所有候选人装进队列
    LinkedList<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        q.addLast(i);
    }
    // 一直排除，直到只剩下一个候选人停止循环
    while (q.size() >= 2) {
        // 每次取出两个候选人，排除一个
        int cand = q.removeFirst();
        int other = q.removeFirst();
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人，排除，让 other 归队
            q.addFirst(other);
        } else {
            // other 不可能是名人，排除，让 cand 归队
            q.addFirst(cand);
        }
    }

    // 现在排除得只剩一个候选人，判断他是否真的是名人
    int cand = q.removeFirst();
    for (int other = 0; other < n; other++) {
        if (other == cand) {
            continue;
        }
        // 保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
}

这个算法避免了嵌套 for 循环，时间复杂度降为 O(N) 了，不过引入了一个队列来存储候选人集合，使用了 O(N) 的空间复杂度。

PS：LinkedList的作用只是充当一个容器把候选人装起来，每次找出两个进行比较和淘汰，但至于具体找出哪两个，都是无所谓的，也就是说候选人归队的顺序无所谓，我们用的是addFirst只是方便后续的优化，你完全可以用addLast，结果都是一样的。

是否可以进一步优化，把空间复杂度也优化掉？

最终解法

如果你能够理解上面的优化解法，其实可以不需要额外的空间解决这个问题，代码如下：

int findCelebrity(int n) {
    // 先假设 cand 是名人
    int cand = 0;
    for (int other = 1; other < n; other++) {
        if (!knows(other, cand) || knows(cand, other)) {
            // cand 不可能是名人，排除
            // 假设 other 是名人
            cand = other;
        } else {
            // other 不可能是名人，排除
            // 什么都不用做，继续假设 cand 是名人
        }
    }

    // 现在的 cand 是排除的最后结果，但不能保证一定是名人
    for (int other = 0; other < n; other++) {
        if (cand == other) continue;
        // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }

    return cand;
}

我们之前的解法用到了LinkedList充当一个队列，用于存储候选人集合，而这个优化解法利用other和cand的交替变化，模拟了我们之前操作队列的过程，避免了使用额外的存储空间。

现在，解决名人问题的解法时间复杂度为 O(N)，空间复杂度为 O(1)，已经是最优解法了。