C++算法之指针三剑客---图

图

1.数据结构介绍

作为指针三剑客之三，图是树的升级版。图通常分为有向（directed）或无向（undirected），有循环（cyclic）或无循环（acyclic），所有节点相连（connected）或不相连（disconnected）。树即是
一个相连的无向无环图，而另一种很常见的图是有向无环图（Directed Acyclic Graph，DAG）。

图通常有两种表示方法。假设图中一共有 n 个节点、m 条边。第一种表示方法是邻接矩阵 （adjacency matrix）：我们可以建立一个 n× n 的矩阵 G，如果第 i 个节点连向第 j 个节点，则 G[i][j]= 1，反之为 0；如果图是无向的，则这个矩阵一定是对称矩阵，即 G[i][j] = G[j][i]。第二种表示方法是邻接链表（adjacency list）：我们可以建立一个大小为 n 的数组，每个位置 i 储存一个数组或者链表，表示第 i 个节点连向的其它节点。邻接矩阵空间开销比邻接链表大，但是邻接链表不支持快速查找 i 和 j 是否相连，因此两种表示方法可以根据题目需要适当选择。除此之外，我们也可以直接用一个 m × 2 的矩阵储存所有的边。

2.二分图

二分图算法也称为染色法，是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么图为二分。

题目一：给定一个图，判断其是否可以二分。

利用队列和广度优先搜索，我们可以对未染色的节点进行染色，并且检查是否有颜色相同的相邻节点存在。注意在代码中，我们用 0 表示未检查的节点，用 1 和 2 表示两种不同的颜色。

bool isBipartite(vector<vector<int>>&graph)
{
    int n=graph.size();
    if(n==0){
        return true;
    }
    vector<int>color(n,0);
    queue<int>q;
    for(int i=0;i<n;++i)
    {
        if(!color[i]){
            q.push(i);
            color[i]=1;
        }
        while(!q.empty()){
            int node=q.front();
            q.pop();
            for(const int & j:graph[node]){
                if(color[j]==0){
                    q.push(j);
                    color[j]=color[node]==2?1:2;
                }
                else if(color[node]==color[j]){
                    rerturn false;
                }
            }
        }
    }
    rerturn true;
}
    

2.拓扑排序

拓扑排序（topological sort）是一种常见的，对有向无环图排序的算法。给定有向无环图中的N 个节点，我们把它们排序成一个线性序列；若原图中节点 i 指向节点 j，则排序结果中 i 一定在j 之前。拓扑排序的结果不是唯一的，只要满足以上条件即可。

题目一：给定N个课程和这些课程的前置必修课，求可以一次性完成所有课的顺序。

我们可以先建立一个邻接矩阵表示图，方便进行直接查找。这里注意我们将所有的边反向，使得如果课程 i 指向课程 j，那么课程 i 需要在课程 j 前面先修完。这样更符合我们的直观理解。
拓扑排序也可以被看成是广度优先搜索的一种情况：我们先遍历一遍所有节点，把入度为 0的节点（即没有前置课程要求）放在队列中。在每次从队列中获得节点时，我们将该节点放在目前排序的末尾，并且把它指向的课程的入度各减 1；如果在这个过程中有课程的所有前置必修课都已修完（即入度为0），我们把这个节点加入队列中。当队列的节点都被处理完时，说明所有的节点都已排好序，或因图中存在循环而无法上完所有课程。

vector<int>findOrder(int numCourses,vector<vector<int>>&prerequisites)
{
    vector<vector<int>>graph(numCourses,vector<int>());
    vector<int>indegree(numCourses,0),res;
    for(const auto & preprequisite:prerequisite)
    {
        graph[prerequisite[1]].push_back(prerequisites[0];
        ++indegree[prerequisite[0]];
    }
    queue<int>q;
    for(int i=0;i<indegree.size();++i)
    {
        if(!indegree[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        res.push_back(u);
        q.pop();
        for(auto v:graph[u]){
            --indegree[v];
            if(!indegree[v]){
                q.push(v);
            }
        }
    }
    for(int i=0;i<indegree.size();++i)
    {
        if(indegree[i]){
            return vector<int>();
        }
    }
    return res;
}