Topsort.cpp

include”matrix.h”

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

include”matrix.h”

void getdist(int dist[MAXVEX][MAXVEX],Graph*G)//图的距离信息收录
{
int i,j;
for(i=0;ivexnum;i++)
for(j=0;jvexnum;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

include”matrix.h”

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;ivexnum;i++)
{
k=0;
for(j=0;jvexnum;j++)
{
if(record[i][j]==1)
tree[i][k++]=j;
}
}
for(i=0;ivexnum;i++)
{
flag=0;
for(j=0;jvexnum;j++)
{
if(tree[i][j]==m||tree[i][j]==n)
flag++;
}
}
if (flag==2) return 0;
else return 1;
}
void Kruskal(GraphG)
{
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)&&not_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

include”matrix.h”

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

include”matrix.h”

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);

}