Topsort.cpp
int indegree[MAXVEX];
int flag[MAXVEX]={0};
void GetIndegree(Graph *G)
{
int i,j;
for(i=0;i<G->vexnum;i++)
indegree[i]=0;
for(i=0;i<G->vexnum;i++)
{
for(j=0;j<G->vexnum;j++)
{
if(G->arcs[j][i]==1) indegree[i]++;
}
}
}
void DeleteRelated(int v,Graph *G)//删除与顶点i有关的弧
{
int i;
for(i=0;i<G->vexnum;i++)
G->arcs[v][i]=0;
}
void Topsort(Graph *G)
{
int i,j;
int count;//数flag的个数,即没有排的顶点个数
if(G->kind>1){printf("Graph have no derection, cannot topsort\n");return;}
GetIndegree(G);//初始化入度数组
for(i=0;i<G->vexnum;i++)//找到入度为零的顶点,进行操作
{
if(indegree[i]==0&&flag[i]==0)
{
printf("%s\t",G->vexs[i]);
flag[i]=1;
DeleteRelated(i,G);
break;
}
}
for(count=0,j=0;j<G->vexnum;j++)//找到没有排序的个数count
{
if(flag[j]==0)count++;
}
if(i==G->vexnum)//如果找不到入度为零的顶点
if(count==0){printf("\n");return;}
else {printf("Graph have a cycle, cannot topsort\n");return;}
Topsort(G);
}
Dijkslra.cpp
void getdist(int dist[MAXVEX][MAXVEX],Graph*G)//图的距离信息收录
{
int i,j;
for(i=0;i
for(j=0;j
{
dist[i][j]=G->arcs[i][j];
if(dist[i][j]==0)dist[i][j]=INFINITY;
}
}
void Dijkslra(VertexType x,VertexType y,Graph*G)
{
int distance[MAXVEX]={INFINITY};
int pre[MAXVEX];//记录前一个的下标
int dist[MAXVEX][MAXVEX]={INFINITY};
int s[MAXVEX]={0};//集合s
int start,end;//两个点的数组下标
int i;int j;int k;
int temp;
int mindistance=INFINITY;
int minmark;
int no_zero_flag=0;
int remember;
int path[MAXVEX];
start=getmark(x,G);
end=getmark(y,G);
temp=start;
for(i=0;i<G->vexnum;i++)//赋初值
{
distance[i]=INFINITY;
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);//初始化全部距离信息资料
for(i=0;i<G->vexnum;i++)
{
pre[i]=temp;//路径初始化
}
distance[start]=0;
while(no_zero_flag==0)//这次困在了达不到的情况
{
remember=temp;
s[temp]=1;//printf("%d",temp);
//////////////////////////////////////////
for(i=0;i<G->vexnum;i++)
{
if(distance[temp]+dist[temp][i] < distance[i])
{
distance[i]=distance[temp]+dist[temp][i];//求全部点到源点的距离distance[]
pre[i]=temp;
//printf("%d*",distance[i]);
}
}
mindistance=INFINITY;
for(i=0;i<G->vexnum;i++)
{
if(s[i]==0&&distance[i]<mindistance)//所有distance里找最小的
{
mindistance=distance[i];
minmark=i;
}
}
/////////////////////////////////////////////////////////
temp=minmark;
no_zero_flag=1;
for(i=0;i<G->vexnum;i++)//判断是不是全零
{
if(s[i]==0) no_zero_flag=0;
}
/////////////////////
if(temp==remember)break;//这种情况说明有达不到的顶点
}
/////////////////////输出部分///////////////////////
if(distance[end]>=INFINITY)
{
printf("达不到顶点%s\n",G->vexs[end]);
return;
}
printf("距离:\t%d\n",distance[end]);
i=j=k=0;
i=end;
while(i!=start)
{
path[j++]=i;
i=pre[i];
}
path[j]=start;
printf("路径:\t");
for(k=j;k>=0;k--)
{
printf("%s",G->vexs[path[k]]);
if(k==0) printf("\n");
else printf("->");
}
}
Kruskal.cpp
int not_a_tree(int m,int n,int record[MAXVEX][MAXVEX],Graph G)
{
int i,j,k;
int flag;
int tree[MAXVEX][MAXVEX]={0};
for(i=0;i
{
k=0;
for(j=0;j
{
if(record[i][j]==1)
tree[i][k++]=j;
}
}
for(i=0;i
{
flag=0;
for(j=0;j
{
if(tree[i][j]==m||tree[i][j]==n)
flag++;
}
}
if (flag==2) return 0;
else return 1;
}
void Kruskal(Graph
{
int dist[MAXVEX][MAXVEX]={INFINITY};
int record[MAXVEX][MAXVEX]={0};
int i,j;
int min_i,min_j;
int mindistance=INFINITY;
int count=0;
if(G->kind<=1) {printf("Graph have direction, cannot kruskal\n");return;}
for(i=0;i<G->vexnum;i++)//赋初值
{
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);
while(count<G->vexnum-1)
{
mindistance=INFINITY;
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
if((i!=j)&&(record[i][j]==0)&¬_a_tree(i,j,record,G)&&(dist[i][j]<mindistance))
{
mindistance=dist[i][j];
min_i=i;min_j=j;
}
}
record[min_i][min_j]=1;
record[min_j][min_i]=1;
count=0;
for(i=0;i<G->vexnum;i++)
{
for(j=0;j<i;j++)
{
if(record[i][j]==1) count++;
//printf("%d\t",count);
}
}
}
/////////输出//////////////////
printf("kruskal最小生成树:\n");
for(i=0;i<G->vexnum;i++)
for(j=0;j<i;j++)
if(record[i][j]==1)
printf("%s-%s\t",G->vexs[i],G->vexs[j]);
printf("\n");
}
Prim.cpp
void Prim(Graph*G)
{
int distance[MAXVEX]={INFINITY};
int pre[MAXVEX];//记录前一个的下标
int dist[MAXVEX][MAXVEX]={INFINITY};
int s[MAXVEX]={0};//集合s
int start=0;//两个点的数组下标
int i;int j;
int mindistance=INFINITY;
int minmark;
int zeroflag=0;
if(G->kind<=1) {printf("Graph have direction, cannot prim\n");return;}
for(i=0;i<G->vexnum;i++)//赋初值
{
distance[i]=INFINITY;
for(j=0;j<G->vexnum;j++)
{
dist[i][j]=INFINITY;
if(i==j) dist[i][j]=0;
}
}
getdist(dist,G);//初始化全部距离信息资料
for(i=0;i<G->vexnum;i++)
{
pre[i]=start;//路径初始化
}
while(zeroflag==0)
{
s[start]=1;//printf("%d",start);
distance[start]=0;
//////////////////////////////////////////
for(i=0;i<G->vexnum;i++)
{
if(dist[start][i]< distance[i])
{
distance[i]=dist[start][i];//求全部点到集合中点的距离distance[]
pre[i]=start;
}
}
mindistance=INFINITY;
for(i=0;i<G->vexnum;i++)
{
if(s[i]==0&&distance[i]<mindistance)//所有distance里找最小的
{
mindistance=distance[i];
minmark=i;
}
}
/////////////////////////////////////////////////////////
start=minmark;
zeroflag=1;
for(i=0;i<G->vexnum;i++)//判断是不是全零
{
if(distance[i]!=0) zeroflag=0;
}
}
/////////////////下面是代码的第二部分,输出结果/////////////////////////////////////////
printf("Prim最小生成树:\n");
for(i=0;i<G->vexnum;i++)
{
if(i!=pre[i])
printf("%s-%s\t",G->vexs[pre[i]],G->vexs[i]);
}
printf("\n");
}
Main.cpp
void main()
{
Graph G;
VertexType x,y;
CreateGraph(&G);
PrintGraph(&G);
printf("请输入起点终点(例如a f):");
scanf("%s%s",x,y);
Dijkslra(x,y,&G);
Prim(&G);
Kruskal(&G);
printf("拓扑排序:\n");
Topsort(&G);
}