vertex.h
#ifndef vertex_h
#define vertex_h
#define OK 1
#define ERR 0
#define MAX 20
#define INF 0xFFFF
typedef int Status;
typedef int VexType;
typedef int EdgeType;
typedef struct EdgeNode
{
int adjvex;
EdgeType weight;
struct EdgeNode *next;
}EdgeNode;
typedef struct VexNode
{
VexType data;
EdgeNode *firstedge;
}VexNode;
typedef struct Graph
{
VexNode v[MAX];
int vexnum;
int edgenum;
}Graph;
#endif
graph.h
#ifndef graph_h
#define graph_h
Status Cgraph(Graph *g);
Status BFSTraverse(Graph *g);
Status DFSTraverse(Graph *g);
Status ShortPath(Graph *g,int v,int P[],int D[]);
Status Floyd(Graph *g,int P[MAX][MAX],int D[MAX][MAX]);
Status Destroy(Graph *g);
#endif
graph.c
#include<stdio.h>
#include<stdlib.h>
#include"vertex.h"
#include"graph.h"
int visited[MAX];
Status Cgraph(Graph *g)
{
int i,j,k;
int weight;
EdgeNode *e;
printf("Input vexnums : ");
scanf("%d",&g->vexnum);
printf("Input edgenums : ");
scanf("%d",&g->edgenum);
for(i=1;i<=g->vexnum;i++)
{
printf("%d th vertex: ",i);
scanf("%d",&(g->v[i].data));
g->v[i].firstedge=NULL;
}
for(k=0;k<g->edgenum;k++)
{
printf("Input edge information(V1~V%d):\n",g->vexnum);
scanf("%d%d",&i,&j);
e=(EdgeNode *)malloc(sizeof(EdgeNode));
if(!e)
{
printf("No enough memory!\n");
return ERR;
}
e->adjvex=j;
printf("Input edge weight: ");
scanf("%d",&weight);
e->weight=weight;
e->next=g->v[i].firstedge;
g->v[i].firstedge=e;
e=(EdgeNode *)malloc(sizeof(EdgeNode));
if(!e)
{
printf("No enough memory!\n");
return ERR;
}
e->adjvex=i;
e->weight=weight;
e->next=g->v[j].firstedge;
g->v[j].firstedge=e;
}
return OK;
}
void DFS(Graph *g,int i)
{
EdgeNode *e;
visited[i]=1;
printf("%4d",g->v[i].data);
e=g->v[i].firstedge;
while(e)
{
if(!visited[e->adjvex])
DFS(g,e->adjvex);
e=e->next;
}
}
Status DFSTraverse(Graph *g)
{
int i;
for(i=1;i<=MAX;i++)
visited[i]=0;
for(i=1;i<=g->vexnum;i++)
if(!visited[i])
DFS(g,i);
return OK;
}
Status BFSTraverse(Graph *g)
{
int Queue[100];
int front=0,rear=0;
int i,j;
EdgeNode *p;
for(i=1;i<=MAX;i++)
visited[i]=0;
for(i=1;i<=g->vexnum;i++)
{
if(!visited[i])
{
visited[i]=1;
printf("%4d",g->v[i].data);
Queue[rear++]=i;
while(front!=rear)
{
j=Queue[front++];
p=g->v[j].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
visited[p->adjvex]=1;
printf("%4d",g->v[p->adjvex].data);
Queue[rear++]=p->adjvex;
}
else
p=p->next;
}//end of inner while
}//end of outer while
}//end of if
}//end of for
return OK;
}
Status ShortPath(Graph *g,int vex,int Path[],int Distance[])//Dijkstra
{
int flag[MAX];
int i,j,k,min;
int dis;
EdgeNode *p=NULL;
for(i=1;i<=g->vexnum;i++)
{
flag[i]=0;
Path[i]=1;
p=g->v[vex].firstedge;
while(p&&(i!=p->adjvex))
p=p->next;
if(p)
Distance[i]=p->weight;
else
Distance[i]=INF;
}
Path[vex]=0;
Distance[vex]=0;
flag[vex]=1;
for(i=2;i<=g->vexnum;i++)
{
min=INF;
for(j=1;j<=g->vexnum;j++)
{
if(!flag[j]&&Distance[j]<min)
{
k=j;
min=Distance[j];
}
}
flag[k]=1;
for(j=1;j<=g->vexnum;j++)
{
p=g->v[k].firstedge;
while(p&&(j!=p->adjvex))
p=p->next;
if(p)
dis=p->weight;
else
dis=INF;
if(!flag[j]&&(min+dis<Distance[j]))
{
Distance[j]=min+dis;
Path[j]=k;
}
}
}
return OK;
}
Status Floyd(Graph *g,int P[MAX][MAX],int D[MAX][MAX])
{
int i,j,k;
EdgeNode *e;
for(i=1;i<=g->vexnum;i++)
for(j=1;j<=g->vexnum;j++)
{
P[i][j]=j;
e=g->v[i].firstedge;
while(e&&(j!=e->adjvex))
e=e->next;
if(e)
D[i][j]=e->weight;
else
D[i][j]=INF;
}
for(k=1;k<=g->vexnum;k++)
for(i=1;i<=g->vexnum;i++)
for(j=1;j<=g->vexnum;j++)
{
if(D[i][j]>D[i][k]+D[k][j])
{
D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[i][k];
}
}
return OK;
}
Status Destroy(Graph *g)
{
int i;
EdgeNode *p=NULL,*q=NULL;
for(i=1;i<=g->vexnum;i++)
{
p=g->v[i].firstedge;
while(p)
{
q=p;
p=p->next;
free(q);
}
g->v[i].firstedge=NULL;
}
return OK;
}
main.c
#include<stdio.h>
#include<stdlib.h>
#include"vertex.h"
#include"graph.h"
void menu(void)
{
printf("\n\n");
printf("***************************************\n");
printf(" Menu Version 1.0\n");
printf("***************************************\n");
printf("1.CreateGraph 2.DFS \n");
printf("3.BFS 4.Dijkstra \n");
printf("5.Floyd 6.Quit \n");
printf("***************************************\n");
printf("Please input your choice : ");
}
int main(int argc,char *argv[])
{
Graph g;
int choice,v;
int i,j,k;
int stack[MAX],top=-1;
int Path[MAX],Distance[MAX];
int P[MAX][MAX],D[MAX][MAX];
while(1)
{
menu();
scanf("%d",&choice);
switch(choice)
{
case 1:
if(Cgraph(&g))
printf("Create success!\n");
else
printf("Create failure!\n");
break;
case 2:
if(DFSTraverse(&g))
printf("\nDFSTraverse success!\n");
else
printf("\nDFSTraverse failure!\n");
break;
case 3:
if(BFSTraverse(&g))
printf("\nBFSTraverse success!\n");
else
printf("\nBFSTraverse failure!\n");
break;
case 4:
printf("Input a vertex : ");
scanf("%d",&v);
if(ShortPath(&g,v,Path,Distance))
{
printf("Calculate success!\n");
for(i=1;i<=g.vexnum;i++)
{
if(i==v)
continue;
printf("The distance from V%d to V%d is %d !\n",v,i,Distance[i]);
printf("Path: V%d",v);
j=Path[i];
while(j!=v)
{
stack[++top]=j;
j=Path[j];
}
while(top>-1)
printf("->V%d",stack[top--]);
printf("->V%d\n",i);
}
}
else
printf("Calculate failure!\n");
break;
case 5:
if(Floyd(&g,P,D))
{
printf("Calculate success!\n");
for(i=1;i<=g.vexnum;i++)
{
for(j=i+1;j<=g.vexnum;j++)
{
printf("V%d-V%d Weight: %d\n",i,j,D[i][j]);
k=P[i][j];
printf("Path: V%d",i);
while(k!=j)
{
printf("->V%d",k);
k=P[k][j];
}
printf("->V%d\n",j);
}
}
}
else
printf("Calcalute failure!\n");
break;
case 6:
Destroy(&g);
exit(0);
break;
default:
printf("Illegal input!\n");
break;
}//end of switch
}//end of while
return 0;
}