吊带裤小熊 2015-12-27 15:12 采纳率: 0%
浏览 1707

拓扑排序(c++)不太懂,有没有大神,求教

最近要写拓扑排序的程序,然后作为一名渣渣,并不是特别懂。课本上说的只说了大致的,我只知道它的思想,却写不出程序来。有没有大神愿意教我(*´ο`*)

  • 写回答

2条回答 默认 最新

  • threenewbee 2015-12-27 15:17
    关注

    有向图可以拓扑排序的条件是:图中没有环。
    具体方法:
    ⑴ 从图中选择一个入度为0的点加入拓扑序列。
    ⑵ 从图中删除该结点以及它的所有出边(即与之相邻点入度减1)。
    反复执行这两个步骤,直到所有结点都已经进入拓扑序列。

     #include <iostream>
    #include <fstream>
    #include <stack>
    using namespace std;
    
    ifstream fin("in.txt");
    #define MAX_VERTEX_NUM 26
    
    stack<int> s;
    
    typedef struct ArcNode{
        int adjvex;
        struct ArcNode *nextarc;
        ArcNode(){nextarc=0;}
    //  InfoType *info;
    }ArcNode;
    
    typedef struct VNode{
        int data;
        ArcNode *firstarc;
        VNode(){firstarc=0;}
    }VNode,AdjList[MAX_VERTEX_NUM];
    
    typedef struct{
        AdjList vertices;
        int vexnum,arcnum;
        int kind;
    }ALGraph;
    
    bool TopologicalSort(ALGraph G,int *indegree)
    {
        int i,k;
        for(i=1;i<G.vexnum+1;i++)
        {
            if(!indegree[i]){s.push(i);}
        }
        int count=0;
        ArcNode *p;
        while(!s.empty())
        {
            i = s.top();
            s.pop();
            cout<<G.vertices[i].data<<"-->";
            count++;
            for(p=G.vertices[i].firstarc;p;p=p->nextarc)
            {
                k = p->adjvex;
                indegree[k]--;
                if(!indegree[k])s.push(k);
            }
        }
        if(count<G.vexnum) return false;
        return true;
    }
    
    
    int main()
    {
        int i;
        ALGraph g;
        cout<<"输入节点数和边数: ";
        fin>>g.vexnum>>g.arcnum;
        for(i=1;i<g.vexnum+1;i++)
            g.vertices[i].data = i;
    
        int b,e;
        ArcNode *p;
        int *indegree = new int[g.vexnum+1];    
        //注意 int *a=new int(n);  申请一个整型变量空间,赋初值为n,并定义一个整型指针a指向该地址空间 
        //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));
        memset(indegree,0,sizeof(int)*(g.vexnum+1));
        cout<<"逐一输入边的顶点对,形如 3 5 "<<endl;
        for(i=1;i<g.arcnum+1;i++)
        {
            cout<<"第"<<i<<"条边:";
            fin>>b>>e;
            p = new ArcNode();
            p->adjvex = e;
            p->nextarc = g.vertices[b].firstarc;
            g.vertices[b].firstarc = p;
            indegree[e]++;
            cout<<endl;
        }
        if(TopologicalSort(g,indegree))cout<<"正常完成!"<<endl;
        else cout<<"该有向图有回路!"<<endl;
        return 0;
    }
    
    评论

报告相同问题?

悬赏问题

  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)