#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define MAX_VERTEX_NUM 20
typedef char Vertex_Type[5];
typedef struct Arc_Node
{
    int adjvex;    //弧所指向的顶点的位置
    struct Arc_Node *nextarc;
}Arc_Node;
typedef struct Vertex_Node
{
    Vertex_Type data;
    int indegree;
    Arc_Node *firstarc;
}Vertex_Node;
typedef struct
{
    Vertex_Node vexs[MAX_VERTEX_NUM];
    //Vertex_Type *vexs;
    int vexnum;
    int arcnum;
}ALGraph;
/*struct Vertex
{
    Vertex_Type data;    //结点的数据域
    Arc_Node *adj;        //边链表的首指针
}*/
typedef struct    //栈的定义
{
    int *base;
    int *top;
    int stacksize;
}SqStack;
/////////////栈的操作函数定义
void InitStack(SqStack *S)
{
    S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
    if(!S->base)
        exit(0);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *S,int e)
//插入元素e为新的栈顶元素        
{
    if(S->top-S->base>=S->stacksize)
    {
        S->base=(int*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));
        if(!S->base)
            exit(0);
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
    }
    *(S->top)++=e;
}
void Pop(SqStack *S,int *e)
//若栈不空，则删除S的栈顶元素，用e返回其值
{   
    if(S->top==S->base)
        exit(0);
    *e=*--(S->top);
}
int StackEmpty(SqStack *S)
{
    if(S->base==S->top)
        return (1);
    else
        return (0);
}
void Init_ALGraph(ALGraph &G)
{
    cout<<"输入图的顶点数:";
    cin>>G.vexnum;
    cout<<"输入图的边数:";
    cin>>G.arcnum;
    int i;
    cout<<"输入定点值:";
    for(i=0;i<G.vexnum;++i)
    {
        cin>>G.vexs[i].data;
        G.vexs[i].firstarc=NULL;
    }
}
//获取定点在向量中的位置 如果出错就终止运行
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
    int i;
    for(i=0;i<G.vexnum;++i)
   
        if(strcmp(v,G.vexs[i].data)==0)
            return i;
        exit(0);
}
void Greate_ALGraph(ALGraph &G)
{
    Init_ALGraph(G);
    Vertex_Type v1,v2;
    int m,n,i;
    cout<<"输入图形的边数:";
    for(i=0;i<G.arcnum;++i)                //输入并构造邻接表
    {
        cin>>v1>>v2;
        m=Get_Vertex_Location(G,v1);
        n=Get_Vertex_Location(G,v2);

        Arc_Node *p1;
        p1=(Arc_Node*)malloc(sizeof(Arc_Node));
        p1->adjvex=n;                    //对弧点赋邻接点位置信息
        p1->nextarc=G.vexs[m].firstarc;
        G.vexs[m].firstarc=p1;
    }
}

int TopSort(ALGraph G)
{
    SqStack S;
    int k,i;
    int vexnum;
    int*indegree=new int[vexnum];
    //int v;
    Arc_Node *p;
     //int FindInDegree(ALGraph &G,int *indegree);    //对各顶点求入度indegree[0...vexnum-1]
    for(i=0;i<vexnum;i++)
    {
        indegree[i]=0;         //初始化入度统计数组
    }
/*首先遍历结点数组找出每个结点的入度*/
    for(i=0;i<vexnum;i++)
    {
        Arc_Node *ptr=vexs[i].data;    //取得每个边链表的第一个元素结点
        while(ptr!=NULL)    //遍历每个边链表的结点   
        {
            int p=ptr->adjvex;    //统计图中每个顶点入度数
            indegree[p]++;
            ptr=ptr->nextarc;
        }
    }
    InitStack(&S);
    for(i=0;i<G.vexnum;++i)        //建零入度顶点栈S
    {
        if(indegree[i]==0)    //入度为零者进栈
            Push(&S,i);   
        int count=0;        //对输出的顶点计数
        while(!StackEmpty(&S))
        {
            Pop(&S,&i);
            cout<<i<<G.vexs[i].data;    //输出i号顶点并计数
            ++count;
            for(p=G.vexs[i].firstarc;p;p=p->nextarc)
            {
                k=p->adjvex;        
                if(!(--indegree[k]))    //对i号顶点的每个邻接点的入度减1
                    Push(&S,k);            //若入度减为零则入栈
            }
        }
        if(count<G.vexnum)        //该有向图有回路
            return 0;
        else
            return 1;
    }
}
void Print_ALGraph(ALGraph G)
{
    int i;
    Arc_Node *p=NULL;
    for(i=0;i<G.vexnum;++i)
    {
         //p=G.vexs[i].indegree[i];
        p=G.vexs[i].firstarc;
        while(p)
        {
            cout<<G.vexs[i].data;
            cout<<G.vexs[p->adjvex].data<<endl;
            p=p->nextarc;
        }
    }
}
int main()
{
    ALGraph G;
    Greate_ALGraph(G);
    cout<<"该有向图的拓扑排序为:";
    TopSort(G);
    Print_ALGraph(G);
    return 0;
}

顶

嘿嘿，这个程序还未实现，求指点

嘿嘿，这个程序还未实现，求指点