#include <stdio.h>
#include <string.h>
#define MAX_VEX 20
#define MAX_ARC 20
#define MAX_INT (1<<31-1)
typedef struct
{
char szName[32];
}vexdata;
typedef struct ARCNODE
{
int adjvex;
struct ARCNODE *nextarc;
int dist;
}ArcNode;
typedef struct VEXNODE
{
vexdata data;
ArcNode *firstarc;
}VexNode;
typedef struct
{
VexNode vextices[MAX_VEX];
int vexnum,arcnum;
}net;
int FindIndex(net gb,char *name)
{
for(int i=0;i<gb.vexnum;i++)
{
if(strcmp(gb.vextices[i].data.szName,name)==0)
return i;
}
return -1;
}
void Build_Net(net &gb)
{
int dist;
int n1,n2;
char ch1[32],ch2[32];
ArcNode *pArc;
printf("请输入顶点和边的数目:");
scanf("%d%d",&gb.vexnum,&gb.arcnum);
printf("请输入顶点的信息:\n");
for(int i=0;i<gb.vexnum;i++)
{
printf("%d: ",i+1);
scanf("%s",gb.vextices[i].data.szName);
gb.vextices[i].firstarc=NULL;
}
printf("请输入边的信息(格式:顶点 顶点 距离):\n");
for(i=0;i<gb.arcnum;i++)
{
printf("%d(共%d): ",i+1,gb.arcnum);
scanf("%s%s%d",ch1,ch2,&dist);
n1=FindIndex(gb,ch1);n2=FindIndex(gb,ch2);
pArc=new ArcNode;
pArc->dist=dist;
pArc->adjvex=n2;
pArc->nextarc=gb.vextices[n1].firstarc;
gb.vextices[n1].firstarc=pArc;
pArc=new ArcNode;
pArc->dist=dist;
pArc->adjvex=n1;
pArc->nextarc=gb.vextices[n2].firstarc;
gb.vextices[n2].firstarc=pArc;
}
}
void DFS(net gb,char *name,bool visited[])
{
int start=FindIndex(gb,name);
ArcNode *pArc;
pArc=gb.vextices[start].firstarc;
printf("%s ",gb.vextices[start].data.szName);
visited[start]=true;
while(pArc)
{
if(visited[pArc->adjvex]!=true)
DFS(gb,gb.vextices[pArc->adjvex].data.szName,visited);
pArc=pArc->nextarc;
}
}
void DFSTravel(net gb,char *name)
{
bool visited[MAX_VEX];
for(int i=0;i<gb.vexnum;i++)
visited[i]=false;
DFS(gb,name,visited);
printf("\n");
}
///////////////////////////////BFS
typedef struct QNODE
{
int *elem;
int rear,front;
}Qnode;
void QInit(Qnode &Q)
{
Q.elem=new int[MAX_VEX];
Q.front=Q.rear=0;
}
void QEnter(Qnode &Q,int e)
{
if((Q.rear+1)%MAX_VEX!=Q.front)
Q.elem[Q.rear]=e;
else
printf("Full!\n");
Q.rear=(Q.rear+1)%MAX_VEX;
}
void QLeave(Qnode &Q,int &e)
{
if(Q.front!=Q.rear)
e=Q.elem[Q.front];
else
printf("Empty!\n");
Q.front=(Q.front+1)%MAX_VEX;
}
void QDestory(Qnode &Q)
{
delete []Q.elem;
Q.front=Q.rear=0;
}
void BFSTravel(net gb,char *name)
{
bool visited[MAX_VEX];
for(int i=0;i<gb.vexnum;i++)
visited[i]=false;
Qnode Q;
int start=FindIndex(gb,name);
int vex;
ArcNode *p;
printf("%s ",gb.vextices[start].data.szName);
visited[start]=true;
QInit(Q);
QEnter(Q,start);
while(Q.front!=Q.rear)
{
QLeave(Q,vex);
p=gb.vextices[vex].firstarc;
while(p)
{
if(visited[p->adjvex]!=true)
{
printf("%s ",gb.vextices[p->adjvex].data.szName);
visited[p->adjvex]=true;
QEnter(Q,p->adjvex);
}
p=p->nextarc;
}
}
}
////////////////////////////////////////Prime
typedef struct
{
int adjvex;
int lowcost;
}CloseEdge;
int GetDistance(net gb,int v1,int v2)
{
ArcNode *pArc;
pArc=gb.vextices[v1].firstarc;
while(pArc)
{
if(pArc->adjvex==v2)
return pArc->dist;
pArc=pArc->nextarc;
}
return MAX_INT;
}
int FindMin(net gb,CloseEdge mst[])
{
int vex,cost;
vex=-1;cost=MAX_INT;
for(int i=0;i<gb.vexnum;i++)
{
if(mst[i].lowcost!=0&&mst[i].lowcost<cost)
{
cost=mst[i].lowcost;
vex=i;
}
}
return vex;
}
void MST_Prime(net gb,char *name)
{
CloseEdge mst[MAX_VEX];
int start=FindIndex(gb,name);
int dist;
for(int i=0;i<gb.vexnum;i++)
{
if(i==start) continue;
dist=GetDistance(gb,start,i);
if(dist<MAX_INT)
{
mst[i].adjvex=start;
mst[i].lowcost=dist;
}
else
{
mst[i].adjvex=-1;
mst[i].lowcost=MAX_INT;
}
}
mst[start].adjvex=-1;
mst[start].lowcost=0;
int vexmin;
for(int j=0;j<gb.vexnum-1;j++)
{
vexmin=FindMin(gb,mst);
printf("%s--------%s\n",gb.vextices[vexmin].data.szName,gb.vextices[mst[vexmin].adjvex].data.szName);
mst[vexmin].lowcost=0;
for(int k=0;k<gb.vexnum;k++)
{
if(mst[k].lowcost>GetDistance(gb,vexmin,k))
{
mst[k].adjvex=vexmin;
mst[k].lowcost=GetDistance(gb,vexmin,k);
}
}
}
}
void ShortPathDIJ(net gb,char *spot1,char *spot2)
{
bool path[MAX_VEX][MAX_VEX];
int order[MAX_VEX][MAX_VEX];
int dist[MAX_VEX];
bool final[MAX_VEX];
int i,j,v,w;
int v0=FindIndex(gb,spot1);
int min;
int number;
for(v=0;v<gb.vexnum;v++)
{
final[v]=false;
dist[v]=GetDistance(gb,v0,v);
for(w=0;w<gb.vexnum;w++)
{
path[v][w]=false;
order[v][w]=0;
}
if(dist[v]<MAX_INT)
{
path[v][v0]=true;
path[v][v]=true;
order[v][v0]=1;
order[v][v0]=2;
}
}
final[v0]=true;dist[v0]=0;
for(i=1;i<gb.vexnum;i++)
{
min=MAX_INT;
for(w=0;w<gb.vexnum;w++)
{
if(final[w]!=true&&dist[w]<min)
{
min=dist[w];
v=w;
}
}
final[v]=true;
number=0;
for(w=0;w<gb.vexnum;w++)
{
if(final[w]!=true&&min+GetDistance(gb,v,w)<dist[w])
{
number=0;
dist[w]=min+GetDistance(gb,v,w);
for(j=0;j<gb.vexnum;j++)
{
if(order[w][j]>number)
number=order[w][j];
path[w][j]=path[v][j];
order[w][j]=order[v][j];
}
path[w][w]=true;
order[w][w]=number+1;
}
}
}
printf("%s到%s的最短路径是:",gb.vextices[v0].data.szName,spot2);
i=FindIndex(gb,spot2);
number=0;
for(j=0;j<gb.vexnum;j++)
if(order[i][j]>number)
number=order[i][j];
for(int k=1;k<=number;k++)
for(j=0;j<gb.vexnum;j++)
if(order[i][j]==k)
printf("%s ",gb.vextices[j].data.szName);
printf("\n");
}
void main(void)
{
net gb;
char sz[32];
char vs1[32],vs2[32];
printf("---------------NET-----------------\n");
printf("Build!\n");
Build_Net(gb);
getchar();
printf("DFS\n");
printf("start:");
scanf("%s",sz);
DFSTravel(gb,sz);
printf("BFS\n");
printf("start:");
scanf("%s",sz);
BFSTravel(gb,sz);
printf("Prime!\n");
printf("start:");
scanf("%s",sz);
getchar();
MST_Prime(gb,sz);
getchar();
printf("DIJ!\n");
printf("start and End:");
scanf("%s%s",vs1,vs2);
getchar();
ShortPathDIJ(gb,vs1,vs2);
}
评论0