作者在 2012-02-29 23:18:59 发布以下内容
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100
#define ApplySpaceFail -1
#define TRUE  1
#define FALSE 0
#define    UNLIMIT 65535
#define Edges 15

int visited[MaxSize];
int P[MaxSize];
int D[MaxSize];
int PF[MaxSize][MaxSize];
int DF[MaxSize][MaxSize];

typedef struct Graph{
    char vex[MaxSize];
    int  GraMtr[MaxSize][MaxSize];
    int  numVex,numEdge;
}GraNode;

typedef struct Gra{
    int begin;
    int end;
    int weight;
}GraStr[Edges],GraS;

void CreatGraph(GraNode *G){
    int i,j;
    
    if(G==NULL){
        printf("申请空间失败!\n");
        exit(ApplySpaceFail);
    }    
    G->numVex=9;    
    G->numEdge=15;
    for(i=0;i<G->numVex;i++){
        for(j=0;j<G->numVex;j++)
                    G->GraMtr[i][j]=UNLIMIT;
    }
    for(i=0;i<G->numVex;i++){
        scanf("%c",&G->vex[i]);
    }
    G->GraMtr[0][1]=G->GraMtr[1][0]=10;//1;
    G->GraMtr[0][5]=G->GraMtr[5][0]=11;//1;
    G->GraMtr[1][2]=G->GraMtr[2][1]=18;//1;
    G->GraMtr[1][6]=G->GraMtr[6][1]=16;//1;
    G->GraMtr[1][8]=G->GraMtr[8][1]=12;//1;
    G->GraMtr[2][3]=G->GraMtr[3][2]=22;//1;
    G->GraMtr[2][8]=G->GraMtr[8][2]=8;//1;
    G->GraMtr[3][4]=G->GraMtr[4][3]=20;//1;
    G->GraMtr[3][6]=G->GraMtr[6][3]=24;//1;
    G->GraMtr[3][7]=G->GraMtr[7][3]=16;//1;
    G->GraMtr[3][8]=G->GraMtr[8][3]=21;//1;
    G->GraMtr[4][5]=G->GraMtr[5][4]=26;//1;
    G->GraMtr[4][7]=G->GraMtr[7][4]=7;//1;
    G->GraMtr[5][6]=G->GraMtr[6][5]=17;//1;
    G->GraMtr[6][7]=G->GraMtr[7][6]=19;//1;
    /*G->GraMtr[0][1]=G->GraMtr[1][0]=1;
    G->GraMtr[0][2]=G->GraMtr[2][0]=5;
    G->GraMtr[1][2]=G->GraMtr[2][1]=3;
    G->GraMtr[1][3]=G->GraMtr[3][1]=7;
    G->GraMtr[1][4]=G->GraMtr[4][1]=5;
    G->GraMtr[4][3]=G->GraMtr[3][4]=2;
    G->GraMtr[2][4]=G->GraMtr[4][2]=1;
    G->GraMtr[2][5]=G->GraMtr[5][2]=7;
    G->GraMtr[4][5]=G->GraMtr[5][4]=3;
    G->GraMtr[3][6]=G->GraMtr[6][3]=3;
    G->GraMtr[4][6]=G->GraMtr[6][4]=6;
    G->GraMtr[4][7]=G->GraMtr[7][4]=9;
    G->GraMtr[5][7]=G->GraMtr[7][5]=5;
    G->GraMtr[8][6]=G->GraMtr[6][8]=7;
    G->GraMtr[6][7]=G->GraMtr[7][6]=2;
    G->GraMtr[8][7]=G->GraMtr[7][8]=4;
*/
}


void MAINDFS_TravelGraph(GraNode *G,int i){
    int k;
    printf("%c",G->vex[i]);
    visited[i]=TRUE;
    for(k=i+1;k<G->numVex;k++)
        if(G->GraMtr[i][k]==1&&visited[k]!=TRUE){
            MAINDFS_TravelGraph(G,k);
        }
    
}

void DFS_TravelGraph(GraNode *G){
    int i;
    for(i=0;i<MaxSize;i++){
        visited[i]=FALSE;
    }
    for(i=0;i<G->numVex;i++){
        if(visited[i]==FALSE)MAINDFS_TravelGraph(G,i);    
    }
}

void  BFS_TravelGraph(GraNode *G){
    int Qu[MaxSize];
    int front,rear;
    front=rear=0;
    int i,t;
    for(i=0;i<G->numVex;i++){
        visited[i]=FALSE;
    }
    rear++;
    Qu[rear]=0;
    printf("%c",G->vex[0]);
    visited[0]=TRUE;
    while(front!=rear){
        front=(front+1)%MaxSize;
        t=Qu[front];
        for(i=0;i<G->numVex;i++){
            if(visited[i]==FALSE&&G->GraMtr[t][i]==1){
                rear++;
                Qu[rear]=i;
                printf("%c",G->vex[i]);
                visited[i]=TRUE;
            }
        }
    }
}    

void MiniSpanTree_Prim(GraNode *G){
    int i,j,k,min;
    int adjvex[MaxSize]; //相关顶点数组
    int lowcost[MaxSize];//相关顶点权值
    adjvex[0]=0;
    lowcost[0]=0;
    for(i=1;i<G->numVex;i++){
        adjvex[i]=0;
        lowcost[i]=G->GraMtr[0][i];
    }
    for(i=1;i<G->numVex;i++){
        min=UNLIMIT;
        for(j=0;j<G->numVex;j++){
            if(lowcost[j]!=0&&lowcost[j]<min){
                min=lowcost[j];
                k=j;
            }
        }
        printf(" (%d,%d) ",adjvex[k],k);
        lowcost[k]=0;
        for(j=0;j<G->numVex;j++){
            if(lowcost[j]!=0&&G->GraMtr[k][j]<lowcost[j]){
                lowcost[j]=G->GraMtr[k][j];
                adjvex[j]=k;
            
            }
        }
    }
}

void CreatGraStr(GraStr Gs){
    Gs[0].begin=0;Gs[0].end=1;Gs[0].weight=10;
    Gs[1].begin=0;Gs[1].end=5;Gs[1].weight=11;
    Gs[2].begin=1;Gs[2].end=2;Gs[2].weight=18;
    Gs[3].begin=1;Gs[3].end=6;Gs[3].weight=16;
    Gs[4].begin=1;Gs[4].end=8;Gs[4].weight=12;
    Gs[5].begin=2;Gs[5].end=3;Gs[5].weight=22;
    Gs[6].begin=2;Gs[6].end=8;Gs[6].weight=8;
    Gs[7].begin=3;Gs[7].end=4;Gs[7].weight=20;
    Gs[8].begin=3;Gs[8].end=6;Gs[8].weight=24;
    Gs[9].begin=3;Gs[9].end=7;Gs[9].weight=16;
    Gs[10].begin=3;Gs[10].end=8;Gs[10].weight=21;
    Gs[11].begin=4;Gs[11].end=5;Gs[11].weight=26;
    Gs[12].begin=4;Gs[12].end=7;Gs[12].weight=7;
    Gs[13].begin=5;Gs[13].end=6;Gs[13].weight=17;
    Gs[14].begin=6;Gs[14].end=7;Gs[14].weight=19;
}

void AddQuList(GraStr Gs){
    int i,j;
    GraS t;
    for(i=0;i<Edges-1;i++){
        for(j=0;j<Edges-i-1;j++){
            if(Gs[j].weight>Gs[j+1].weight){
                t=Gs[j];        
                Gs[j]=Gs[j+1];
                Gs[j+1]=t;
            }
        }
    }
}

int Find(int *parent,int f){
    while(parent[f]>0)
        f=parent[f];
    return f;

}
        
void MiniSpanTree_Kruscal(GraStr Gs){
    int parent[Edges];    
    int i,m,n;
    for(i=0;i<Edges;i++){
        parent[i]=0;    
    }
    for(i=0;i<Edges;i++){
        m=Find(parent,Gs[i].begin);
        n=Find(parent,Gs[i].end);
        if(n!=m){
            parent[m]=n;
            printf("(%d,%d) weight:%d",Gs[i].begin,Gs[i].end,Gs[i].weight);printf("\n");
        }
    }
}
    
void ShortPath_Dijstra(GraNode *G){
    int i,j,k,min;
    int final[MaxSize];
    for(i=0;i<G->numVex;i++){
        final[i]=0;
        P[i]=0;
        D[i]=G->GraMtr[0][i];
    }
    final[0]=1;
    D[0]=0;
    for(i=1;i<G->numVex;i++){
        min=UNLIMIT;    
        for(j=0;j<G->numVex;j++){
            if(final[j]!=1&&D[j]<min){
                min=D[j];
                k=j;
            }
        }
        final[k]=1;
        for(j=0;j<G->numVex;j++){
            if(final[j]!=1&&min+G->GraMtr[k][j]<D[j]){
                D[j]=min+G->GraMtr[k][j];
                P[j]=k;
            }
        }
    }
}
        
void Dijstra_DisplayPath(GraNode *G){
    int w,k;
    int v=0;
    for(w=v+1;w<G->numVex;w++){
        printf("v%d-v%d  weight:%d   ",v,w,D[w]);
        k=P[w];
        printf("%d->",w);
        while(k!=v){
            printf("%d->",k);
            k=P[k];
        }
        printf("%d",v);
        printf("\n");
    }
}

void ShortPath_Floyd(GraNode *G){
    int v,k,w;
    for(v=0;v<G->numVex;v++){
        for(w=0;w<G->numVex;w++){
            PF[v][w]=w;
            DF[v][w]=G->GraMtr[v][w];
        }
    }
    for(k=0;k<G->numVex;k++){
        for(v=0;v<G->numVex;v++){
            for(w=0;w<G->numVex;w++){
                if(DF[v][k]+DF[k][w]<DF[v][w]){
                    DF[v][w]=DF[v][k]+DF[k][w];
                    PF[v][w]=PF[v][k];
                }
            }
        }
    }
}    

void Floyd_DisplayPath(GraNode *G){
    int v,w,k;
    for(v=0;v<G->numVex;v++){
        for(w=v+1;w<G->numVex;w++){
            printf("v%d-v%d   weight: %d ",v,w,DF[v][w]);        
            k=PF[v][w];
            printf("%d",v);
            while(k!=w){
                printf("->%d",k);
                k=PF[k][w];
            }
            printf("->%d",w);
            printf("\n");
        }
    printf("\n");        
    }
}    

int main(void){
    GraNode *Gp;
    Gp=(GraNode *)malloc(sizeof(GraNode));
    CreatGraph(Gp);
    //图的遍历(深度遍历\广度遍历)
    
//printf("深度遍历:");DFS_TravelGraph(Gp);printf("\n");
    
//printf("广度遍历:");BFS_TravelGraph(Gp);printf("\n");
    
//最小生成树(普里姆算法\克鲁斯卡尔算法)
    printf("    普里姆算法:");MiniSpanTree_Prim(Gp);printf("\n");
    GraStr GS;CreatGraStr(GS);
    AddQuList(GS);printf("克鲁斯卡尔算法:");printf("\n");
    MiniSpanTree_Kruscal(GS);printf("\n");
    //最短路径(迪杰斯特拉算法\弗洛依德算法)
    printf("迪杰斯特拉算法:");printf("\n");
    ShortPath_Dijstra(Gp);Dijstra_DisplayPath(Gp);
    printf("弗洛依德算法:");printf("\n");
    ShortPath_Floyd(Gp);Floyd_DisplayPath(Gp);
    return 0;
}
默认分类 | 阅读 776 次
文章评论,共0条
游客请输入验证码
文章分类
最新评论