数据结构-图

图

图的存储

图的顺序存储-邻接矩阵法-数据结构

1
2
3
4
5
6
7
8
9
10
//顺序存储，将所有的点根据矩阵按序存入
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];   //顶点表
    //A[i][j]表示边，为0则没有联通，为1则联通，其他数则为其权值
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    //边表
    int vexnum,arcnum;  //记录图的当前顶点数与弧数
}MGragh;

图的链式存储-邻接表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//邻接表法类似树的孩子兄弟表示法，有顶点表，和一串与该顶点相连的链表
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef struct ArcNode{ //边表结点
    int adjvex; //该弧指向的顶点位置
    struct ArcNode *next;   //指向下一条弧的指针
}ArcNode;
typedef struct VNode{   //邻接表
    VertexType data;    //顶点信息
    ArcNode *first; //指向第一条依附于该顶点的边的指针
}VNode,AdjList[MaxVertexNum];   //顶点表与顶点结点
typedef struct{
    AdjList vertices;   //邻接表，顶点表
    int vexnum,arcnum;  //记录图的当前顶点数与弧数
}ALGraph;   //ALGraph是以邻接表存储的图类型

图的链式存储-十字链表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用于表示有向图，十字链表法是邻接矩阵法的拓展，相当于增加了边的前后驱，能更快的遍历相同入度或相同出度的边
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef string InfoType;    //边信息的数据类型
typedef struct ArcNode{ //边表结点
    int tailvex,headvex;    //该弧的头尾结点
    ArcNode *hlink,*tlink;  //分别指向弧头相同和弧尾相同的结点
    InfoType info;  //边相关信息
}ArcNode;
typedef struct VNode{   //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstin,*firstout; //指向第一条入弧和出弧
}VNode,GLlist[MaxVertexNum];
typedef struct{
    //VNode GLlist[MaxVertexNum];  //邻接表
    GLlist GLlist;  //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}GLGraph;   //GLGraph是以邻接表存储的图类型

图的链式存储-邻接多重表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用于表示无向图，与有向图的十字链表法类似
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef string InfoType;    //边信息的数据类型
typedef struct ArcNode{ //边表结点
    bool mark;  //访问标记
    int ivex,jvex;  //分别指向该弧的两个结点
    ArcNode *ilink,*jlink;  //分别指向两个顶点的下一条边
    InfoType info;  //相关边的信息
}ArcNode;
typedef struct VNode{   //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstedge; //指向第一条依附该顶点的边
}VNode,Adjmulist[MaxVertexNum];
typedef struct{
    Adjmulist adjmulist;    //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}AMLGraph;

判断顶点存在

图-邻接矩阵法-判断顶点存在

1
2
3
4
5
6
7
8
9
10
//由于内部方法不同存储结构大同小异，以邻接矩阵法为例
//查找顶点在图G中是否存在,存在则返回下标，不存在则返回-1
int findVertex(MGragh G,char x){
    for(int i=0;i<G.vexnum;i++){
        if(G.Vex[i]==x){
            return i;
        }
    }
    return -1;
}

判断边存在

图-邻接矩阵法-判断边存在

1
2
3
4
5
6
7
8
9
10
11
12
13
//判断是否存在边<x,y>
bool Adjacent(MGragh G,char x,char y){
    if(findVertex(G,x) != -1&&findVertex(G,y) != -1){
        if(G.Edge[findVertex(G,x)][findVertex(G,y)] == 0){
            return false;
        }else{
            return true;
        }
    }else{
        printf("其中顶点不存在");
        return false;
    }
}

寻找相邻顶点

图-邻接矩阵法-寻找相邻顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//列出图G中与结点x相接的边,输出与x相连的另一个顶点
VertexType *Neighbor(MGragh G,char x,int type){
    VertexType Edges[G.vexnum];
    for(int i=0;i<G.vexnum;i++){
        Edges[i] = '0';
    }   //输出数组赋初值
    if(findVertex(G, x) != -1){
        int index = 0;
        switch (type) {
            case 0: //输出出度为x的边
                for(int i=0;i<G.vexnum;i++){
                    if(G.Edge[findVertex(G, x)][i] != 0){
                        Edges[index] = i;
                        index++;
                    }
                }
                break;
            case 1: //输出入度为x的边
                for(int i=0;i<G.vexnum;i++){
                    if(G.Edge[i][findVertex(G, x)] != 0){
                        Edges[index] = i;
                        index++;
                    }
                }
                break;
            case 2: //输出出度或入度为x的边
                for(int i=0;i<G.vexnum;i++){
                    if(G.Edge[i][findVertex(G, x)] != 0){
                        Edges[index] = i;
                        index++;
                    }
                }
                for(int i=0;i<G.vexnum;i++){
                    if(G.Edge[findVertex(G, x)][i] != 0){
                        Edges[index] = i;
                        index++;
                    }
                }
                break;
            default:
                break;
        }
    }else{
        printf("顶点不存在");
    }
    return Edges;
}

插入顶点

图-邻接矩阵法-插入顶点

1
2
3
4
5
6
7
8
9
//在图G中插入顶点x
void InsertVertex(MGragh G,char x){
    if(G.vexnum<MaxVertexNum){
        G.Vex[G.vexnum] = 'x';
        G.vexnum++;
    }else{
        printf("超出最大结点数限制，插入失败");
    }
}

删除顶点

图-邻接矩阵法-删除顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//在图G中删除顶点x
void DeleteVertex(MGragh G,char x){
    if(findVertex(G, x) == -1){
        printf("顶点表中没有该顶点，插入失败");
    }else{
        //删除原顶点相关数据，把最后一个顶点的相关数据填补到删除的空缺处
        //替换顶点表
        G.Vex[findVertex(G, x)] = G.Vex[G.vexnum-1];
        G.Vex[G.vexnum-1] = '0';  //设为初值
        //替换边表
        for(int i=0;i<G.vexnum;i++){
            if(G.Edge[i][findVertex(G, x)]){    //若该边存在，则边数-1
                G.arcnum--;
            }
            G.Edge[i][findVertex(G, x)] = G.Edge[i][G.vexnum-1];
            G.Edge[i][G.vexnum-1] = 0;
        }
        for(int i=0;i<G.vexnum;i++){
            if(G.Edge[findVertex(G, x)][i]){    //若该边存在，则边数-1
                G.arcnum--;
            }
            G.Edge[findVertex(G, x)][i] = G.Edge[G.vexnum-1][i];
            G.Edge[G.vexnum-1][i] = 0;
        }
        G.vexnum--;
    }
}

添加边

图-邻接矩阵法-添加边

1
2
3
4
5
6
7
8
9
//若边<x,y>不存在，则在图G中添加这条边，weight为权值
void AddEdge(MGragh G,char x,char y,int weight){
    if(!Adjacent(G, x, y)&&findVertex(G, x) != -1&&findVertex(G, y) != -1){ //边不存在，并且顶点都存在
        G.arcnum ++;
        G.Edge[findVertex(G, x)][findVertex(G, y)] = weight;
    }else{
        printf("添加边失败");
    }
}

删除边

图-邻接矩阵法-删除边

1
2
3
4
5
6
7
8
9
//若边<x,y>存在，则在图G中删除这条边
void RemoveEdge(MGragh G,char x,char y){
    if(Adjacent(G, x, y)){ //边存在
        G.arcnum --;
        G.Edge[findVertex(G, x)][findVertex(G, y)] = 0;
    }else{
        printf("删除边失败");
    }
}

获得权值

图-邻接矩阵法-获得权值

1
2
3
4
5
6
7
8
9
10
//获取图G中边<x,y>对应的权值
EdgeType GetEdgeValue(MGragh G,char x,char y){
    EdgeType output = -1;
    if(Adjacent(G, x, y)){ //边存在
        output = G.Edge[findVertex(G, x)][findVertex(G, y)];
    }else{
        printf("查询边失败");
    }
    return output;
}

设置权值

图-邻接矩阵法-设置权值

1
2
3
4
5
6
7
8
//设置图G中边<x,y>对应的权值为weight
void SetEdgeValue(MGragh G,char x,char y,int weight){
    if(Adjacent(G, x, y)){
        G.Edge[findVertex(G, x)][findVertex(G, y)] = weight;
    }else{
        AddEdge(G, x, y, weight);   //边不存在，添加这条边
    }
}

寻找第一个邻接顶点

图-邻接表法-寻找第一个邻接顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//邻接矩阵法中，求图G中的第一个邻接点，若有则返回顶点号，没有或失败则返回-1
int FirstNeighbor(ALGraph G,char x){
    int indexX = -1;
    int output = -1;
    //判断顶点x存在
    for(int i=0;i<G.vexnum;i++){
        if(G.vertices[i].data==x){
            indexX = i;
            break;
        }
    }
    //判断是否存在依附于x的边
    if(indexX != -1 &&G.vertices[indexX].first){
        output = G.vertices[indexX].first->adjvex;
    }
    return output;
}

寻找下一个邻接顶点

图-邻接表法-寻找下一个邻接顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//邻接矩阵法中，求图G中，y是x的邻接点，求y的下一个邻接点，若有则返回顶点号，没有或失败则返回-1
int NextNeighbor(ALGraph G,char x,char y){
    int indexX = -1;
    int output = -1;
    //判断顶点x存在
    for(int i=0;i<G.vexnum;i++){
        if(G.vertices[i].data==x){
            indexX = i;
            break;
        }
    }
    //判断是否存在依附于x的边
    ArcNode *temp;
    if(indexX != -1 &&G.vertices[indexX].first){
        temp = G.vertices[indexX].first;
        while(temp){
            if(G.vertices[temp->adjvex].data == y && temp->next){
                output = temp->next->adjvex;
                break;
            }
            temp = temp->next;
        }
    }
    return output;
}

图的遍历

图的遍历-邻接矩阵法-深度优先遍历-递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool visted[MaxVertexNum];  //访问标记数组
void DFS(MGragh G,int index){
    visted[index] = true;   //开始顶点标记访问
    printf("访问结点:%c",G.Vex[index]); //访问结点，也可作其他运算
    for(int i=0;i<G.vexnum;i++){
        if(G.Edge[index][i]!=0&&!visted[i]){ //若路径存在，且顶点未访问
            DFS(G,i);    //递归
        }
    }
}
void DFSTraverse(MGragh G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            DFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的遍历-邻接矩阵法-深度优先遍历-非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool visted[MaxVertexNum];  //访问标记数组
void DFS(MGragh G,int index){
    int currentindex = -1;
    SqStack *S = InitStack();
    PushStack(*S, index);
    visted[index] = true;   //开始顶点标记访问
    while(!isStackEmpty(*S)){   //若栈非空，则有未处理完的顶点
        currentindex = PopStack(*S);
        printf("访问结点:%c",G.Vex[index]); //访问结点，也可作其他运算
        for(int i=0;i<G.vexnum;i++){
            if(G.Edge[currentindex][i]!=0&&!visted[i]){ //若路径存在，且顶点未访问
                visted[i] = true;   //开始顶点标记访问
                PushStack(*S, i);   //当前顶点入栈
            }
        }
    }
}
void DFSTraverse(MGragh G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            DFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的遍历-邻接表法-深度优先遍历-递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool visted[MaxVertexNum];  //访问标记数组
void DFS(ALGraph G,int index){
    visted[index] = true;   //开始顶点标记访问
    printf("访问结点:%c",G.vertices[index].data); //访问结点，也可作其他运算
    for(int i=FirstNeighbor(G, G.vertices[index].data);i>=0;i=NextNeighbor(G,G.vertices[index].data,G.vertices[i].data)){
        if(!visted[i]){ //若顶点未访问
            DFS(G,FirstNeighbor(G, G.vertices[i].data));    //递归
        }
    }
}
void DFSTraverse(ALGraph G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            DFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的遍历-邻接表法-深度优先遍历-非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool visted[MaxVertexNum];  //访问标记数组
void DFS(ALGraph G,int index){
    int currentVex = index;
    SqStack *S = InitStack();
    PushStack(*S, index);
    visted[index] = true;   //开始顶点标记访问
    while(!isStackEmpty(*S)){
        currentVex = PopStack(*S);
        printf("访问结点:%c",G.vertices[index].data); //访问结点，也可作其他运算
        for(int i=FirstNeighbor(G, G.vertices[currentVex].data);i>=0;i=NextNeighbor(G,G.vertices[currentVex].data,G.vertices[i].data)){
            if(!visted[i]){ //若顶点未访问
                PushStack(*S, i);    //递归
                visted[i] = true;   //以免再次入栈
            }
        }
    }
}
void DFSTraverse(ALGraph G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            DFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的遍历

图的遍历-邻接矩阵法-广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool visted[MaxVertexNum];  //访问标记数组
void BFS(MGragh G,int index){
    int currentVex = -1;
    SqQueue *Q = InitQueue();   //初始化辅助队列
    visted[index] = true;   //开始顶点标记访问
    printf("访问结点:%c",G.Vex[index]); //访问结点，也可作其他运算
    EnSqQueue(*Q, index);   //开始顶点入队
    while(!isSqQueueEmpty(*Q)){ //若队列非空，则说明还有顶点未处理
        currentVex = DeSqQueue(*Q); //取出待处理顶点
        for(int i=0;i<G.vexnum;i++){
            if(G.Edge[currentVex][i] != 0&& !visted[i]){    //顶点与当前有连线，且顶点未被访问
                visted[i] = true;   //开始顶点标记访问
                printf("访问结点:%c",G.Vex[i]); //访问结点，也可作其他运算
                EnSqQueue(*Q, i);   //当前顶点入栈，等待寻找其后续
            }
        }
    }
}
void BFSTraverse(MGragh G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            BFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的遍历-邻接表法-广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool visted[MaxVertexNum];  //访问标记数组
void BFS(ALGraph G,int index){
    int currentVex = -1;
    SqQueue *Q = InitQueue();   //初始化辅助队列
    visted[index] = true;   //开始顶点标记访问
    printf("访问结点:%c",G.vertices[index].data); //访问结点，也可作其他运算
    EnSqQueue(*Q, index);   //开始顶点入队
    while(!isSqQueueEmpty(*Q)){ //若队列非空，则说明还有顶点未处理
        currentVex = DeSqQueue(*Q); //取出待处理顶点
        for(int i=FirstNeighbor(G,G.vertices[currentVex].data);i>=0;i=NextNeighbor(G,G.vertices[currentVex].data,G.vertices[i].data)){  //i=-1则没有后续邻接顶点
            if(!visted[i]){    //顶点未被访问
                visted[i] = true;   //开始顶点标记访问
                printf("访问结点:%c",G.vertices[i].data); //访问结点，也可作其他运算
                EnSqQueue(*Q, i);   //当前顶点入栈，等待寻找其后续
            }
        }
    }
}
void BFSTraverse(ALGraph G){
    for(int i=0;i<G.vexnum;i++){
        visted[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visted[i]){ //对每组联通分量单独访问
            BFS(G,i);   //出现一个未访问结点，则访问与之联通的整个分量
        }
    }
}

图的应用

图的应用-深度优先搜索-寻找路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//使用邻接表法为数据结构
//寻找下标indexX与indexY之间的一条路径,只能找到其中一条
int path[MaxVertexNum]; //记录路径
int route = 0;  //路径长度初值为0
bool visted[MaxVertexNum];  //访问标记数组
void InitBFSMinDistance(ALGraph G){  //初始化数据
    for(int i=0;i<G.vexnum;i++){
        path[i] = -1;
        visted[i] = false;
    }
}
void BFSMinDistance(ALGraph G,int indexX,int indexY,int path[],int route){
    path[route] = indexX;  //路径记录当前顶点
    route++;   //路径长度增加
    visted[indexX] = true;  //顶点已访问
    if(indexX == indexY){
        printf("找到路径,长度为%d\n路径为:",route);
        printf("%c",G.vertices[0].data);
        for(int i=1;i<route;i++){
            printf("->%c",G.vertices[i].data);
        }
    }
    for(int i=FirstNeighbor(G, G.vertices[indexX].data);i>=0;i=NextNeighbor(G,G.vertices[indexX].data,G.vertices[i].data)){
        if(!visted[i]){
            BFSMinDistance(G, i, indexY, path, route);  //不同方向的递归有不同的path数组，最后输出正确的结果数组
        }
    }
}

图的应用-最小生成树-普里姆Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//默认图为无向连通图，vex[i][j]=vex[j][i];vex[i][i]=0;
MGragh *MSTPrim(MGragh G){
    bool VexVisted[MaxVertexNum];
    MGragh *H = (MGragh *)malloc(sizeof(MGragh));
    //初始化顶点数和边数
    H->vexnum = 0;
    H->arcnum = 0;
    for(int i=0;i<G.vexnum;i++){
        H->Vex[i] = G.Vex[i];   //顶点赋值
        VexVisted[i] = false; //访问顶点标记初始化
        for(int j=0;j<G.vexnum;j++){
            H->Edge[i][j]=0;  //初始化边
        }
    }
    //假设从Vex[0]顶点开始找
    int min = 9999999;
    int edgeS=0;
    int edgeE=0;
    VexVisted[0] = true;
    //全遍历这种找法有一半是多余的，因为这是一个对称矩阵
    while(H->vexnum<G.vexnum){
        //遍历所有已有的顶点
        for(int i=0;i<G.vexnum;i++){
            if(VexVisted[i]){
                //寻找所有与他们没有连接的顶点最小
                for(int j=0;j<G.vexnum;j++){
                    if(!VexVisted[j]){
                        //找到最小的那条边，记录新的顶点和边
                        if(G.Edge[i][j]<min){
                            min = G.Edge[i][j];
                            edgeS = i;
                            edgeE = j;
                        }
                    }
                }
            }
        }
        //找到一组最小的边与新加的顶点
        VexVisted[edgeE] = true;
        H->Edge[edgeS][edgeE] = min;
        H->arcnum ++;
        H->vexnum ++;
    }
    return H;
}

图的应用-最小生成树-克鲁斯卡尔Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//默认图为无向连通图，vex[i][j]=vex[j][i];vex[i][i]=0;
MGragh *MSTKruskal(MGragh G){
    int connected[MaxVertexNum];    //记录每个顶点当前的连通分量
    MGragh *H = (MGragh *)malloc(sizeof(MGragh));
    //初始化顶点数和边数
    H->vexnum = G.vexnum;
    H->arcnum = 0;
    for(int i=0;i<G.vexnum;i++){
        H->Vex[i] = G.Vex[i];   //顶点赋值
        connected[i] = i; //顶点联通分量初始化
        for(int j=0;j<G.vexnum;j++){
            H->Edge[i][j]=0;  //初始化边
        }
    }
    int min = 9999999;
    int edgeS=0;
    int edgeE=0;
    //全遍历这种找法有一半是多余的，因为这是一个对称矩阵
    while(H->arcnum<G.vexnum-1){    //有可能顶点找完，边还没找完，但是边肯定最后是顶点-1，这种找法按边算
        for(int i=0;i<G.vexnum;i++){
            for(int j=0;j<G.vexnum;j++){
                //找到最小的那条边，记录新的顶点和边
                if(G.Edge[i][j]<min && connected[i]!=connected[j]){ //边为最小，且2个顶点在不同的连通分量内
                    min = G.Edge[i][j];
                    edgeS = i;
                    edgeE = j;
                }
            }
        }
        //找到一组最小的边与新加的顶点
        H->Edge[edgeS][edgeE] = min;
        H->arcnum ++;
        //更新当前连通分量,把拥有相同连通分量的都更新为他们之间的同一种标记
        for(int k=0;k<G.vexnum;k++){
            if(connected[k]==edgeS||connected[k]==edgeE){
                connected[k]=edgeS; //更新为同一种标记
            }
        }
    }
    return H;
}

图的应用-最短路径-Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//寻找顶点下标为VexIndex的单源最短路径(默认连通),不适用于负权值的图,路径不存在为0，增加判断，也可以设为MAX方便
int path[MaxVertexNum][MaxVertexNum]; //输出路径数组,每个顶点有一条路径,path[i][]为到顶点i的路径
void SPDijkstra(MGragh G,int VexIndex){
    int dist[MaxVertexNum];
    int Vexcount=0;
    for(int i=0;i<G.vexnum;i++){    //数组初始化
        for(int j=0;j<G.vexnum;j++){
            path[i][j]=-1;
        }
        path[i][0] = VexIndex;
        path[i][1] = i;
        dist[i]=G.Edge[VexIndex][i];    //初试距离为起点到各个顶点的直接距离
    }
    int mindist=999999;
    int minVex = -1;
    while(Vexcount<G.vexnum){
        for(int i=0;i<G.vexnum;i++){
            if(dist[i]<mindist&&dist[i]!=0){    //存在路径且为最短
                mindist = dist[i];  //找到当前距离最短的那条
                minVex = i;
            }
        }
        Vexcount++;
        int tempIndex=0;
        for(int i=0;i<G.vexnum;i++){    //更新新的路径总长度
            while(path[i][tempIndex]!=-1){  //找到路径的最后一个
                tempIndex++;
            }
            if(G.Edge[VexIndex][minVex]+G.Edge[minVex][i]<dist[i]){ //如果新的路径更短，则替换
                dist[i] = G.Edge[VexIndex][minVex]+G.Edge[minVex][i];
                path[i][tempIndex] = path[i][tempIndex-1];  //向原路径中插入新顶点
                path[i][tempIndex-1] = minVex;
            }else if(dist[i] == 0&&G.Edge[VexIndex][minVex]+G.Edge[minVex][i]>0){ //新路径存在，原路径不存在
                dist[i] = G.Edge[VexIndex][minVex]+G.Edge[minVex][i];
                path[i][tempIndex] = path[i][tempIndex-1];  //原来没有路径，替换新路径,此时tempIndex为2
                path[i][tempIndex-1] = minVex;
            }
        }
    }
}

图的应用-最短路径-Floyd算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//Floyd算法将Dijkstra算法的所有顶点同时计算，变成了矩阵与矩阵之间的运算，适用于负权值的图
int path[MaxVertexNum][MaxVertexNum];    //path[i][j]=k表示i->k->j,路径a->b->c->d中,path[a][d]记录了c,然后找path[a][c]得到b
void SPFloyd(MGragh G){
    int dist[MaxVertexNum][MaxVertexNum];   //存储新构成的矩阵
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            dist[i][j]=G.Edge[i][j];    //初始化为各个边
            path[i][j]=j;
        }
    }
    for(int k=0;k<G.vexnum;k++){    //遍历所有顶点作为跳板
        for(int i=0;i<G.vexnum;i++){
            for(int j=0;j<G.vexnum;j++){
                if(dist[i][j]<dist[i][k]+dist[k][j]){
                    //不用担心矩阵数据变化对后面的数造成影响，因为比较的只是第k个顶点的行列，但是那一行列在该趟中是不变的
                    dist[i][j] = dist[i][k]+dist[k][j]; //如果路径更短则替换,路径i->k->j，k->j是连续的，i->K是一整段
                    path[i][j] = path[i][k];; //替换中间顶点,记录上一整段终点
                }
                if(dist[i][j]==0&&dist[i][k]+dist[k][j]>0){
                    dist[i][j] = dist[i][k]+dist[k][j]; //如果路径存在则替换,路径i->k->j，k->j是连续的，i->K是一整段
                    path[i][j] = path[i][k];; //替换中间顶点,记录上一整段终点
                }
            }
        }
    }
}

图的应用-拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//此处使用邻接表法,拓扑排序用于检验有向无环图
bool TopologicalSort(ALGraph G){
    //如果G存在拓扑排序，返回true，否则说明G中存在环
    int output[MaxVertexNum];
    //维护一个入度数组
    int indegree[MaxVertexNum];
    for(int i=0;i<G.vexnum;i++){
        indegree[i]=0;  //入度数组初始化为0
    }
    ArcNode *currentVex;
    for(int i=0;i<G.vexnum;i++){
        currentVex = G.vertices[i].first;
        while(currentVex){  //有一个出都，则将对应的入度+1
            indegree[currentVex->adjvex]++; //出都对应顶点的入度+1
            currentVex = currentVex->next;
        }
    }
    SqStack *S = InitStack();
    for(int i=0;i<G.vexnum;i++){
        if(indegree[i] == 0){    //出度为0，没有指向其他顶点的边
            PushStack(*S, i);
        }
    }
    int count = 0;
    int current = -1;
    while(!isStackEmpty(*S)){
        current = PopStack(*S);
        output[count++] = current;    //存入拓扑排序数组，也可输出,并且count++
        currentVex = G.vertices[current].first;
        while(currentVex){  //将其所有出度的顶点，入度-1
            //将所有i指向的顶点的入度-1，并将入度为0的顶点入栈
            if(indegree[currentVex->adjvex] == 1){
                indegree[currentVex->adjvex]--;
                PushStack(*S, currentVex->adjvex);
            }
            currentVex = currentVex->next;
        }
    }
    if(count<G.vexnum){   //说明还有顶点没有参与遍历
        return false;
    }else{
        return true;
    }
}
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家