图的所有算法

（一）最小生成树

最小生成树的特点就是包含所有点，边的数目=点的数目-1。

Prime算法就是先随机选取一点放到点集V，从剩下的点（点集U）中选择一条到点集V的最短的线，把线的另一头从点集U弹出，进入点集V。

然后不停重复上述。该算法是从顶点开始扩展最小生成树不同。

Prime算法的时间复杂度是O(|V|^2)，不依赖于|E|。适用于求解边稠密的图的最小生成树。

Kruskal算法就是对所有的线进行排序，然后每次都打算加入最短的，检查是不是会成环，如果会成环就不放进去；如果不会成环就放进去。

该算法是一种按权值递增次序选择合适的边来构造最小生成树的方法。

检查环用的是并查集。判断加入的线的两个顶点是不是在同一棵树里面。找到顶点A的根rootA，找到顶点B的根rootB。

如果rootA=rootB就在同一棵树上。

通常采用堆来存放边的集合，因此每次选择最小权值的边只需要O(log|E|)的时间。

此外，由于生成树的所有边可以视为一个等价类，因此可以采用并查集的数据结构描述T。

 （二）带权有向图的最短路径

单源最短路径使用Dijkstra，求途中某一顶点到其他所有顶点的最短路径0。

class Solution {
public:
    //依据就是利用层次遍历，当遍历到第三层的时候计算如下：
    //第三层的distFromStart = 第二层节点的distFromStart + 第二层和第三层之间的权重。
    //队列中第一个放进去的就是开始节点k
    struct State
    {
        //图节点的ID
        int id;
        int distFromStart;//从start节点到当前节点的距离
        State(int id, int distFromStart)
        {
            this->id = id;
            this->distFromStart = distFromStart;
        }  
    };=
    
    int networkDelayTime(vectorint>>& times, int n, int k) {
        //从这个可以指向哪些？
        vectorint, int>>> edge(n);//邻接表的方式进行表示
        //vector vis(n, false);
        for(auto & time: times)
        {
            edge[time[0]-1].push_back(make_pair(time[1]-1, time[2]));
        }
        vector<int> distTo(n, INT_MAX);//表示起点k到达节点i的最短路径权重
        distTo[k-1] = 0;
        //小顶堆的优先级队列,distance比较小的放前面
        //priority_queue, compare> que;
        queue que;
        //从节点k开始进行bfs层次遍历
        que.push(State(k-1, 0));
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                //State curNode = que.top();
                State curNode = que.front();
                que.pop();
                int curNodeID = curNode.id;
                int curDistFromStart = curNode.distFromStart;
                if(curDistFromStart > distTo[curNodeID]) continue;
                //将curNode的相邻节点装入队列当中
                for(auto& neighbor: edge[curNodeID])
                {
                    int nextNodeID = neighbor.first;
                    int nextNodeDistFromStart = distTo[curNodeID] + neighbor.second;
                    if(nextNodeDistFromStart < distTo[nextNodeID])
                    {
                        distTo[nextNodeID] = nextNodeDistFromStart;
                        que.push(State(nextNodeID, nextNodeDistFromStart)); 
                    }
                }
            }
        }
        //找到最长的那条路径，就是最短时间
        int result = 0;
        for(int i = 0; i < n; i++)
        {
            if(distTo[i] == INT_MAX)
            {
                return -1;
            }
            result = max(result, distTo[i]);
        }
        return result;
    }
};

使用一个State类来记录当前节点的id和从start节点到该节点的路径。本质就是层次遍历一层一层求。

每一个节点都使用edge记录它可以出度到哪里和那个权值（pair），然后一个节点先出度到一层计算所有distFromstart，然后再算第二层的。

Floyd-Warshall求解每对顶点之间的路径。

（三）拓扑排序

有向无环图叫做DAG图。构成AOV网（顶点表示活动的网）。还有AOE（用边表示活动的网络）

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，叫做该图的一个拓扑排序。

（1）每个顶点出现且只出现一次。

（2）如果顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。（无环）

就是课程表的那道题目，可以使用DFS和BFS。

BFS的思路就是让每一个节点的入度都变成0，使用队列统计节点的数目等于总数目就符合要求。

//使用广度优先搜索的方式，入度0的进入队列，看进入队列的有没有达到数目
    vectorint>> edges;//统计a点指向b点，那么要完成b的前提就是完成a
    vector<int> indeg;
    bool result = true;
    bool canFinish(int numCourses, vectorint>>& prerequisites) {
        //首先要统计每个的入度，0的前提是1，那就是1推出0的，0的入度就是1
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for(auto temp: prerequisites)
        {
            edges[temp[1]].push_back(temp[0]);
            indeg[temp[0]]++;
        }
        int count = 0;
        queue<int> que;
        for(int i = 0; i < numCourses; i++)
        {
            if(indeg[i] == 0) 
            {
                que.push(i); 
            }
        }
        while(!que.empty())
        {
            int val = que.front(); que.pop();
            count++;
            for(auto temp2: edges[val])
            {
                indeg[temp2]--;
                //看看这个的入度
                if(indeg[temp2] == 0) que.push(temp2);
            }
        }
        return count == numCourses;
    }

DFS的思路就是像二叉树一样遍历邻边，但是需要一个visited来判断是不是遍历过。然后采用回溯的思想，使用OnPath数组记录这条路遍历过，如果形成环就会再次检测到OnPath。

class Solution {
public:
    vectorint>> edges;
    vector<bool> onPath;//记录一次遍历递归经过的节点
    vector<bool> visited;//记录遍历过的节点，防止走回头路
    bool result = true;//如果有环就变成false
    void dfs(int i)
    {
        if(onPath[i]) result = false;//出现环了
        if(visited[i] || !result) return;
        //开始遍历
        visited[i] = true;
        onPath[i] = true;
        for(auto edge: edges[i])
        {
            dfs(edge);
        }
        onPath[i] = false;
    }

    bool canFinish(int numCourses, vectorint>>& prerequisites) {
        //[0,1]，1指向0的
        edges.resize(numCourses);
        onPath.resize(numCourses);
        visited.resize(numCourses);
        for(auto temp: prerequisites)
        {
            edges[temp[1]].push_back(temp[0]);
        }
        for(int i = 0; i < numCourses; i++)
        {
            if(result) dfs(i);
            else break;
        }
        return result;
    }
};

每个DAG图都有一个或多个拓扑排序序列。

（四）并查集。

就是写一个UF的类，然后连接两个点的函数，以及判断两个点是否相连的函数。

class UF
{
public:
    UF(int n)
    {
        this->count = n;
        parent.resize(n);
        ssize.resize(n);
        for(int i = 0; i < n; i++)
        {
            parent[i] = i;
            ssize[i] = 1;
        }
    }
    //返回节点x的根节点，进行路径压缩
    int find(int x)
    {
        while(parent[x] != x)
        {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    //将p和q进行连通
    void uunion(int p, int q)
    {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ) return;
        //小树在下面
        if(ssize[rootP] > ssize[rootQ])
        {
            parent[rootQ] = rootP;
            ssize[rootP] += ssize[rootQ];
        }
        else
        {
            parent[rootP] = rootQ;
            ssize[rootQ] += ssize[rootP];
        }
        count--;
    }
    //判断p和q是否相互连通
    bool connected(int p, int q)
    {
        int rootP = find(p);
        int rootQ = find(q);
        return (rootP == rootQ);
    }
    
private:
    int count; //记录连通分量的个数
    vector<int> parent; //存储若干棵树
    vector<int> ssize; //记录树的重量
};