数据结构最短生成路径（BFS算法、Floyd（弗洛伊德）算法、Dijkstra算法）

标签：vexnum return int Vi Dijkstra BFS ++ 算法顶点

8.9、最短生成路径-BFS算法

BFS算法只能处理无权图

BFS算法的基本思想

代码实现

#include <stdio.h>
#include <stdlib.h>
#include<math.h>

#define MaxSize 100
#define MaxInteger 32767
#define boolean int
#define true 1
#define false 0

//邻接矩阵存储图的信息
typedef struct MGraph{
    char Vex[MaxSize];//顶点信息
    int Edge[MaxSize][MaxSize];//邻接矩阵
    int vexnum,arcnum;//顶点数和边数
}MGraph;

//初始化一个邻接矩阵
boolean MG_Init(MGraph **G){
    *G = (MGraph*)malloc(sizeof(MGraph));
    if((*G) == NULL) return false;//申请空间失败
    (*G)->vexnum = 0;//顶点数为0
    (*G)->arcnum = 0;//边数为0
    // for(int i = 0;i < MaxSize;i++){
    //     for(int j = 0;j < MaxSize;j++){
    //         (*G)->Edge[i][j] = 0;
    //     }
    // }
    return true;
}

//获取该结点v的索引
int GetV_Index(MGraph *G,char v){
    for(int i = 0;i<G->vexnum;i++){
        if(G->Vex[i] == v) return i;
    }
    return -1;
}

//判断图中是否有结点v
boolean IsVEmpty(MGraph *G,char v){
    for(int i=0;i<G->vexnum;i++){
        if(G->Vex[i] == v) return true;//存在
    }
    return false;//不存在
}

//判断图中是否存在该边;传入边
boolean Adjancent(MGraph *G,char v,char w){
    int vi = GetV_Index(G,v);
    int wi = GetV_Index(G,w);

    return G->Edge[vi][wi];
}
//判断图中是否存在该边;传入边的索引
boolean Adjancent1(MGraph *G,int vi,int wi){
    if(G->Edge[vi][wi] == 1) return true;
    else return false;
}

//插入一个新的顶点
boolean InsertV(MGraph *G,char v){
    if(G->vexnum >= MaxSize || IsVEmpty(G,v)){
        printf("存储顶点数的空间满了或者改结点存在！\n");
        return false;
    }
    G->Vex[G->vexnum++] = v;
    return true;
}

//插入边(v,w)
boolean AddEdge(MGraph *G,char v,char w){
    if(!IsVEmpty(G,v) || !IsVEmpty(G,w)){
        printf("输入的边其中有一个顶点或者两个顶点不存在\n");
        return false;
    }
    //获取结点的索引
    int vi = GetV_Index(G,v);
    int wi = GetV_Index(G,w);
    if(Adjancent1(G,vi,wi)){
        printf("该边已经存在\n");
        return false;
    }
    //修改邻接矩阵
    G->Edge[vi][wi] = 1;
    G->Edge[wi][vi] = 1;
    //修改边数
    G->arcnum++;
    return true;
}

//删除边(v,w)
boolean RemoveEdge(MGraph *G,char v,char w){
    if(!IsVEmpty(G,v) || !IsVEmpty(G,w)){
        //判断这两个点是否存在
        printf("这两个点不存在\n");
        return false;
    }
    int vi = GetV_Index(G,v);
    int wi = GetV_Index(G,w);
    if(Adjancent1(G,vi,wi) == true){//存在该边就删除
        G->Edge[vi][wi] = 0;
        G->Edge[wi][vi] = 0;
        G->arcnum--;//边减1
        return true;
    }else{
        printf("删除的边不存在\n");
        return false;
    }
}

//获取某个结点v的所有邻接边
boolean NeighBors(MGraph *G,char v,char ***res,int *length){
    if(!IsVEmpty(G,v)){
        printf("输入的顶点不存在\n");
        return false;
    }
    int vi = GetV_Index(G,v);
    for(int i = 0;i < G->vexnum;i++){
        if(G->Edge[vi][i] == 1) {
            (*length)++;
        }
    }
    *res = (char **)malloc(sizeof(char)*(*length));
    int index = 0;
    for(int i = 0;i < G->vexnum;i++){
        if(G->Edge[vi][i] == 1) {
            (*res)[index] = (char *)malloc(sizeof(char)*2);
            (*res)[index][0] = v;
            (*res)[index][1] = G->Vex[i];
            index++;
        }
    }
    return true;
}


//队列的数据信息
typedef struct ElemType{
    int index;
    char v;
}ElemType;
//结点
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
//链队列定义
typedef struct{
    LinkNode *front,*rear;//*front 队头指针, *rear 队尾指针
}LinkQueue;
//初始化带头结点的队列
int InitLinkQueue(LinkQueue *Q){
    (*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkNode));
    if((*Q).front == NULL || (*Q).rear == NULL) return false;
    (*Q).front->next = NULL;
    return true;
};
//带头结点判断是否为空
int IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    else return false;
}
//带头结点入队操作
int EnQueue(LinkQueue *Q,ElemType e){
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL) return false;//分配内存失败
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}
//带头结点出队操作
int DeQueue(LinkQueue *Q,ElemType *e){
    if(Q->front == Q->rear) return false;//队列为空，出队失败
    LinkNode *p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p){       //如果出队的元素是对尾元素，需要特殊处理
        Q->rear = Q->front;
    }
    free(p);//释放片
    return true;
}

//寻找某个结点V的所有邻接点
boolean Neighbors(MGraph *G,char V,int Vi,char **resNode,int **resIndex,int *length){
    for(int i = 0;i < G->vexnum;i++){
        if(G->Edge[Vi][i] == 1){
            (*length)++;
        } 
    }
    *resNode = (char *)malloc(sizeof(char)*(*length));
    *resIndex = (int *)malloc(sizeof(int)*(*length));
    int index = 0;
    for(int i = 0;i < G->vexnum;i++){
        if(G->Edge[Vi][i] == 1){
            (*resNode)[index] = G->Vex[i];
            (*resIndex)[index] = i;
            index++;
        }
    }
    return true;
}

//广度优先遍历到各个结点的最距离
void BFS_MIN_Distance(MGraph *G,char V,int Vi,char **res,int *resLength,boolean **visited,int ** distance,char ** path){
    LinkQueue Q;//队列
    InitLinkQueue(&Q);//初始化队列
    ElemType e;//顶点信息
    e.index = Vi;//顶点所在图的顶点集合中的位置索引
    e.v = V;//顶点的char值
    (*visited)[Vi] = true;//顶点是否遍历的数组修改
    (*distance)[Vi] = 0;
    EnQueue(&Q,e);//遍历到的顶点如队列
    while(!IsEmpty(Q)){
        DeQueue(&Q,&e);//出队列
        (*res)[*resLength] = e.v;//广度优先遍历顺序数组
        (*resLength)++;//下一个元素的数组下标
        char *resChar;//邻接结点的char值和顶点索引对应
        int *resIndex;//邻接结点的顶点索引和结点的char值对应
        int length = 0;//该结点的邻接结点个数
        Neighbors(G,e.v,e.index,&resChar,&resIndex,&length);//获取出队列结点的邻接结点信息
        for(int i = 0;i < length;i++){//没有入队列的结点如队列
            if((*visited)[resIndex[i]] == false){//判断是否已经入队了
                (*visited)[resIndex[i]] = true;//顶点是否遍历的数组修改
                (*distance)[resIndex[i]] = (*distance)[e.index]+1;//修改最短路径
                (*path)[resIndex[i]] = e.v;//修改它的直接前驱结点
                ElemType e1;
                e1.index = resIndex[i];
                e1.v = resChar[i];
                EnQueue(&Q,e1);//该结点如队列
            }
        }
    }
}
//访问结点
void visitV(char *res,int resLength){
    for(int i = 0;i < resLength;i++){
        printf("%c ,",res[i]);
    }
}
void visitDistance(int *distance,int resLength){
    for(int i = 0;i < resLength;i++){
        printf("%d ,",distance[i]);
    }
}
//对图G进行广度优先遍历
void BFSMGraph(MGraph *G,char V){
    int Vi = GetV_Index(G,V);
    char *res = (char *)malloc(sizeof(char)*G->vexnum);
    char *path = (char *)malloc(sizeof(char)*G->vexnum);
    int *distance = (int *)malloc(sizeof(int)*G->vexnum);
    int resLength = 0;
    boolean *visited = (boolean *)malloc(sizeof(boolean)*G->vexnum);
    for(int i = 0;i < G->vexnum;i++){
        visited[i] = false;
        path[i] = '~';
        distance[i] = MaxInteger;
    }
    BFS_MIN_Distance(G,V,Vi,&res,&resLength,&visited,&distance,&path);
    
    printf("广度优先遍历的结果：");
    visitV(res,resLength);
    printf("\n");
    printf("\n");
    printf("结点信息：");
    visitV(G->Vex,G->vexnum);
    printf("\n");
    printf("最短长度distance[]：");
    visitDistance(distance,resLength);
    printf("\n");
    printf("结点前驱path[]：");
    visitV(path,resLength);
}


int main(){
    MGraph *G;
    MG_Init(&G);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    InsertV(G,'A');
    InsertV(G,'B');
    InsertV(G,'C');
    InsertV(G,'D');
    InsertV(G,'E');
    InsertV(G,'F');
    InsertV(G,'G');
    InsertV(G,'H');
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    AddEdge(G,'A','B');
    AddEdge(G,'A','C');
    AddEdge(G,'C','D');
    AddEdge(G,'D','E');
    AddEdge(G,'D','F');
    AddEdge(G,'E','F');
    AddEdge(G,'E','G');
    AddEdge(G,'F','G');
    AddEdge(G,'F','H');
    AddEdge(G,'G','H');
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);

    BFSMGraph(G,'C');

    return 0;
}

//结果：
顶点数：0；边数：0
顶点数：8；边数：0
顶点数：8；边数：10
广度优先遍历的结果：C ,A ,D ,B ,E ,F ,G ,H ,

结点信息：			A ,B ,C ,D ,E ,F ,G ,H ,
最短长度distance[]：	1 ,2 ,0 ,1 ,2 ,2 ,3 ,3 ,
结点前驱path[]：		C ,A ,~ ,C ,D ,D ,E ,F ,

8.10、最短生成路径-Dijkstra算法

适用于单个结点到其他结点之间

Dijkstra算法的思想

Dijkstra算法代码实现

#include <stdio.h>
#include <stdlib.h>
#include<math.h>

#define MaxSize 100
#define MaxInteger 32767
#define boolean int
#define true 1
#define false 0

//边\弧
typedef struct ArcNode{
    int adjvex;//边或者弧指向的那个结点
    struct ArcNode *next;//指向下一个弧的指针
   	int info;//权值
}ArcNode;

//顶点信息
typedef struct ElemType{
    char v;//顶点信息
    int flag;//顶点是否被使用，1表示使用，0表示未使用
}ElemType;

//顶点
typedef struct VNode{
    ElemType data;//顶点信息
    ArcNode *first;//第一个边或弧
}VNode,AdjList[MaxSize];

//有向图的邻接表存储
typedef struct MGraph{
    AdjList vertices;//图的信息
    int vexnum,arcnum;//顶点数和边数
}MGraph;

//初始化图
boolean MG_Init(MGraph **G){
    (*G) = (MGraph *)malloc(sizeof(MGraph));
    if(*G == NULL){
        printf("内存申请失败！\n");
        return false;
    }
    (*G)->arcnum = 0;//边数
    (*G)->vexnum = 0;//顶点数
    for(int i = 0;i < MaxSize;i++){//把所有带使用的顶点信息数据使用标志全置为0
        (*G)->vertices[i].data.flag = 0;
        (*G)->vertices[i].first = NULL;
    }
    return true;
}

//判断顶点V是否存在,并获取边的索引Vi
boolean IsVEmpty(MGraph *G,ElemType V,int *Vi){
    for(int i = 0;i < G->vexnum;i++){
        if(G->vertices[i].data.v == V.v && G->vertices[i].data.flag == 1) {
            *Vi = i;
            return true;
        }
    }
    return false;
}

//判断边是否存在:
boolean Adjancent(MGraph *G,ElemType V,ElemType W,int *Vi,int *Wi){
    if(!IsVEmpty(G,V,Vi) || !IsVEmpty(G,W,Wi)){
        printf("其中一个顶点不存在!!/\n");
        return true;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node != NULL){
        if(node->adjvex == *Wi){
            // printf("边已经存在\n");
            return true;
        }
        node = node->next;
    }
    return false;
}

//插入顶点
boolean InsertV(MGraph *G,ElemType V){
    int *Vi;
    if(IsVEmpty(G,V,Vi)){
        printf("顶点已经存在！！\n");
        return false;
    }
    V.flag = 1;
    G->vertices[G->vexnum++].data = V;
    return true;
}

//插入边
boolean AddArcNode(MGraph *G,ElemType V,ElemType W,int info){
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    if(Adjancent(G,V,W,Vi,Wi)){//判断边是否存在
        return false;
    }
    ArcNode * p = (ArcNode*)malloc(sizeof(ArcNode));
    p->adjvex = *Wi;
    p->info = info;
    p->next = NULL;
    if(G->vertices[*Vi].first == NULL){//没有边，新增加边
        G->vertices[*Vi].first = p;
        G->arcnum++;
        return true;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node->next != NULL){
        node = node->next;
    }
    node->next = p;
    G->arcnum++;
    return true;
}

//获取某个结点v的所有邻接边;<v,wi>;以v为尾巴
boolean NeighBors(MGraph *G,ElemType V,ElemType ***res,int **infos,int *length){
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G,V,Vi)){
        return false;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node != NULL){
        (*length)++;
        node = node->next;
    }
    *res = (ElemType **)malloc(sizeof(ElemType)*(*length));
    *infos = (int *)malloc(sizeof(ElemType)*(*length));
    node = G->vertices[*Vi].first;
    for(int i=0;i < (*length) ;i++){
        (*res)[i] = (ElemType *)malloc(sizeof(ElemType)*3);
        (*res)[i][0] = V;
        (*res)[i][1] = G->vertices[node->adjvex].data;
        (*infos)[i] = node->info;
        node = node->next;
    }
    return true;
}

//Dijkstra算法  G是图，V表示从哪个顶点出发，distance表示最短权值集合，path表示该顶点的前驱
void Dijkstra_Min_Path(MGraph *G,ElemType V,int **distance,char **path,int **pathIndex){
    boolean *fianl = (int *)malloc(sizeof(int)*(G->vexnum));//标记数组
    for(int i = 0;i < G->vexnum;i++){//初始化标记数组
        fianl[i] = false;
    }
    int Vi;
    IsVEmpty(G,V,&Vi);//获取当前结点的索引
    (*distance)[Vi] = 0;//初始化当前结点到自己为0
    int sum = 1;//记录已经找到的结点数

    while(sum < G->vexnum){
        fianl[Vi] = true;//修改当前结点的值
        sum++;//进入顶点数+1
        ArcNode *node = G->vertices[Vi].first;//前一个加入结点的第一条边
        while(node != NULL){
            //获取该边的信息
            int Wi = node->adjvex;//下一个顶点的索引
            int info = node->info;//这条边的权值
            if(fianl[Wi] == false && (*distance)[Wi] > info){//满足该结点没有加入和权值小之前的就修改信息
                (*distance)[Wi] = info + (*distance)[Vi];
                (*path)[Wi] = G->vertices[Vi].data.v;
                (*pathIndex)[Wi] = Vi;
            }
            node = node->next;//继续遍历
        }
        //循环获取当前distance中最小的
        int min = MaxInteger;
        for(int i = 0;i < G->vexnum;i++){//寻找最小的路径
            if(fianl[i] == false && min > (*distance)[i]){
                min = (*distance)[i];//最小值
                Vi = i;//顶点索引
            }
        }
    }

}

//打印信息
void Visited(MGraph *G,int *distance,char *path,int *pathIndex){
    printf("字母顺序：");
    for(int i = 0; i < G->vexnum;i++){
        printf("%c,",G->vertices[i].data.v);
    }
    printf("\n");
    printf("路径distance[]：");
    for(int i = 0; i < G->vexnum;i++){
        printf("%d,",distance[i]);
    }
    printf("\n");
    printf("前驱path[]：");
    for(int i = 0; i < G->vexnum;i++){
        printf("%c,",path[i]);
    }
    printf("\n");
    printf("索引pathIndex[]：");
        for(int i = 0; i < G->vexnum;i++){
        printf("%d,",pathIndex[i]);
    }
}

//Dijkstra算法的使用
void Dijkstra(MGraph *G,ElemType V){
    int *distance = (int *)malloc(sizeof(int)*(G->vexnum));
    char *path = (char *)malloc(sizeof(char)*(G->vexnum));
    int *pathIndex = (int *)malloc(sizeof(int)*(G->vexnum));
    for(int i = 0;i < G->vexnum;i++){
        distance[i] = MaxInteger;
        path[i] = '~';
        pathIndex[i] = -1;
    }
    Dijkstra_Min_Path(G,V,&distance,&path,&pathIndex);
    Visited(G,distance,path,pathIndex);
}

//移除该边<V,W>
boolean RemoveArcNode(MGraph *G,ElemType V,ElemType W){
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    if(!Adjancent(G,V,W,Vi,Wi)){//判断该边是否存在
        return false;
    }
    ArcNode *delete = G->vertices[*Vi].first;//删除的结点
    ArcNode *pre = NULL;//删除边的前一个结点
    while(delete != NULL){//寻找删除的边
        if(delete->adjvex == *Wi){
            break;
        }
        pre = delete;
        delete = delete->next;
    }
    if(pre == NULL){
        G->vertices[*Vi].first = G->vertices[*Vi].first->next;
    }else{
        pre->next = delete->next;//修改指针
    }
    G->arcnum--;//修改边数
    free(delete);//释放内存

    return true;
}

//删除顶点
boolean DeleteV(MGraph *G,ElemType V){
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G,V,Vi)){
        return false;
    }
    ArcNode *W = G->vertices[*Vi].first;
    while(W != NULL){
        RemoveArcNode(G,V,G->vertices[G->vertices[*Vi].first->adjvex].data);
        W = G->vertices[*Vi].first;
    }
    int index = 0;
    int sum = 0;
    while(sum < G->vexnum){
        if(G->vertices[index].data.flag==1){
            W = G->vertices[index].first;
            while(W != NULL){
                if(W->adjvex == *Vi){
                    RemoveArcNode(G,G->vertices[index].data,V);
                    break;
                }
                W = W->next;
            }
            sum++;
        }
        index++;
    }
    G->vertices[*Vi].data.flag = 0;
    G->vexnum--;
    return true;
}


int main(){
    MGraph *G;
    MG_Init(&G);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    ElemType V1;
    V1.v = 'A';
    InsertV(G,V1);
    ElemType V2;
    V2.v = 'B';
    InsertV(G,V2);
    ElemType V3;
    V3.v = 'C';
    InsertV(G,V3);
    ElemType V4;
    V4.v = 'D';
    InsertV(G,V4);
    ElemType V5;
    V5.v = 'E';
    InsertV(G,V5);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    AddArcNode(G,V1,V2,10);
    AddArcNode(G,V1,V5,5);
    AddArcNode(G,V2,V3,1);
    AddArcNode(G,V2,V5,2);
    AddArcNode(G,V3,V4,4);
    AddArcNode(G,V4,V1,7);
    AddArcNode(G,V4,V3,6);
    AddArcNode(G,V5,V2,3);
    AddArcNode(G,V5,V3,9);
    AddArcNode(G,V5,V4,2);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    Dijkstra(G,V1);

    return 0;
}
//结果：
顶点数：0；边数：0
顶点数：5；边数：0
顶点数：5；边数：10
    
字母顺序：			A,B,C,D,E,
路径distance[]：	 0,8,9,7,5,
前驱path[]：		 ~,E,B,E,A,
索引pathIndex[]：	-1,4,1,4,0,

注意：如果有负数带权值的，这个算法可能会失效不行

8.11、最短生成路径-Floyd（弗洛伊德）算法

Floyd（弗洛伊德）算法：求出每一对顶点之间的最短路径

使用动态规划的思想，将问题分为多个阶段

对于n个顶点的图G，求任意一对顶点\(V_i -> V_j\)之间的最短路径可分为如下阶段：

初始：不允许其他顶点中转，最短路径是？

0：允许\(V_0\)中转，最短路径是？

1：允许\(V_1\)中转，最短路径是？

......

n-1：允许\(V_{n-1}\)中转，最短路径是？

设定一个\(A\)矩阵来存储该图的邻接矩阵，\(path\)矩阵来存储两个顶点之间最短路径经过的顶点

\(若： A^{(k-1)}[i][j] > A^{(k-1)}[i][k]+A^{(k-1)}[k][j])\)

\(则：A^{k}[i][j] = A^{(k-1)}[i][k]+A^{(k-1)}[k][j])\)

\(path^k[i][j] = k\)

\(否则：A^{k}和path^k保持原值\)

Floyd算法的思想

注意：不能实现回路带有负权值的

Floyd算法代码实现

#include <stdio.h>
#include <stdlib.h>
#include<math.h>

#define MaxSize 100
#define MaxInteger 32767
#define boolean int
#define true 1
#define false 0

//边\弧
typedef struct ArcNode{
    int adjvex;//边或者弧指向的那个结点
    struct ArcNode *next;//指向下一个弧的指针
   	int info;//权值
}ArcNode;

//顶点信息
typedef struct ElemType{
    char v;//顶点信息
    int flag;//顶点是否被使用，1表示使用，0表示未使用
}ElemType;

//顶点
typedef struct VNode{
    ElemType data;//顶点信息
    ArcNode *first;//第一个边或弧
}VNode,AdjList[MaxSize];

//有向图的邻接表存储
typedef struct MGraph{
    AdjList vertices;//图的信息
    int vexnum,arcnum;//顶点数和边数
}MGraph;

//初始化图
boolean MG_Init(MGraph **G){
    (*G) = (MGraph *)malloc(sizeof(MGraph));
    if(*G == NULL){
        printf("内存申请失败！\n");
        return false;
    }
    (*G)->arcnum = 0;//边数
    (*G)->vexnum = 0;//顶点数
    for(int i = 0;i < MaxSize;i++){//把所有带使用的顶点信息数据使用标志全置为0
        (*G)->vertices[i].data.flag = 0;
        (*G)->vertices[i].first = NULL;
    }
    return true;
}

//判断顶点V是否存在,并获取边的索引Vi
boolean IsVEmpty(MGraph *G,ElemType V,int *Vi){
    for(int i = 0;i < G->vexnum;i++){
        if(G->vertices[i].data.v == V.v && G->vertices[i].data.flag == 1) {
            *Vi = i;
            return true;
        }
    }
    return false;
}

//判断边是否存在:
boolean Adjancent(MGraph *G,ElemType V,ElemType W,int *Vi,int *Wi){
    if(!IsVEmpty(G,V,Vi) || !IsVEmpty(G,W,Wi)){
        printf("其中一个顶点不存在!!/\n");
        return true;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node != NULL){
        if(node->adjvex == *Wi){
            // printf("边已经存在\n");
            return true;
        }
        node = node->next;
    }
    return false;
}

//插入顶点
boolean InsertV(MGraph *G,ElemType V){
    int *Vi;
    if(IsVEmpty(G,V,Vi)){
        printf("顶点已经存在！！\n");
        return false;
    }
    V.flag = 1;
    G->vertices[G->vexnum++].data = V;
    return true;
}

//插入边
boolean AddArcNode(MGraph *G,ElemType V,ElemType W,int info){
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    if(Adjancent(G,V,W,Vi,Wi)){//判断边是否存在
        return false;
    }
    ArcNode * p = (ArcNode*)malloc(sizeof(ArcNode));
    p->adjvex = *Wi;
    p->info = info;
    p->next = NULL;
    if(G->vertices[*Vi].first == NULL){//没有边，新增加边
        G->vertices[*Vi].first = p;
        G->arcnum++;
        return true;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node->next != NULL){
        node = node->next;
    }
    node->next = p;
    G->arcnum++;
    return true;
}

//获取某个结点v的所有邻接边;<v,wi>;以v为尾巴
boolean NeighBors(MGraph *G,ElemType V,ElemType ***res,int **infos,int *length){
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G,V,Vi)){
        return false;
    }
    ArcNode *node = G->vertices[*Vi].first;
    while(node != NULL){
        (*length)++;
        node = node->next;
    }
    *res = (ElemType **)malloc(sizeof(ElemType)*(*length));
    *infos = (int *)malloc(sizeof(ElemType)*(*length));
    node = G->vertices[*Vi].first;
    for(int i=0;i < (*length) ;i++){
        (*res)[i] = (ElemType *)malloc(sizeof(ElemType)*3);
        (*res)[i][0] = V;
        (*res)[i][1] = G->vertices[node->adjvex].data;
        (*infos)[i] = node->info;
        node = node->next;
    }
    return true;
}


//Floyd（弗洛伊德）算法;A是邻接矩阵，path是两个顶点之间的中转点矩阵
void Floyd_Min_Path(MGraph *G,int ***A,int ***path,char ***pathChar){
    for(int k = 0;k < G->vexnum;k++){//遍历每个顶点，以该顶点作为中转点
        //遍历A矩阵
        for(int i = 0;i < G->vexnum;i++){
            for(int j = 0;j < G->vexnum;j++){
                if((*A)[i][j] > (*A)[i][k] + (*A)[k][j]){//如果加入k这个顶点后小于之前就更新
                    (*A)[i][j] = (*A)[i][k] + (*A)[k][j];//更新i和j之间的最短距离
                    (*path)[i][j] = k;//更新中转顶点
                    (*pathChar)[i][j] = G->vertices[k].data.v;
                }
            }
        }
    }
}

//打印信息
void Visited_Floyd(MGraph *G,int **A,int **path,char **pathChar){
    printf("A矩阵：\n");
    for(int i = 0;i < G->vexnum;i++){
        for(int j = 0;j<G->vexnum;j++){
            printf("%3d,  ",A[i][j]);
        }
        printf("\n");
    }
    printf("path矩阵：\n");
    for(int i = 0;i < G->vexnum;i++){
        for(int j = 0;j<G->vexnum;j++){
            printf("%3d,  ",path[i][j]);
        }
        printf("\n");
    }
    printf("pathChar矩阵：\n");
    for(int i = 0;i < G->vexnum;i++){
        for(int j = 0;j<G->vexnum;j++){
            printf("%3c,  ",pathChar[i][j]);
        }
        printf("\n");
    }
}
//Floyd（弗洛伊德）算法使用
void Floyd(MGraph *G){
    int **A = (int **)malloc(sizeof(int)*(G->vexnum));//邻接矩阵
    int **path = (int **)malloc(sizeof(int)*(G->vexnum));//顶点中转矩阵的索引
    char **pathChar = (char **)malloc(sizeof(char)*(G->vexnum));//顶点中转矩阵的char值
    //初始化
    for(int i = 0;i < G->vexnum;i++){
        A[i] = (int *)malloc(sizeof(int)*(G->vexnum));
        pathChar[i] = (char *)malloc(sizeof(char)*(G->vexnum));
        path[i] = (int *)malloc(sizeof(int)*(G->vexnum));
        for(int j = 0; j < G->vexnum;j++){
            path[i][j] = -1;
            pathChar[i][j] = '~';
            if(i == j){
                A[i][j] = 0;
            }else{
                A[i][j] = MaxInteger;
            }
        }
    }

    //把图中信息更新到邻接矩阵
    for(int i = 0;i < G->vexnum;i++){
        ArcNode *node = G->vertices[i].first;
        while(node != NULL){
            A[i][node->adjvex] =node->info; 
            node = node->next;
        }
    }

    //调用Floyd（弗洛伊德）算法
    Floyd_Min_Path(G,&A,&path,&pathChar);
    //打印信息
    Visited_Floyd(G,A,path,pathChar);
}

//移除该边<V,W>
boolean RemoveArcNode(MGraph *G,ElemType V,ElemType W){
    int *Vi = (int *)malloc(sizeof(int));
    int *Wi = (int *)malloc(sizeof(int));
    if(!Adjancent(G,V,W,Vi,Wi)){//判断该边是否存在
        return false;
    }
    ArcNode *delete = G->vertices[*Vi].first;//删除的结点
    ArcNode *pre = NULL;//删除边的前一个结点
    while(delete != NULL){//寻找删除的边
        if(delete->adjvex == *Wi){
            break;
        }
        pre = delete;
        delete = delete->next;
    }
    if(pre == NULL){
        G->vertices[*Vi].first = G->vertices[*Vi].first->next;
    }else{
        pre->next = delete->next;//修改指针
    }
    G->arcnum--;//修改边数
    free(delete);//释放内存

    return true;
}

//删除顶点
boolean DeleteV(MGraph *G,ElemType V){
    int *Vi = (int *)malloc(sizeof(int));
    if(!IsVEmpty(G,V,Vi)){
        return false;
    }
    ArcNode *W = G->vertices[*Vi].first;
    while(W != NULL){
        RemoveArcNode(G,V,G->vertices[G->vertices[*Vi].first->adjvex].data);
        W = G->vertices[*Vi].first;
    }
    int index = 0;
    int sum = 0;
    while(sum < G->vexnum){
        if(G->vertices[index].data.flag==1){
            W = G->vertices[index].first;
            while(W != NULL){
                if(W->adjvex == *Vi){
                    RemoveArcNode(G,G->vertices[index].data,V);
                    break;
                }
                W = W->next;
            }
            sum++;
        }
        index++;
    }
    G->vertices[*Vi].data.flag = 0;
    G->vexnum--;
    return true;
}


int main(){
    MGraph *G;
    MG_Init(&G);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    ElemType V1;
    V1.v = 'A';
    InsertV(G,V1);
    ElemType V2;
    V2.v = 'B';
    InsertV(G,V2);
    ElemType V3;
    V3.v = 'C';
    InsertV(G,V3);
    ElemType V4;
    V4.v = 'D';
    InsertV(G,V4);
    ElemType V5;
    V5.v = 'E';
    InsertV(G,V5);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    AddArcNode(G,V1,V2,10);
    AddArcNode(G,V1,V5,5);
    AddArcNode(G,V2,V3,1);
    AddArcNode(G,V2,V5,2);
    AddArcNode(G,V3,V4,4);
    AddArcNode(G,V4,V1,7);
    AddArcNode(G,V4,V3,6);
    AddArcNode(G,V5,V2,3);
    AddArcNode(G,V5,V3,9);
    AddArcNode(G,V5,V4,2);
    printf("顶点数：%d；边数：%d\n",G->vexnum,G->arcnum);
    Floyd(G);

    return 0;
}

//结果：
顶点数：0；边数：0
顶点数：5；边数：0
顶点数：5；边数：10
    
A矩阵：
  0,    8,    9,    7,    5,
 11,    0,    1,    4,    2,
 11,   19,    0,    4,   16,
  7,   15,    6,    0,   12,
  9,    3,    4,    2,    0,
path矩阵：
 -1,    4,    4,    4,   -1,
  4,   -1,   -1,    4,   -1,
  3,    4,   -1,   -1,    3,
 -1,    4,   -1,   -1,    0,
  3,   -1,    1,   -1,   -1,
pathChar矩阵：
  ~,    E,    E,    E,    ~,
  E,    ~,    ~,    E,    ~,
  D,    E,    ~,    ~,    D,
  ~,    E,    ~,    ~,    A,
  D,    ~,    B,    ~,    ~,

	BFS 算法	Dijkstra 算法	Floyd 算法
无权图	是	是	是
带权图	否	是	是
带权负值图	否	否	是
带负值权回路图	否	否	否
时间复杂度	\(O(\|V\|^2)或O(\|V\|+\|E\|)\)	\(O(\|V\| ^2)\)	\(O(\|V\|^3)\)
通用用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图各顶点间的最短路径

标签：vexnum,return,int,Vi,Dijkstra,BFS,++,算法,顶点
From： https://www.cnblogs.com/shuisanya/p/16869303.html

数据结构最短生成路径（BFS算法、Floyd（弗洛伊德）算法、Dijkstra算法）

相关文章

赞助商

阅读排行

数据结构 最短生成路径（BFS算法、Floyd（弗洛伊德）算法、Dijkstra算法）

相关文章

赞助商

阅读排行

数据结构最短生成路径（BFS算法、Floyd（弗洛伊德）算法、Dijkstra算法）