矩阵图的四个算法 - DFS、BFS、Dijkstra、Topological Sort

之前总结的图的基本算法有DFS、BFS、Dijkstra、Topological Sort、关键路径、Prim和Kruskal。但PAT甲级中目前只使用到了如下四个算法，而且一般都是用矩阵图来实现，所以把这四个算法用矩阵图实现一下总结成一篇文章。

#include <bits/stdc++.h>
#define INF 1010 

using namespace std;
class Dijkstra_Record
{
public: 
    int length;       //最小边权值
    int pre;          //前继，用于输出路径
    int num;          //最短路径的个数
    int weight;       //最大点权值
    Dijkstra_Record()
    {
        pre = 0; length = INF; 
        num = 0; weight = 0; 
    }
};
typedef class MGraph
{
public:
    int **matrix;
    int vertexNum;
    MGraph(){ matrix = NULL; vertexNum = 0; }
} *G;
void DFS(MGraph *g, int start, bool *visits)
{
    visits[start] = true;
    cout << start << " ";
    for(int i = 0; i < g->vertexNum; i++)
        if(!visits[i] && g->matrix[start][i] != 0
            && g->matrix[start][i] != INF) 
        DFS(g, i, visits);
}
void BFS(MGraph *g, int start, bool *visits)
{
    int arr[INF];
    int countt = 0, countf = 0;
    if(g && g->matrix)
        arr[countt++] = start;
    visits[start] = true;
    while(countt > countf)
    {
        int out = arr[countf++];
        cout << out << " ";
        for(int i = 0; i < g->vertexNum; i++)
            if(!visits[i] && g->matrix[out][i] != 0
                    && g->matrix[out][i] != INF)
            {
                arr[countt++] = i;
                visits[i] = true; 
            } 
    }
}
void creatGraph(MGraph *g)
{
    int edgeNum, begin, end;
    cin >> edgeNum;
    for(int i = 0; i < edgeNum; i++)
    {
        cin >> begin >> end;
        cin >> g->matrix[begin][end];
    }
}
int Dijkstra(MGraph *g, int s, int v, bool *visits, int *weight)
{
    int n = g->vertexNum, i, j;
    Dijkstra_Record *dr = new Dijkstra_Record[n];
    dr[s].length = 0;       //起点初始化为 0
    dr[s].num = 1;          //起点路径条数为 1 
    dr[s].weight = weight[s];
    for(i = 0; i < n; i++)
    {
        int cur = -1, min = INF;
        for(j = 0; j < n; j++)
            if(!visits[j] && dr[j].length < min)
                min = dr[cur = j].length;
        if(cur == -1)
            return -1;      //无法到达 
        visits[cur] = true;
        for(j = 0; j < n; j++){
            int newLen = g->matrix[cur][j] + dr[cur].length;
            if(!visits[j] && g->matrix[cur][j] != INF)
            {
                if(newLen < dr[j].length)
                {
                    dr[j].length = newLen;
                    dr[j].pre = cur;
                    dr[j].num = dr[cur].num;
                    dr[j].weight = dr[cur].weight + weight[j];
                }else if(newLen == dr[j].length){
                    dr[j].num = dr[cur].num + dr[j].num;
                    if(dr[j].weight < dr[cur].weight + weight[j]){
                         dr[j].pre = cur;
                         dr[j].weight = dr[cur].weight + weight[j];
                    }
                }
            }
            if(cur == v)
                return dr[v].length;
        }
    }
}
bool topSort(MGraph *g, int *topOrder)
{
    int  n = g->vertexNum, countt = 0, i, j, cnt = 0;
    int *arr = new int[n], *inDegree = new int[n];
    memset(inDegree, 0, n*sizeof(int));
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)      //O(v方)
            if(g->matrix[i][j] != INF && g->matrix[i][j] != 0)
                inDegree[j]++;
    for(i = 0; i < n; i++)
        if(inDegree[i] == 0)
            arr[countt++] = i;
    while(countt != 0){
        int out = arr[--countt];
        topOrder[cnt++] = out;
        for(i = 0; i < n; i++)
            if(g->matrix[out][i] != INF && g->matrix[out][i] != 0
                     && --inDegree[i] == 0)
                arr[countt++] = i;
    }
    if(cnt != n)
        return false;       //图有环 
    return true;
}

int main()
{
    int n, i, j;
    MGraph *g = new MGraph();
    bool visits[INF];
    cin >> n;   //定义一个 n，不然总是写 g->vertexNum浪费时间。 

    //初始化图 ：主对角线初始化为0，其余初始化为MY_INFINOTY 
    g->vertexNum = n;
    g->matrix = new int*[n];
    for(i = 0; i < n; i++)
    {
        g->matrix[i] = new int[n];
        fill(g->matrix[i], g->matrix[i]+n, INF);
        g->matrix[i][i] = 0;
    }

    //创建图
    creatGraph(g);
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
            printf("%04d ", g->matrix[i][j]);
        cout << endl;
    }

    //DFS周游
    memset(visits, 0, n*sizeof(int));
    for(i = 0; i < g->vertexNum; i++)
        if(!visits[i])
            DFS(g, i, visits);
    cout<<endl;

    //BFS周游 
    memset(visits, 0, n*sizeof(int));
    for(i = 0; i < g->vertexNum; i++)
        if(!visits[i]) 
            BFS(g, i, visits);
    cout << endl;

    //Dijkstra 
    memset(visits, 0, n*sizeof(int));
    int *weight = new int[n];
    for(i = 0; i < n; i++)
        weight[i] = i;
    cout << Dijkstra(g, 0, 4, visits, weight) << endl;

    //拓扑排序
    int *topOrder = new int[n];
    if(topSort(g, topOrder)) 
        for(i = 0; i < n; i++)
            cout << topOrder[i] << "  ";
    else
        cout << "图有环";
    cout << endl; 
    return 0;
}

/*
    input:
        5 6 
        0 1 1
        0 2 2
        0 3 1
        1 2 1
        2 4 1
        3 4 1
    graph:
        0000  0001  0002  0001  1010
        1010  0000  0001  1010  1010
        1010  1010  0000  1010  0001
        1010  1010  1010  0000  0001
        1010  1010  1010  1010  0000
    DFS from 0 : 0 1 2 4 3
    BFS from 0 : 0 1 2 3 4

    input：
        5 8
        0 1 10
        0 3 30
        0 4 100
        1 2 50
        2 4 10
        3 1 10
        3 2 20
        3 4 60 
    graph:
        0000 0010 1010 0030 0100
        1010 0000 0050 1010 1010
        1010 1010 0000 1010 0010
        1010 0010 0020 0000 0060
        1010 1010 1010 1010 0000
*/