数据结构入门——图的相关算法（一）

写在前面

距离19年研究生考试越来越近了，专业课的算法设计题考数据结构中的图的部分。感觉这部分比较困难，我大学没参加过ACM，之前也从来没写过图的代码，照着王道的书花了一天撸了四百行代码，着实费劲。函数名、变量名甚至代码结构都和王道的相关代码相似。包括BFS和DFS, 分别用邻接矩阵和邻接表实现了，还有SPFA, Floyd, Dijkstra，这些算法都用题目验证过，保证正确性。在此附上完整代码，可以直接copy运行。由于王道书上已经写了不少注释了，故这些代码的注释写得很少，看不懂的地方请在下方评论，我尽可能回复。
spfa算法是受博主 xunalove 转发的这篇文章 最快最好用的——spfa算法 的启发写出来的。

#include <bits/stdc++.h>

#define MaxNum 200

using namespace std;

typedef int VertexType;
typedef int EdgeType;

//顺序栈
typedef struct{
    int data[MaxNum];
    int top;
}SqStack;

//顺序队列
typedef struct{
    int data[MaxNum];
    int rear,head;
}SqQueue;

//图的邻接矩阵表示法
typedef struct{
    VertexType vertex[MaxNum];
    EdgeType edge[MaxNum][MaxNum];
    int vexNum,arcNum;
}MGraph;

//图的邻接表表示法
typedef struct ArcNode{
    int adjvex;
    struct ArcNode * next;
}ArcNode;

typedef struct VNode{
    VertexType vex;
    ArcNode * first;
}VNode,AdjList[MaxNum];

typedef struct{
    AdjList verticies;
    int vexNum,arcNum;
}ALGraph;

//输入数据并存储到邻接矩阵中
void MGReadData(MGraph &G);
//输入数据并存储到邻接表中
void ALGReadData(ALGraph &G);

//采用邻接矩阵存储的广度优先搜索
void MGBFSTraverse(MGraph G);
void MGBFS(MGraph G,int u);
//采用邻接矩阵存储的深度优先搜索
void MGDFSTraverse(MGraph G);
void MGDFS(MGraph G,int u);
//采用邻接表存储的广度优先搜索
void ALGBFSTraverse(ALGraph G);
void ALGBFS(ALGraph G,int u);
//采用邻接表存储的深度优先搜索
void ALGDFSTraverse(ALGraph G);
void ALGDFS(ALGraph G,int u);
void visit(int v);

//从u开始执行迪杰斯特拉求最短路
void Dijkstra(MGraph G,int u,int path[],int dist[]);
//打印最短路
void printPath(int v);
//从u开始执行SPFA求最短路
void SPFA(MGraph G,int u,int paht[],int dist[]);
//弗洛伊德算法求任意两点最短路
void Floyd(MGraph G);

int MGFirstNeighbor(MGraph G,int k);
int MGNextNeighbor(MGraph G,int k,int n);
int ALGNextNeighbor(ALGraph G,int k,int w);
int ALGFirstNeighbor(ALGraph G,int k);

int path[MaxNum];
int dist[MaxNum];
int u,v;    //u是起点，v是终点
int visited[MaxNum] = {0};
int mp[MaxNum][MaxNum];

int main(){
    //MGraph G;
    //ALGraph ALG;

    //MGReadData(G);
    //ALGReadData(ALG);

    //MGBFSTraverse(G);
    //MGDFSTraverse(G);
    //ALGBFSTraverse(ALG);
    //ALGBFSTraverse(ALG);

    //printf("请输入起点和终点，以空格隔开\n");
    //scanf("%d%d",&u,&v);
    //Dijkstra(G,u,path,dist);
    //SPFA(G,u,path,dist);
    //printPath(v);
    //Floyd(G);
    //printf("从1到3的最短路径距离为：%d",mp[1][3]);

    return 0;
}

void MGReadData(MGraph &G){
    int i,j,k;
    scanf("%d%d",&G.vexNum,&G.arcNum);
    for(i = 1;i <= G.vexNum;i++){
        for(j = 1;j <= G.vexNum;j++){
            G.edge[i][j] = 1e9;
        }
    }

    for(k = 1;k <= G.arcNum;k++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        G.edge[x][y] = z;

        //对于无向图，邻接矩阵是个对称矩阵，下边的一行代码应打开
        //G.edge[y][x] = z;
    }
}

void ALGReadData(ALGraph &G){
    int i,j;
    ArcNode * s,* p;
    scanf("%d%d",&G.vexNum,&G.arcNum);
    //初始化顶点表
    for(i = 1;i <= G.vexNum;i++){
        G.verticies[i].vex = i;
        G.verticies[i].first = NULL;
    }
    //初始化边表
    for(j = 1;j <= G.arcNum;j++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(G.verticies[x].first == NULL){
            s = (ArcNode * )malloc(sizeof(ArcNode));
            s->adjvex = y;
            s->next = NULL;
            G.verticies[x].first = s;
        }else{
            p = G.verticies[x].first;
            while(p->next){ //找到链尾
                p = p->next;
            }
            s = (ArcNode * )malloc(sizeof(ArcNode));
            s->adjvex = y;
            s->next = NULL;
            p->next = s;
        }
    }
}

void MGBFSTraverse(MGraph G){
    int i;

    for(i = 1;i <= G.vexNum;i++){
        if(!visited[i]){
            MGBFS(G,i);
        }
    }
}

void MGBFS(MGraph G,int u){
    int w;
    SqQueue que;
    int rear = 0,head = 0;

    visit(u);
    visited[u] = 1;
    que.data[rear++] = u;

    while(head < rear){
        int k = que.data[head++];
        for(w = MGFirstNeighbor(G,k);w >= 0;w = MGNextNeighbor(G,k,w)){
            if(!visited[w]){
                visit(w);
                visited[w] = 1;
                que.data[rear++] = w;
            }
        }
    }
}

void MGDFSTraverse(MGraph G){
    int i;
    for(i = 1;i <= G.vexNum;i++){
        if(!visited[i]){
            MGDFS(G,i);
        }
    }
}

void MGDFS(MGraph G,int u){
    int w;
    visit(u);
    visited[u] = 1;
    for(w = MGFirstNeighbor(G,u);w >= 0;w = MGNextNeighbor(G,u,w)){
        if(!visited[w]){
            MGDFS(G,w);
        }
    }
}

int MGFirstNeighbor(MGraph G,int k){
    int i;
    for(i = 1;i <= G.vexNum;i++){
        if(G.edge[k][i] < 1e9){
            return i;
        }
    }

    return -1;
}

int MGNextNeighbor(MGraph G,int k,int n){
    int i;
    for(i = n+1;i <= G.vexNum;i++){
        if(G.edge[k][i] < 1e9){
            return i;
        }
    }

    return -1;
}

void visit(int v){
    printf("%d ",v);
}

void ALGBFSTraverse(ALGraph G){
    int i;
    for(i = 1;i <= G.vexNum;i++){
        if(!visited[i]){
            ALGBFS(G,i);
        }
    }
}

void ALGBFS(ALGraph G,int u){
    SqQueue que;
    int rear = 0,head = 0;
    int w;

    visit(u);
    visited[u] = 1;
    que.data[rear++] = u;
    while(head < rear){
        int k = que.data[head++];
        for(w = ALGFirstNeighbor(G,k);w >= 0;w = ALGNextNeighbor(G,k,w)){
            if(!visited[w]){
                visit(w);
                visited[w] = 1;
                que.data[rear++] = w;
            }
        }
    }
}

void ALGDFSTraverse(ALGraph G){
    int i;
    for(i = 1;i <= G.vexNum;i++){
        if(!visited[i]){
            ALGDFS(G,i);
        }
    }
}

void ALGDFS(ALGraph G,int u){
    int w;

    visit(u);
    visited[u] = 1;
    for(w = ALGFirstNeighbor(G,u);w >= 0;w = ALGNextNeighbor(G,u,w)){
        if(!visited[w]){
            ALGDFS(G,w);
        }
    }
}

int ALGFirstNeighbor(ALGraph G,int k){

    if(G.verticies[k].first != NULL){
        return G.verticies[k].first->adjvex;
    }

    return -1;
}

int ALGNextNeighbor(ALGraph G,int k,int w){
    ArcNode * p;
    if(k != -1){
        p = G.verticies[k].first;
        while(p != NULL && p->adjvex != w){
            p = p->next;
        }

        if(p != NULL && p->next != NULL){
            return p->next->adjvex;
        }

    }

    return -1;

}

void Dijkstra(MGraph G,int u,int path[],int dist[]){
    int i,j,k,mini,t;
    int s[MaxNum];

    for(i = 1;i <= G.vexNum;i++){
        s[i] = 0;
        dist[i] = G.edge[u][i];
        if(dist[i] < 1e9){
            path[i] = u;
        }else{
            path[i] = -1;
        }
    }
    s[u] = 1;
    path[u] = -1;

    for(i = 1;i <= G.vexNum;i++){
        mini = 1e9;
        for(j = 1;j <= G.vexNum;j++){
            if(s[j] == 0 && dist[j] < mini){
                t = j;
                mini = dist[j];
            }
        }

        s[t] = 1;
        for(k = 1;k <= G.vexNum;k++){
            if(s[k] == 0 && dist[t] + G.edge[t][k] < dist[k]){
                dist[k] = dist[t] + G.edge[t][k];
                path[k] = t;
            }
        }
    }
}

void printPath(int v){
    if(path[v] != -1){
        printPath(path[v]);
    }
    printf("%d ",v);
}

//SPFA单源最短路，权值可为负
void SPFA(MGraph G,int u,int paht[],int dist[]){
    int i;
    SqQueue que;
    int rear = 0,head = 0;

    for(i = 1;i <= G.vexNum;i++){
        dist[i] = 1e9;
        path[i] = -1;
    }

    dist[u] = 0;
    visited[u] = 1;
    que.data[rear++] = u;

    while(head < rear){
        int k = que.data[head++];
        visited[k] = 0; //释放对k的标记，可以重新入队
        for(int w = MGFirstNeighbor(G,k);w >= 0;w = MGNextNeighbor(G,k,w)){
            if(dist[k] + G.edge[k][w] < dist[w]){   //原理：三角形两边之和大于第三边
                dist[w] = dist[k] + G.edge[k][w];
                path[w] = k;
            }
            if(!visited[w]){
                que.data[rear++] = w;
                visited[w] = 1;
            }
        }
    }
}

//Floyd求全局最短路
void Floyd(MGraph G){
    int i,j,k;
    for(i = 1;i <= G.vexNum;i++){
        for(j = 1;j <= G.vexNum;j++){
            if(i == j)
                mp[i][j] = 0;
            else mp[i][j] = G.edge[i][j];
        }
    }

    for(k = 1;k <= G.vexNum;k++){
        for(i = 1;i <= G.vexNum;i++){
            for(j = 1;j <= G.vexNum;j++){
                mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);
            }
        }
    }
}

下面是各个算法的输入样例，顶点编号都从1开始。

//邻接矩阵的BFS输入样例（2019王道200页第8题图）
//第一行两个数字，分别表示结点数N和边数M
//下面M行表示结点间的连通性，每行由3个数组成
//1 2 1表示从顶点1到顶点2之间有权值为1的路径
6 8
1 2 1
1 4 1
2 5 1
3 5 1
3 6 1
4 2 1
5 4 1
6 6 1
输出结果：1 2 4 5 3 6

//邻接表的BFS输入样例（2019王道200页第8题图）
//第一行的两个数字，分别表示结点数N和边数M
//下面M行表示结点间的连通性
//PS：此处的邻接表的结构体无法存储权值信息
6 8
1 2
1 4
2 5
3 5
3 6
4 2
5 4
6 6
输出结果：1 2 4 5 3 6


//邻接矩阵的DFS输入样例（2019王道200页第8题图）
//第一行两个数字，分别表示结点数N和边数M
//下面M行表示结点间的连通性
6 8
1 2 1
1 4 1
2 5 1
3 5 1
3 6 1
4 2 1
5 4 1
6 6 1
输出结果：1 2 5 4 3 6

//邻接表的DFS输入样例（2019王道200页第8题图）
//第一行两个数字，分别表示结点数N和边数M
//下面M行表示结点间的连通性
6 8
1 2
1 4
2 5
3 5
3 6
4 2
5 4
6 6
输出结果：1 2 5 4 3 6

求最短路的算法，Dijkstra, spfa, floyd用的都是邻接矩阵，方便处理

//Dijkstra、spfa和floyd的输入样例（2019王道210页图5-22）
//第一行两个数字，分别表示结点数N和边数M
//接下来有M行，每行三个数字，分别表示第一个结点，第二个结点，权值
//例如 1 2 10表示结点1到结点2之间的权值是10
//若是无权图，将权值全部赋值为1即可
5 10
1 2 10
1 5 5
2 3 1
2 5 2
3 4 4
4 1 7
4 3 6
5 2 3
5 3 9
5 4 2

请输入起点和终点，以空格隔开
1 3
输出结果：1 5 2 3