#include
#include
#define Max 20 //最大顶点数
//顺序存储方式使用的结构体定义
typedef struct vexType
{
char data;
int indegree;
}Vex;
typedef struct Graph
{
int vexnum; //顶点数量
int arcnum; //边数
Vex vex_array[Max]; //存放顶点的数组
int arc_array[Max][Max]; //存放邻接矩阵的二维数组}Graph; //图的定义
//链式存储使用的结构体定义
typedef struct arcType
{
char vex1,vex2; //边所依附的两点
int arcVal; //边的权值
}Arc; //边的定义
typedef struct LinkType
{
int index; //在顶点表的下标
struct LinkType *nextarc; //指向下一个顶点结点
}LinkNode; //边表定义
typedef struct vexNode
{
char data;
int add; //在顶点数组的下表位置
LinkNode *firstarc; //指向边表的第一个结点
int indegree; //入度
}VexNode; //顶点边定义
typedef struct LGraph
{
VexNode vex_array[Max]; //顶点数组
int vexnum; //图中顶点数
}LGraph;
/*函数功能：图的创建
入口参数：图G
返回值：无
*/
void Creat_G(Graph *G)
{
char v;
int i=0;
int j=0;
G->vexnum=0;
printf("输入说明。。。有权值请输入权值，无权值请输入1，无边请输入0\n");
printf("\n请输入所有顶点(不超过20个，按‘#’结束输入)：\n");
do{
printf("输入第%d 个顶点：",G->vexnum+1);
scanf(" %c",&v);
G->vex_array[G->vexnum].data = v;
G->vexnum++;
}while(v!='#');
G->vexnum--;
printf("输入邻接矩阵（%d * %d）：",G->vexnum,G->vexnum);
for(i=0; ivexnum; i++)
{
printf("输入%c 到以下各点的权值：\n",G->vex_array[i].data);
for(j=0; jvexnum; j++)
{
printf("<%c, %c>: ",G->vex_array[i].data,G->vex_array[j].data);
scanf("%d",&G->arc_array[i][j]);
}
}
printf("\n构建图的顶点为：\n");
for(i=0; ivexnum; i++)
{
printf("%c ",G->vex_array[i].data);
}
printf("\n构建图的邻接矩阵为：\n");
for(i=0; ivexnum; i++)
{
for(j=0; jvexnum; j++)
{
printf("%d ",G->arc_array[i][j]);
}
printf("\n");
}
}
/*函数功能：统计各点的入度
入口参数：指向图的指针*G
返回值：无
*/
void Count_indegree(Graph *G)
{
int i;
int j;
for(j=0; jvexnum; j++)
{
G->vex_array[j].indegree =0;
for(i=0; ivexnum; i++)
{
if(G->arc_array[i][j]!=0)
G->vex_array[j].indegree++;
}
}
}
/*函数功能：对邻接矩阵进行拓扑排序
入口参数：指向图的指针*G
返回值：无
*/
void Topol_sort(Graph *G)
{
int i,j;
char topo[Max]; //存放拓扑排序的结果
int count=0; //记录topo[]中的元素个数，便于与vexnum比较，判断是有环图还是无环图
char stack[Max]; //存放indegree=0的顶点所在vex_array[]中的下标
int top=0; //栈的指针
int bool=1; //弹栈的标准
int no; //接收stack[]栈中弹出的顶点下标
for(i=0; ivexnum; i++)
{
if(G->vex_array[i].indegree==0)
{
stack[top] = i;
top++;
}
}
do{
if(top==-1)
bool=0;
else
{
top--;
no = stack[top];
topo[count] = G->vex_array[no].data;
count++;
for(j=0; jvexnum; j++)
{
if(G->arc_array[i][j]!=0)
{
G->vex_array[j].indegree--;
if(G->vex_array[j].indegree==0)
{
