拓扑排序(算法篇)

算法之拓扑排序

拓扑排序

概念：

• 拓扑排序是对有向无圈图的顶点的一种排序。排序不必是唯一的，任何合理的排序都是可以的。
• 具体做法是：先找出任意一个没有入边的顶点v(就是没有其他顶点指向的顶点)，将顶点v放入队列，然后将顶点v和它邻接的边从图中删除(其实就是将顶点v指向的顶点的入边数都-1，这样就可以代表删除边了)，然后用数组topnum来记录该顶点的排序位置。然后重复上述操作。顶点v的入度(indegree)为边(u,v)的条数。并用indegree数组来存储每个顶点的入度值。如果不存在入度为0的顶点，则该图是个有圈图。

代码：

struct listnode{
    int data;
    listnode* next;
};

class graph{
public:
    graph(int n){
        vnum=n;
        an=new listnode[n+1];
        indegree=(int*) malloc(sizeof(int)*(n+1));
        for(int i=0;i<n+1;i++){
            an[i].data=0;
            an[i].next= nullptr;
            indegree[i]=0;
        }
    }
    listnode* createNode(int data){
        auto p=new listnode;
        p->data=data;
        p->next= nullptr;
        return p;
    };
    void insert(int v,int data){
        auto add= createNode(data);
        if(an[v].next== nullptr){
            an[v].next=add;
        } else{
            listnode* p=an[v].next;
            while (p->next!= nullptr){
                p=p->next;
            }
            p->next=add;
        }
        indegree[data]++;
    }
    int findedgenull(){
        for(int i=1;i<=vnum;i++){
            if(indegree[i]==0){
                return i;
            }
        }
        return 0;
    }
    //拓扑排序
    void topsort(){
        queue<int>q;
        int v=findedgenull();
        if(v==0){
            cout<<"该图含有圈"<<endl;
            return;
        }else{
            q.push(v);
            if(q.empty()){
                cout<<"该图含有圈"<<endl;
                return;
            }
            while (!q.empty()){
                int w=q.front();
                cout<<w<<" ";
                q.pop();
                listnode* p=an[w].next;
                while (p!= nullptr){
                    if(--indegree[p->data]==0){
                        q.push(p->data);
                    }
                    p=p->next;
                }
            }
            cout<<endl;
        }
    }
private:
    listnode *an;
    int vnum;
    int *indegree;
};

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms