| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6481 人关注过本帖
标题:拓扑排序 C语言代码
只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
结帖率:94.44%
收藏
已结贴  问题点数:100 回复次数:12 
拓扑排序 C语言代码
求用C语言写的拓扑排序代码(注意:要用C语言写) 要求最好简单易懂,网上找来的C++代码就别发了 谢谢合作
搜索更多相关主题的帖子: C语言 拓扑 代码 
2010-05-29 16:12
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
来个人回答下啊
2010-05-29 16:57
冥卫
Rank: 8Rank: 8
来 自:深山老林
等 级:蝙蝠侠
帖 子:280
专家分:772
注 册:2010-4-20
收藏
得分:0 
LZ是什么意思啊?说清楚
2010-05-29 17:34
kingsroot
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:284
专家分:1159
注 册:2010-3-28
收藏
得分:0 
意思是不是把图排序的拉成一个线性结构
2010-05-29 22:38
xichong
Rank: 7Rank: 7Rank: 7
来 自:四川南充
等 级:黑侠
威 望:2
帖 子:146
专家分:582
注 册:2009-6-10
收藏
得分:100 
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT  10

#define MAX 20
typedef int VertexType;
typedef struct ArcNode//表结点
{
    int adjvex;//弧所指向的顶点的位置
    struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//头结点
{
    VertexType data;//顶点信息
    ArcNode *firstarc;//指向第一条依附该弧的顶点指针
}VNode,*AdjList;
typedef struct
{
    AdjList vertices;
    int vexnum;//图的**当前**顶点数
}ALGraph;
typedef struct//栈的定义
{
    int *base;
    int *top;
    int stacksize;
}SqStack;
/////////栈的操作函数定义
void initialStack(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)
{
    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)
{
    if(s->top==s->base) exit(0);
    *e=*--(s->top);
}
void GetTop(SqStack *s,int *e)
{
    if(s->top==s->base) exit(0);
    *e=*(s->top-1);
}
int StackEmpty(SqStack *s)
{
    if(s->base==s->top)
        return(1);
    else
        return(0);
}
/////创建图的邻接矩阵
void CreatAjacentMatrix(int *array,int n)//创建邻接矩矩阵(n行n列)
{
    int a;
    int i,j,flag=0;
    printf("请输入一个%d行%d列的关于图的邻接矩阵:\n",n,n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&a);
            *(array+i*n+j)=a;
        }   
}
void PrintAjacentMatrix(int *array,int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            printf("%5d ",*(array+i*n+j));
        printf("\n");
    }
}

////将邻接矩阵导出为图的邻接表形式
void CreatAdjList(int *array,int n,ALGraph *G)
{
    int i,j;
    ArcNode *p;//表结点
    G->vexnum=n;//初始化顶点数
    G->vertices=(VNode *)malloc((n+1)*sizeof(VNode));//头结点数组,开辟n+1长度的数组空间
    for(i=1;i<=n;i++)//初始化头结点数组
    {
        G->vertices[i].data=i;
        G->vertices[i].firstarc=NULL;
    }
    //////////
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(*(array+i*n+j)==1)
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));
                p->adjvex=j+1;
                p->nextarc=G->vertices[i+1].firstarc;
                G->vertices[i+1].firstarc=p;
            }
        }
}

void FindInDegree(ALGraph G,int *indegree)//对顶点求入度
{
    int i,j;
    ArcNode *p;
    for(i=1;i<=G.vexnum;i++)
        indegree[i]=0;//indispensable
    for(i=1;i<=G.vexnum;i++)//对每个结点跑完整个邻接表
        for(j=1;j<=G.vexnum;j++)
            for(p=G.vertices[j].firstarc;p;p=p->nextarc)
                if(G.vertices[i].data==p->adjvex)//==
                    indegree[i]++;
}

/////////拓扑排序算法
int TopologicalSort(ALGraph G)
{
    //有向图采用邻接表存储结构
    //若G无回路,则flag=0,输出G的顶点的一个拓扑序列,否则给出该有向图有回路的提示.
    int i,count,k;
    int *indegree=(int *)malloc((G.vexnum+1)*sizeof(int));
    SqStack S;
    ArcNode *p;
    FindInDegree(G,indegree);//对顶点求入度indegree[G.vexnum]
    initialStack(&S);//为避免重复检测入度为0的顶点,可另设一栈暂存放所有入度为0的顶点
    for(i=1;i<=G.vexnum;i++)
        if(!indegree[i])
            Push(&S,i);//0入度点进栈
    count=0;//对输出顶点计数,作为判断是否有回路的根据
    while(!StackEmpty(&S))
    {
        Pop(&S,&i);
        printf("%d  ",i);//输出i号顶点并计数
        count++;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)
        {
            k=p->adjvex;//表结点的数据域,即对i号顶点的每个邻接点的入度减1
            if(!(--indegree[k]))//若入度减少为0,则入栈
                Push(&S,k);
        }
    }
    if(count<G.vexnum)//该有向图有回路
        return 0;
    else
        return 1;
}
void main()
{
    int n;
    int *A;
    ALGraph G;
    printf("请输入你想创建的邻接矩矩阵的行列数(即顶点数):\n");
    scanf("%d",&n);
    A=(int *)malloc(n*n*sizeof(int));
    CreatAjacentMatrix(A,n);
    printf("请输出图的邻接矩阵A:\n");
    PrintAjacentMatrix(A,n);
    CreatAdjList(A,n,&G);
    printf("该有向图的一个拓扑排序结果如下所示:\n");
    if(TopologicalSort(G))
        printf("\n");
    else
        printf("该有向图有回路!\n");
}

运行结果如下:
图片附件: 游客没有浏览图片的权限,请 登录注册
2010-05-29 22:42
q3286446
Rank: 1
来 自:中国
等 级:新手上路
帖 子:31
专家分:6
注 册:2010-5-24
收藏
得分:0 
牛~! 我也得努力加油了~~~~~
2010-05-30 01:50
ouyangouyang
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:273
专家分:579
注 册:2009-10-8
收藏
得分:0 
5楼讲讲你的程序的意思,是最小生成树吗?

多少恨, 昨夜梦魂中。 还似旧时游上苑, 车如流水马如龙; 花月正春风!
2010-05-30 18:27
南国利剑
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:29
帖 子:1165
专家分:3536
注 册:2010-4-12
收藏
得分:0 
回复 5楼 xichong
不错,不错。
佩服!

南国利剑
2010-06-01 01:27
bingshiwuyu
Rank: 1
等 级:新手上路
帖 子:42
专家分:0
注 册:2009-5-30
收藏
得分:0 
.
2010-06-01 12:43
ouyangouyang
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:273
专家分:579
注 册:2009-10-8
收藏
得分:0 
#include"stdio.h"
#include"stdlib.h"
int QQ(int *A ,int P,int R )
{
    int I;
    for (I=0;I<P;I++)
        {if (A[I]==R) return 1;}
    return 0;
}
main()
{
    int x,i,j,b,a[10][10],q,m[10],p=0;
    printf("请输入你想创建的邻接矩矩阵行列数(即顶点数):\n");
    scanf("%d",&x);
    printf("请输入一个%d行%d列的关于图的邻接矩阵:\n",x,x);
    for (i=0;i<x;i++)
        for (j=0;j<x;j++)
            scanf("%d",&a[i][j]);
    printf("请输出图的邻接矩阵\n");
    for (i=0;i<x;i++)
    {
        for (j=0;j<x;j++)
            printf("%5d",a[i][j]);
        printf("\n");
    }
     for (q=0;q<x;q++)
        for (i=0;i<x;i++)
        {
            for (j=0,b=0;j<x;j++)
            {
                if (QQ(m,p,i)||QQ(m,p,j)) continue;
                b+=a[j][i];

            }

            if((b==0)&&(!QQ(m,p,i))){m[p]=i;p++;}
        }
    printf("\n");
    printf("该有向图的一个拓扑排序如下所示:\n");
    for (i=0;i<p;i++)
        printf("%5d",m[i]);
    system("pause");
}
闭门思过,看了几天书终于写了出来,各位见笑了
图片附件: 游客没有浏览图片的权限,请 登录注册


[ 本帖最后由 ouyangouyang 于 2010-6-2 15:13 编辑 ]

多少恨, 昨夜梦魂中。 还似旧时游上苑, 车如流水马如龙; 花月正春风!
2010-06-02 15:11
快速回复:拓扑排序 C语言代码
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031356 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved