离散图论1：基础

基础理论

度：

对于无向图

度指的是该节点与相邻节点的总边数

对于有向图:

节点（顶点）的入度是指进入该节点的边的条数；
节点（顶点）的出度是指从该节点出发的边的条数。

度为0的顶点称为孤立顶点。
度为1的顶点称为叶节点或端点，与该顶点相关联的边称为悬挂边。在右图中，{3,5}是一条悬挂边。这个术语在数据结构与图论中对树的研究中很常见。
有n个顶点的图中度为n-1的顶点称为全连接顶点。

算法应用：

在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：
小镇的法官不相信任何人。每个人（除了小镇法官外）都信任小镇的法官。只有一个人同时满足条件 1 和条件 2 。给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -1。
输入：n = 2, trust = [[1,2]]
输出：2

在此场景中，可以把a对b的信任表示为a指向b的有向边，小镇的信任关系表示为一个有向图。

统计所有的顶点的度（每个人对其他人的信任关系）：出度包含所有顶点并且入度为0的顶点则为法官。

public int findJudge(int n, int[][] trust) {
        int[] in = new int[n + 1],
                out = new int[n + 1];
        for (int[] t : trust) {
            int a = t[0], b = t[1];
            in[b]++;
            out[a]++;
        }
        for (int i = 1; i <= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) return i;
        }
        return -1;
    }

遍历：

图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。

所以，如果图包含环，遍历框架就要一个visited数组进行辅助：

    Graph graph;
        boolean[] visited;

        /* 图遍历框架 */
        void traverse(Graph graph, int s) {
        if (visited[s]) return;
        // 经过节点 s
        visited[s] = true;
        for (TreeNode neighbor : graph.neighbors(s))
        traverse(neighbor);
        // 离开节点 s
        visited[s] = false;
        }