实现图的拓扑排序
#include "stdlib.h"#include "stdio.h"
#include "string.h"
/*******************************************/
/* 以下为链式队列操作 */
/*******************************************/
/* 定义链式队列类型 */
typedef int ElemType;
typedef struct QNode
{ ElemType data;
struct QNode *next;
} QNode,*QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
} LinkQueue;
/* 1.初始化链式队列 */
void InitQueue(LinkQueue *Q)
{ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if (!(Q->front)) exit(0);
Q->front->next=NULL; }
/* 2.判断空队列 */
int QueueEmpty(LinkQueue Q)
{ if(Q.front==Q.rear)
return 1;
else
return 0; }
/* 3.入队列 */
void EnQueue(LinkQueue *Q, ElemType e)
{ QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(0);
p->data=e; p->next=NULL;
Q->rear->next=p;
Q->rear=p; }
/* 4.出队列 */
void DeQueue(LinkQueue *Q, ElemType *e)
{ QueuePtr p;
if(Q->front!=Q->rear)
{ p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if (Q->rear==p) Q->rear=Q->front;
free(p); }
}
/****************************************************/
/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */
/****************************************************/
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef char VertexType[20]; //顶点信息（名称）
/* 图的类型定义（邻接表存储结构） */
typedef struct ArcNode //链表结点
{ int vexpos; //该弧所指向的顶点在数组中的位置
struct ArcNode *next; //指向当前起点的下一条弧的指针
} ArcNode;
typedef struct VNode //头结点
{ VertexType name; //顶点信息（名称）
int indegree; //顶点入度
ArcNode *firstarc; //指向当前顶点的第一条弧的指针
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{ AdjList vexhead; //邻接表头结点数组
int vexnum,arcnum; //图的顶点数和弧数
} ALGraph;
/* 5.顶点在头结点数组中的定位 */
int LocateVex(ALGraph G,VertexType v)
{ int i;
for(i=0;i<G.vexnum;i++)
if(strcmp(v,G.vexhead[i].name)==0) break;
return i; }
/* 6.建立图（邻接表） */
int CreateGraph(ALGraph *G) //成功建立返回1，不成功则返回0
{ int i,j,k; VertexType v1,v2;ArcNode *newarc;
printf("\n输入有向图顶点数和弧数vexnum,arcnum:"); //输入顶点数和弧数
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); //输入并判断顶点数和弧数是否正确
if((*G).vexnum<0||(*G).arcnum<0||(*G).arcnum>(*G).vexnum*((*G).vexnum-1))
{ printf("\n顶点数或弧数不正确，有向图建立失败！\n");return 0; }
printf("\n输入 %d 个顶点:",(*G).vexnum); //输入顶点名称
for(i=0;i<(*G).vexnum;i++)
{ scanf("%s",(*G).vexhead[i].name); }
printf("\n顶点列表:\n共有%d个顶点: ",(*G).vexnum);//输出顶点名称
for(i=0;i<(*G).vexnum;i++)
printf("%s ",(*G).vexhead[i].name);
for(i=0;i<(*G).vexnum;i++) //邻接表初始化
{ (*G).vexhead[i].firstarc=NULL;
(*G).vexhead[i].indegree=0;}
printf("\n\n输入 %d 条边:vi vj\n",(*G).arcnum); //输入有向图的边
for(k=0;k<(*G).arcnum;k++)
{ scanf("%s%s",v1,v2); //v1是弧的起点（先决条件），v2是弧的终点
i=LocateVex(*G,v1);j=LocateVex(*G,v2); //定位顶点并判断顶点是否存在
if(i>=(*G).vexnum)
{ printf("顶点%s不存在，有向图建立失败！\n",v1);return 0; } if(j>=(*G).vexnum)
{ printf("顶点%s不存在，有向图建立失败！\n",v2);return 0; }
newarc=(ArcNode*)malloc(sizeof(ArcNode)); //前插法建顶点链表
newarc->vexpos=j;
if((*G).vexhead[i].firstarc==NULL)
{ newarc->next=NULL;
(*G).vexhead[i].firstarc=newarc; }
else
{ newarc->next=(*G).vexhead[i].firstarc->next;
(*G).vexhead[i].firstarc->next=newarc; }
(*G).vexhead[j].indegree++; //对应顶点入度计数加1
}
printf("\n有向图建立成功！\n");
return 1;
}
/* 7.按邻接表方式输出有向图 */
void PrintGraph(ALGraph G)
{ int i;ArcNode *p;
printf("\n输出有向图:\n");
for(i=0; i<G.vexnum; i++)
{ printf("\n顶点:%s ",G.vexhead[i].name);
printf("入度:%3d\n",G.vexhead[i].indegree);
p=G.vexhead[i].firstarc;
printf("邻接点:");
while(p!=NULL)
{ printf("%s ",G.vexhead[p->vexpos].name);
p=p->next; }
printf("\n");
}
}
/**********************************/
/* 以下为拓扑排序算法 */
/**********************************/
/* 8.拓扑排序 */
void TopologicalSort(ALGraph G)
{ int i,k,count;ElemType e;ArcNode *p;
LinkQueue Q; /*定义队列*/
InitQueue(&Q);
for(i=0; i<G.vexnum; i++) //入度为0入队列
if(!G.vexhead[i].indegree) EnQueue(&Q,i);
count=0; //初始化变量
printf("\n\n\n其中一个拓扑排序序列为:\n");
while(!QueueEmpty(Q))
{ DeQueue(&Q,&e); //输出入度为零的点
printf("%s ",G.vexhead[e].name);
count++; //对输出的顶点计数
for(p=G.vexhead[e].firstarc;p;p=p->next) //遍历当前点的邻接点
{ k=p->vexpos; //邻接点位置
if(!(--G.vexhead[k].indegree)) //每个邻接点入度减1后若为零则入队列
EnQueue(&Q,k);
}
}
printf("\n");
if(count<G.vexnum)
{ printf("\n该有向图有回路，无法完成拓扑排序！\n"); }
}
/*******************************************/
/* 9.主函数 */
/*******************************************/
void main()
{ ALGraph G; int menu,menu2;
while(1){
printf("\n **********************************************\n");
printf(" * 1.建立有向图并输出 *\n");
printf(" * 2.建立有向图并求一个拓扑排序序列 *\n");
printf(" * 3.清屏 *\n");
printf(" * 4.退出 *\n");
printf(" **********************************************\n");
printf(" 请输入你的选择:");
scanf("%d",&menu);
switch(menu){
case 1:
if(CreateGraph(&G)){system("PAUSE");PrintGraph(G);}//有向图建成则执操作
break;
case 2:
if(CreateGraph(&G)) //有向图建成则执操作
{ system("PAUSE");
PrintGraph(G);system("PAUSE");
TopologicalSort(G); }
break;
case 3:
system("CLS");
break;
case 4:
return;
}
}
}
我觉得好问题，望那位高手可以改进下
