用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

拓扑排序算法

2012-09-23 作者: 神马举报

[c++]代码库

#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //图的最大顶点数
#define MAX 30       //栈的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{
    int adjvex;              //该弧所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
} ArcNode;      //弧结点
typedef struct
{
    int indegree[MAX_VERTEX_NUM]; //存放各顶点的入度
    ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针
    int vexnum,arcnum;                //图的当前顶点和弧数
} Graph;
typedef struct    //定义堆栈结构
{
    int elem[MAX];   //栈区
    int top;         //栈顶指针
} Stack;
void CreateGraph ( Graph & ); //生成图的邻接表
BOOL TopologicalSort ( Graph );  //进行拓扑排序
void FindInDegree ( Graph& ); //求图各顶点的入度
void Initial ( Stack & );  //初始化一个堆栈
BOOL Push ( Stack &,int ); //将一个元素入栈
BOOL Pop ( Stack&,int & ); //将一个元素出栈
BOOL StackEmpty ( Stack ); //判断堆栈是否为空
void main()
{
    Graph G;  //采用邻接表结构的图
    char j='y';
    BOOL temp;
    textbackground ( 3 );  //设定屏幕颜色
    textcolor ( 15 );
    clrscr();
//------------------程序解说----------------------------
    printf ( "本程序将演示怎样对图进行拓扑排序.\n" );
    printf ( "首先输入图的顶点数和弧数.\n格式:顶点数,弧数;例如:4,4\n" );
    printf ( "再输入各条弧(弧尾,弧头).\n例如:\n1,2\n1,3\n2,4\n4,3\n" );
    printf ( "程序将会生成一个图并对它进行拓扑排序.\n" );
    printf ( "拓扑排序结果:1->2->4->3\n" );
//------------------------------------------------------
    while ( j!='N'&&j!='n' )
    {
        CreateGraph ( G );       //生成邻接表结构的图
        temp=TopologicalSort ( G ); //进行拓扑排序
        if ( temp==False ) printf ( "该图有回路!\n" );
        //若返回为False,表明该图存在有环路
        else printf ( "该图没有回路!\n" );
        printf ( "拓扑排序完毕,继续进行吗?(Y/N)" );
        scanf ( " %c",&j );
    }
}
 
void CreateGraph ( Graph &G )
{//构造邻接表结构的图G
    int i;
    int start,end;
    ArcNode *s;
    printf ( "请输入图的顶点数和弧数:" );
    scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和弧数
    for ( i=1; i<=G.vexnum; i++ ) G.AdjList[i]=NULL; //初始化指针数组
    printf ( "请输入各弧, 格式:弧尾,弧头\n" );
    for ( i=1; i<=G.arcnum; i++ )
    {
        scanf ( "%d,%d",&start,&end ); //输入弧的起点和终点
        s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) ); //生成一个弧结点
        s->nextarc=G.AdjList[start]; //插入到邻接表中
        s->adjvex=end;
        G.AdjList[start]=s;
    }
}
BOOL TopologicalSort ( Graph G )
{//对图G进行拓扑排序,若G存在回路,返回False,否则返回True
    int i,k;
    int count; //计数器
    ArcNode* p;
    Stack S;
    FindInDegree ( G ); //求出图中各顶点的入度
    Initial ( S );   //堆栈初始化,存放入度为零的顶点
    for ( i=1; i<=G.vexnum; i++ )
        if ( !G.indegree[i] ) Push ( S,i ); //入度为零的顶点入栈
    count=0;     //对输出顶点记数
    printf ( "拓扑排序:" );
    while ( !StackEmpty ( S ) )
    {
        Pop ( S,i );  //输出i号顶点并记数
        printf ( "%d->",i );
        count++;
        for ( p=G.AdjList[i]; p; p=p->nextarc )
        {
            k=p->adjvex;       //对i号顶点的每个邻接顶点的入度减一
            if ( ! ( --G.indegree[k] ) ) Push ( S,k ); //若入度为零,入栈
        }
    }
    printf ( "\b\b  \n" );
    if ( count<G.vexnum ) return False; //如输出顶点数少于图中顶点数,则该图有回路
    else return True;
}
void FindInDegree ( Graph &G )
{//求出图G的各顶点的入度,存放在G.indegree[1..G.vexnum]中
    int i;
    ArcNode* p;
    for ( i=1; i<=G.vexnum; i++ )
        G.indegree[i]=0;
    for ( i=1; i<=G.vexnum; i++ )
    {
        for ( p=G.AdjList[i]; p; p=p->nextarc )
            G.indegree[p->adjvex]++;  //弧头顶点的入度加一
    }
}
void Initial ( Stack &S )
{
    S.top=-1;   //栈顶指针初始化为-1
}
 
BOOL Push ( Stack &S,int ch )
{//将元素ch入栈,成功返回True,失败返回False
    if ( S.top>=MAX-1 ) return False;//判断是否栈满
    else
    {
        S.top++;               //栈顶指针top加一
        S.elem[S.top]=ch;      //入栈
        return True;
    }
}
 
BOOL Pop ( Stack &S,int &ch )
{//将栈顶元素出栈,成功返回True,并用ch返回该元素值,失败返回False
    if ( S.top<=-1 ) return False;//判断是否栈空
    else
    {
        S.top--;                                //栈顶指针减一
        ch=S.elem[S.top+1];
        return True;
    }
}
BOOL StackEmpty ( Stack S )
{//判断堆栈是否已空,若空返回True,不空返回False
    if ( S.top<=-1 ) return True;
    else return False;
}


网友评论    (发表评论)

共2 条评论 1/1页

发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...