频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
算法学习 - 图的拓扑排序
2015-03-13 08:35:50         来源:累了就歇一会  
收藏   我要投稿

拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序,使得如果存在一条从Vi到Vj的路径,那么排序中Vj一定出现在Vi后面。

所以假如图里面有圈就不可能完成排序的。

第一种方法

一种简单的办法就是在排序算法中,先找到任意一个没有入边的顶点,然后显示该顶点,并把它和它的边一起从图里删掉。依次类推到最后。

入度(indegree): 顶点v的入度为,所有指向顶点v的变数(u, v)。
出度(outdegree): 顶点v的出度为,顶点v所发出的边数(v, u)。

下面写下这种方法的伪代码,因为这个的时间复杂度O(|V|^2) 所以效率其实并不好,第二种方法给出真实代码。

void Topsort ( Graph G )
{
    int Counter;
    Vertex V, W;
    for ( Counter = 0; Counter < NumVertex; Counter++ )
    {
        V = FindNewVertexOfIndegreeZero();
        if ( V == NotVertex )
        {
            Error("Graph has a cycle");
            break;
        }
        TopNum[V] = Counter;
        for each W adjacent to V
            Indegree[W]--;
    }
}

此伪代码来源:《Data Structures and Algorithm Analysis in C》

第二种方法

这种办法其实也很好理解,就是说在我们上面哪种方法的时候我们发现,其实每次第一次我们把所有入度为0的点加入到队列中后,每次产生的新的入度为0的点,肯定是因为当前遍历的点所造成的,所以我们记录下每次点入度的更新,当为0就加入到队列中就可以了。

//
//  main.cpp
//  TopologySort
//
//  Created by Alps on 15/3/3.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 
#include 
using namespace std;

struct Node{
    int val;
    int length;
    Node* next;
    Node(): val(0), length(0), next(NULL) {}
};

typedef Node* Graph;

int *degree;

Graph CreateG (Graph G){
    int num;
    scanf("%d", &num); // input the number of the vertex
    G = (Graph)malloc(sizeof(struct Node) * (num+1)); //malloc memory for graph
    G[0].length = num; //save the graph vertex number
    degree = (int *)malloc((num+1) * sizeof(int));
    memset(degree, 0, num*sizeof(int));
    for (int i = 1; i <= num; i++) {
        G[i].val = i;
        G[i].next = NULL;
        int outdegree = 0;
        scanf("%d", &outdegree);
        for (int j = 0; j < outdegree; j++) {
            Node* temp = (Node*)malloc(sizeof(struct Node));
            scanf("%d %d",&(temp->val), &(temp->length));
            temp->next = G[i].next;
            G[i].next = temp;
            degree[temp->val] += 1;
        }
    }
    return G;
}

void PrintG (Graph G){
//    int length = sizeof(G)/sizeof(struct Node);
    int length = G[0].length;
    Node * temp;
    for (int i = 1; i <= length; i++) {
        temp = &G[i];
        printf("Node: %d ",temp->val);
        while (temp->next) {
            printf("-> %d(%d)",temp->next->val, temp->next->length);
            temp = temp->next;
        }
        printf("\n");
    }
}

int* TopologySort (Graph G){
    queue Q;
    int counter = 0;
    int length = G[0].length;
    int *TopNum = (int*)malloc((length+1) * sizeof(int));
    for (int i = 1; i <= length; i++) {
        if (degree[i] == 0) {
            Q.push(G[i]);
        }
    }
    while (!Q.empty()) {
        Node V = Q.front();
        TopNum[V.val] = ++counter;
        Node * temp = &V;
        while (temp->next) {
            temp = temp->next;
            degree[temp->val] -= 1;
            if (degree[temp->val] == 0) {
                Q.push(G[temp->val]);
            }
        }
        Q.pop();
    }

    if (length != counter) {
        return NULL;
    }

    return TopNum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    Graph G;
    G = CreateG(G);

    PrintG(G);

    int *TopNum = TopologySort(G);
    for (int i = 1;TopNum != NULL && i <= G[0].length; i++) {
        printf("%d ",TopNum[i]);
    }
//    std::cout << "Hello, World!\n";
    return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 算法
上一篇:算法学习 - 图的创建和打印
下一篇:归并排序及统计数组逆序对
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站