标题:有向图的拓扑排序
只看楼主
月下
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2008-7-2
 问题点数:0 回复次数:0 
有向图的拓扑排序
下面这段代码
//有向图的拓扑排序
#include <stdio.h>
#include <malloc.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
    int no;
    InfoType info;
} VertexType;
typedef struct
{
    int edges[MAXV][MAXV];
    int n,e;
    VertexType vexs[MAXV];
} MGraph;
//邻接表存储方法
typedef struct ANode
{
    int adjvex;
    struct ANode *nextarc;
    InfoType info;
} ArcNode;
typedef struct
{
    VertexType data;
    int count;
    ArcNode *firstarc;
} VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
    AdjList adjlist;
    int n,e;
} ALGraph;
//将邻接矩阵g转换成邻接表G
void MatToList(MGraph g,ALGraph *G)
{
    int i,j,n=g.n;
    ArcNode *p;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    for(i=0;i<n;i++) G->adjlist[i].firstarc=NULL;
    for(i=0;i<n;i++)
    {
        for(j=n-1;j>=0;j--)
        {
            if(g.edges[i][j]!=INF&&g.edges[i][j]!=0)
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));
                p->adjvex=j;
                p->nextarc=G->adjlist[i].firstarc;
                p->info=g.edges[i][j];
                G->adjlist[i].firstarc=p;
            }   
        }   
    }
    G->n=n;G->e=g.e;   
}     
//拓扑排序算法
void TopSort(ALGraph *G)
{
    int i,j;
    int St[MAXV],top=-1;
    ArcNode *p;
    for(i=0;i<G->n;i++) G->adjlist[i].count=0;
    for(i=0;i<G->n;i++)
    {
        p=G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            G->adjlist[p->adjvex].count++;
            p=p->nextarc;
        }   
    }   
    for(i=0;i<G->n;i++)
    {
        if(G->adjlist[i].count==0)
        {
            top++;
            St[top]=i;
        }   
    }   
    while(top>-1)
    {
        i=St[top];top--;
        printf("%d ",i);
        p=G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            j=p->adjvex;
            G->adjlist[j].count--;
            if(G->adjlist[j].count==0)
            {
                top++;
                St[top]=j;
            }   
            p=p->nextarc;
        }   
    }   
}   
     
//主函数
int main()
{
    int i,j,n;
    MGraph g;
    ALGraph *G;
    printf("请输入有向图的顶点个数:");//6
    while(scanf("%d",&n)!=EOF)
    {
        printf("请输入有向图的邻接矩阵:\n");
        /*
        0 1 32767 32767 32767 32767
        32767 0 1 32767 32767 32767
        32767 32767 0 1 32767 32767
        32767 32767 32767 0 32767 32767
        32767 1 32767 32767 0 1
        32767 32767 32767 1 32767 0
        */
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&g.edges[i][j]);
            }
        }
        g.n=n;
        MatToList(g,G);
        printf("有向图的拓扑排序序列为:");
        TopSort(G);
        printf("\n请输入有向图的顶点个数:");
    }   
    return 0;
}        
运行之后就不知道怎么搞了啊。要向老师答辩.有谁能帮忙分析下怎么解释和运用这个程序啊!谢谢啦
搜索更多相关主题的帖子: 有向图 拓扑 int struct typedef 
2008-07-02 17:16



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-222292-1-1.html




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

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