作者在 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;
}
#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;
}