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

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

2个回答

有向图可以拓扑排序的条件是:图中没有环。
具体方法:
⑴ 从图中选择一个入度为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;
}
sinat_31765599
吊带裤小熊 谢谢。这样输出的结果是拓扑排序的结果,如果我想要输出的是每次的源点,该做怎样的处理呢?
4 年多之前 回复
sinat_31765599
吊带裤小熊 谢谢。
4 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐