【标准C】图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现

谁借莪１个温暖的怀抱￠ 2023-07-23 02:35 27阅读 0赞

直接贴代码，给有需要的人，各类函数都已封装好，直接使用。用的是标准C写的，直接复制粘贴即可试用，有问题欢迎指正。如果对你有帮助麻烦给个赞哈~【未经允许，请勿转载】

//无向图哦
    #include<stdio.h>
    #include<stdlib.h>
    #define max 10010
    #define INF 0x3fffffff
    int visit[max];
    int father[max];//并查集父亲结点
    /*ArcNode:最基本的结构体，weigh&adjvex，不做说明*/
    typedef struct ArcNode//弧结点
    { 
        int weigh;//该弧的权重
        int adjvex;//该弧指向的结点序号
        struct ArcNode* next;//指向下一个弧结点
    }ArcNode;
    /* 邻接表，每个图由一个邻接表指针数组组成， g->vertices[i]访问，i取值为点的个数 每个vertices[i]有head与size变量。head为出的每个点，用arcnode表示 */
    typedef struct VertexNode
    {    int size;
        ArcNode* head;//指向头结点
    }VertexNode,*Adjlist[max];
    
    /*定义图的邻接表，一张图仅一个包括一个邻接表数组vertices 和该图的弧数，顶点数 */
    typedef struct Graph
    { 
        Adjlist vertices;//定义一个邻接表
        int vexnum;//顶点数
        int arcnum;//弧数
    }Graph;
    //QNode
    typedef struct Node
    { 
        int data ;
        struct Node* next;
    }Node;
    
    /*图的广度遍历需要队列，故先实现队列和队列的基本操作*/
    typedef struct Queue
    { 
        int size = 0;
        Node* head;
    }Queue;
    Queue* createQueue()
    { 
        Queue* q = (Queue*)malloc(sizeof(Queue));
        q->head = NULL;
        q->size = 0;
        return q;
    }
    void Push(Queue* q,int x)
    { 
        if(q->size == 0)
         { 
          q->head = (Node*)malloc(sizeof(Node));
          q->size++;
          q->head->data = x;
          q->head->next = NULL;
          return ;
         }
         else
         { 
             Node* tmp = q->head;
             while(tmp->next!=NULL)
                tmp = tmp->next;
             tmp->next = (Node*)malloc(sizeof(Node));
             tmp->next->data = x;
            tmp->next->next = NULL;
             q->size++;
             return;
         }
    }
    int Pop(Queue* q)
    { 
        if(q->size==0){ 
            printf("ERROR,Queue Empty");return -1;}
        if(q->size==1)
                { 
                int tmp = q->head->data;
                q->head==NULL;
                q->size--;
                return tmp;
                }
        else
        { 
            Node* p = q->head;
            q->head = p->next;
            int tmp = p->data;
            free(p);
            q->size--;
            return tmp;
        }
    
    }
    
    /*Kruskal需要并查集进行求环操作，所以先实现并查集（disjoint set union）及其基本操作*/
    void initialDSU(int n)//容量为n
    { 
        for(int i=0;i<n;i++)
            father[i] = i;
    }
    int findFather(int x)
    { 
        if(father[x]==x)
            return x;
        return findFather(father[x]);
    }
    void Union(int a,int b)
    { 
        int faA = findFather(a);
        int faB = findFather(b);
        if(faA!=faB)
        { 
            father[faA] = faB;
        }
    }
    
    
    /*邻接表中找到a结点(vertices[a])利用在队尾插入一个结点，size++; B结点同理*/
    void insertNode(Graph* g,int node1,int node2,int arcWeigth)
    { 
        if(g->vertices[node1]->size==0)
        { 
            g->vertices[node1]->head = (ArcNode*)malloc(sizeof(ArcNode));
            g->vertices[node1]->head->next = NULL;
            g->vertices[node1]->head->weigh = arcWeigth;
            g->vertices[node1]->head->adjvex = node2;
            g->vertices[node1]->size++;
        }
        else
        { 
            ArcNode* tmp =  g->vertices[node1]->head ;
            while(tmp->next!=NULL)
                tmp = tmp->next;
            tmp->next = (ArcNode*)malloc(sizeof(ArcNode));
                tmp->next->next = NULL;
            tmp->next->weigh = arcWeigth;
            tmp->next->adjvex = node2;
            g->vertices[node1]->size++;
        }
    
            if(g->vertices[node2]->size==0)
        { 
            g->vertices[node2]->head = (ArcNode*)malloc(sizeof(ArcNode));
            g->vertices[node2]->head->next = NULL;
            g->vertices[node2]->head->weigh = arcWeigth;
            g->vertices[node2]->head->adjvex = node1;
            g->vertices[node2]->size++;
        }
        else
        { 
            ArcNode* tmp =  g->vertices[node2]->head ;
            while(tmp->next!=NULL)
                tmp = tmp->next;
            tmp->next = (ArcNode*)malloc(sizeof(ArcNode));
                tmp->next->next = NULL;
            tmp->next->weigh = arcWeigth;
            tmp->next->adjvex = node1;
            g->vertices[node2]->size++;
        }
    }
    Graph* createGraph(int vexnum,int arcnum,int input[][3])
    { 
        Graph* g = (Graph*)malloc(sizeof(Graph));
        g->vexnum = vexnum;
        g->arcnum = arcnum;
        for(int i=0;i<vexnum;i++)
        {    g->vertices[i] = (VertexNode*)malloc(sizeof(VertexNode));
            g->vertices[i]->head = NULL;
            g->vertices[i]->size = 0;
        }
        for(int i=0;i<arcnum;i++)
        insertNode(g,input[i][0],input[i][1],input[i][2]);
        return g;
        }
    
    void DFS(int i,Graph* g)
    { 
       visit[i] = 1;
        printf("%d ",i);
           if(g->vertices[i]->head==NULL)
           { 
            return;//该结点孤立
           }
    
        else { 
            ArcNode* tmp = g->vertices[i]->head;
            while(tmp!=NULL){ 
           if(visit[tmp->adjvex]==0)
            DFS(tmp->adjvex,g);
            tmp = tmp->next;
            }
        }
    }
    void DFSTravel(Graph* g)
    {  for(int i=0;i<g->vexnum;i++)
            visit[i] = 0;
        for(int i=0;i<g->vexnum;i++)
           if(visit[i]==0)
            DFS(i,g);
    }
    void BFS(Graph* g,int j)
    { 
        Queue* que = createQueue();
        Push(que,j);
        while(que->size!=0)
        { 
            int i = Pop(que);
            if(visit[i]==0)
            { 
                visit[i]=1;
                printf("%d ",i);
               ArcNode* tmp = g->vertices[i]->head;
               while(tmp!=NULL)
                   { Push(que,tmp->adjvex);
                    tmp = tmp->next;
                   }
            }
        }
    }
    void BFSTravel(Graph* g)
    {    for(int i=0;i<g->vexnum;i++)
            visit[i] = 0;
        for(int i=0;i<g->vexnum;i++)
           if(visit[i]==0)
            BFS(g,i);
    }
    /*需要用到的全局变量*/
    int d[max];
    void Dijkstra(Graph *g,int start)
    { 
        //Initialize
        for(int i=0;i<g->vexnum;i++)
        { 
            d[i] = INF;
            visit[i]=0;
        }
        d[start] = 0;
        //循环n次
        for(int i=0;i<g->vexnum;i++)
        { 
            //
            int min = INF;
            int u = -1;//被选中的结点
            for(int j=0;j<g->vexnum;j++)
            { 
                if(visit[j]==0&&d[j]<min)
                { 
                 u = j;
                 min = d[j];
                }
            }
            if(u==-1)
            { 
                break;//不连通
            }
            visit[u] = 1;//访问u
            //更新距离数组
            if(g->vertices[u]->size!=0)
            { 
                ArcNode* tmp = g->vertices[u]->head;
            for(int j=0;j<g->vertices[u]->size;j++)
            { 
                int tmpNode = tmp->adjvex;
                if(visit[tmpNode]==0&&d[tmpNode]>d[u]+tmp->weigh)
                { 
                    d[tmpNode] = d[u]+tmp->weigh;
                }
                tmp = tmp->next;
            }}
        }
                        for(int i=0;i<g->vexnum;i++)
            {    if(d[i]==INF)
                printf("PATH:%d->%d Distance:∞\n",start,i);
                else
                printf("PATH:%d->%d Distance:%d\n",start,i,d[i]);
            }
    }
    
    int  Prim(Graph *g,int start)
    { 
        //Initialize
        for(int i=0;i<g->vexnum;i++)
        { 
            d[i] = INF;
            visit[i] = 0;
        }
        d[start] = 0;
        for(int i=0;i<g->vexnum;i++)
        { 
            int u = -1;
            int min = INF;
            //选择即将改变的点
            for(int j=0;j<g->vexnum;j++)
            { 
                if(visit[j]==0&&d[j]<min)
                { 
                    min = d[j];
                    u = j;
                }
            }
            if(u==-1)
                break;
            //路径更新
            visit[u] = 1;
            if(g->vertices[u]->size!=0)
            { 
                ArcNode* tmp = g->vertices[u]->head;
            for(int j=0;j<g->vertices[u]->size;j++)
                { 
                    if(visit[tmp->adjvex]==0&&d[tmp->adjvex]>(tmp->weigh))
                        d[tmp->adjvex]=(tmp->weigh);
                    tmp = tmp->next;
                }
            }
    
    }
            int result=0;
            for(int i=0;i<g->vexnum;i++)
                result = result+d[i];
            return result;
    }
    
    
    
    //Kruskal需要对所有边集合从小到大排列，并依次访问，顾应先实现对所有边的编号
    int Kruskal(Graph *g,int start)
    { 
    struct ArcSet{ 
    int vex1;
    int vex2;//vex1恒小于vex2
    int weigh;
    }*pArcSet[max];
    int cnt = 0;
    
    for(int i = 0;i<2*g->vexnum;i++)
        pArcSet[i] = (struct ArcSet*)malloc(sizeof(struct ArcSet));
    //加入到结构体中
    for(int i = 0;i<g->vexnum;i++)
    if(g->vertices[i]->size!=0)
    { 
        ArcNode* tmp = g->vertices[i]->head;
        for(int j=0;j<g->vertices[i]->size;j++)
        { 
            if(i<tmp->adjvex)
            { 
            pArcSet[cnt]->vex1 = i;
            pArcSet[cnt]->vex2 = tmp->adjvex;
            }
            else
            { 
                pArcSet[cnt]->vex2 = i;
                pArcSet[cnt]->vex1 = tmp->adjvex;
            }
            pArcSet[cnt]->weigh = tmp->weigh;
            cnt++;
            tmp = tmp->next;
        }
    }
    //直接升序排列
    for(int i=0;i<cnt;i++)
    for(int j=0;j<cnt-1-i;j++)
    if(pArcSet[j]->weigh>pArcSet[j+1]->weigh)
    { 
        struct ArcSet* tmp = pArcSet[j];
        pArcSet[j] = pArcSet[j+1];
        pArcSet[j+1] = tmp;
    }
    //删除奇数次项，cnt减半
    for(int i=0;i<cnt;i++)
        pArcSet[i] =pArcSet[2*i];
    cnt /=2;
    //开始kruskal
    //先把visit数组清0
    initialDSU(g->vexnum);//初始化并查集
    for(int i=0;i<g->vexnum;i++)//初始化visit，为了验证有没有孤立节点
        visit[i]=0;
    int sumWeigh = 0;
    for(int i=0;i<cnt;i++)
    { 
        int v1 = pArcSet[i]->vex1;
        int v2 = pArcSet[i]->vex2;
        if(findFather(v1)==findFather(v2))
            continue;
        visit[v1] = 1;
        visit[v2] = 1;
        Union(v1,v2);
        sumWeigh+=pArcSet[i]->weigh;
    }
        for(int i=0;i<g->vexnum;i++)
            if(visit[i]==0)
            return INF;
        return sumWeigh;
    }
    int main()
    { 
         int numOfvex = 4;
        int numOfarc = 4;
        int input[numOfarc][3] = { 
                                  { 0,1,4},
                                  { 1,2,7},
                                  { 2,3,1},
                                  { 3,0,8},
                                        };
        Graph* g = createGraph(numOfvex,numOfarc,input);//vex：点个数，arc：边个数
       BFSTravel(g);
       printf("\n");
        DFSTravel(g);
        printf("\n");
        Dijkstra(g,0);
        printf("\n");
        int Prim_sumWeigh = Prim(g,0);
        if(Prim_sumWeigh<INF)
        printf("Prim SumWeigth:%d",Prim_sumWeigh);
        else
        printf("Prim SumWeigth:∞");
        printf("\n");
       int Kruskal_sumWeigh =  Kruskal(g,0);
        if(Kruskal_sumWeigh<INF)
        printf("Prim SumWeigth:%d",Kruskal_sumWeigh);
        else
        printf("Prim SumWeigth:∞");
    
    }