栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

数据结构拓扑排序C语言有c++

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构拓扑排序C语言有c++

#include 

using namespace std;
#include
#include
#define MVNum 100
#define OK 1
#define ERROR 0
int indegree[100];
int d[100];      //定义拓扑排序数组
typedef struct edge
{
    int adjvex;
    struct edge*nextarc;
}edge;
typedef struct graph
{
    char data;
    edge*firstarc;
}graph,graphlist[100];
typedef struct graphadj{
    int numvex,numarc;
    graphlist adjlist;
}graphadj;
void creategraph(graphadj*g);
void printfgraph(graphadj*g);
void find(graphadj*g,int indegree[]);
void toposort(graphadj*g);
int main()
{
    graphadj*g;
    g=(graphadj*)malloc(sizeof(graphadj));
    creategraph(g);
    printfgraph(g);
    toposort(g);
}
void find(graphadj*g,int indegree[])
{
    for(int i=0;inumvex;i++)
    {
        indegree[i]=0;
    }
    for(int i=0;inumvex;i++)
    {
        edge*p;
        p=g->adjlist[i].firstarc;
        while(p)
        {
            indegree[p->adjvex]++;
            p=p->nextarc;
        }
    }
}
void toposort(graphadj*g)
{
    find(g,indegree);
    int stack[100];
    int top=-1;
    for(int i=0;inumvex;i++)
    {
        if(indegree[i]==0)
        {
            stack[++top]=i;
        }
    }
    int count=0;
    while(top!=-1)
    {
        int index;
        index=stack[top--];
        cout<adjlist[index].data;
        ++count;
        edge *p;
        for(p=g->adjlist[index].firstarc;p;p=p->nextarc)
        {
            int k=p->adjvex;
            indegree[k]--;
            if(indegree[k]==0)
            {
                stack[++top]=k;
            }

        }
    }
    if(countnumvex)
    {
        cout<<"该图有回路";
        return;
    }
}
void creategraph(graphadj*g)
{
    edge*p;
    int i;
    int vi,vj;
    cout<<"请输入图的顶点树和边数:"<>g->numvex>>g->numarc;
    for(i=0;inumvex;i++)
    {
        cin>>g->adjlist[i].data;
    }
    for(i=0;inumvex;i++)
    {
        g->adjlist[i].firstarc=NULL;
    }
    for(i=0;inumarc;i++)
    {
        cout<<"请输入vi,vj边的顶点"<>vi>>vj;

        p=(edge*)malloc(sizeof(edge));
        p->adjvex=vj;
        p->nextarc=g->adjlist[vi].firstarc;
        g->adjlist[vi].firstarc=p;
    }
}
void printfgraph(graphadj*g)
{
    int i,j,k;
    edge *p;
    cout<<"以下为邻接表的输出:"<numvex;i++)
    {
        cout<adjlist[i].data<<" ";
        p=g->adjlist[i].firstarc;
        while(p)
        {
            cout<adjvex<<" ";
            p=p->nextarc;
        }
        cout< 

可直接测试

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/779835.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号