原 初学图论-Kahn拓扑排序算法(Kah

    笔者使用了较为方便的邻接链表表示法。如果使用邻接矩阵,可能需要平方量级的时间消耗。

    为了实现的方便,笔者使用了STL库中的队列结构。当队列为空时终止循环,此时如果仍然有边存在,则说明图中存在环,没有拓扑顺序。

    代码如下:

/**
 * The Kahn's Topological Sort Algorithm in C++
 * Using the Adjecency List
 * Time Cost : O(|V|+|E|)
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 5; // The number of Vertex

enum status {UNDISCOVERED,VISITED};

struct Vertex
{
    int inDegree, outDegree;
    int data;
    status _stat;
}V[N];

vector<int> AdjList[N];   //Using vector to simulate the adjlist
queue<int> vertexQueue;   //The call queue
/**
 * Initialize the graph as below:
The Graph:

0->1->3
|  |  |
\/ \/ \/
2->4<--

 * @return The pointer to the start vertex
 */
Vertex* init_graph()
{
    while(!vertexQueue.empty())
        vertexQueue.pop();

    for(int i=0; i<N; i++)
    {
        AdjList[i].clear();
        V[i]._stat = UNDISCOVERED;
        V[i].data = i;
    }

    V[0].inDegree = 0; V[0].outDegree = 2;
    V[1].inDegree = 1; V[1].outDegree = 3;
    V[2].inDegree = 1; V[2].outDegree = 1;
    V[3].inDegree = 1; V[3].outDegree = 1;
    V[4].inDegree = 3; V[4].outDegree = 0;

    AdjList[0].push_back(1); AdjList[0].push_back(2);
    AdjList[1].push_back(3); AdjList[1].push_back(4);
    AdjList[2].push_back(4);
    AdjList[3].push_back(4);

    return & V[0];
}

bool Topological_Sort()
{
    for(int i=0; i<N; i++)
    {
        if(V[i].inDegree == 0)
            vertexQueue.push(i);
    }

    while(!vertexQueue.empty())
    {
        int top = vertexQueue.front();
        V[top].outDegree = 0;
        V[top]._stat = VISITED;
        int i=0;

        for(int v : AdjList[top])
        {
            --V[v].inDegree;

            AdjList[top][i++] = -1;
            if(V[v].inDegree == 0)
                vertexQueue.push(v);
        }
        cout<<top<<" ";

        vertexQueue.pop();
    }

    for(int i=0; i<N; i++)
    {
        for(int v : AdjList[i])
            if(v != -1)
            {
                return false;
            }
    }

    return true;
}

int main()
{
    init_graph();

    bool status = Topological_Sort();
    if(status == false)
    {
        cout<<"Error! The graph has at least one cycle!"<<endl;
    }
    return 0;
}

谢谢观看~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习之tensorflow实战篇

igraph软件包创建图和网络(创建邻接矩阵)

一、igraph软件包创建图和网络 igraph 是一个独立的库,底层是 C,上层有 Python 和 R 接口,主要做图和网络方面的计算,附带绘图功能。 ...

6374
来自专栏决胜机器学习

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(十)——有向无环图与拓扑算法 (原创内容,转载请注明来源,谢谢) 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。...

55811
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程1

前言 这里是一篇新手教程,环境是Xcode7+OpenGL ES 2.0,目标写一个OpenGL ES的hello world。 OpenGL ES系列教程在...

3369
来自专栏技术碎碎念

LeetCode-70-Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time y...

36212
来自专栏lhyt前端之路

从MDN上的canvas例子受到的启发0.前言1.面向对象编程的实践2.相互纠缠的现象3.解决方案4.模拟核裂变5.大鱼吃小鱼

在面对碰撞检测后还有后续动作的情况,必须考虑一下相互纠缠的问题: 如果两个小球被检测到碰撞的时候,而且加上他们的速度下一步还是处于碰撞范围内,就像引力一样无法脱...

1462
来自专栏数据结构与算法

洛谷P2774 方格取数问题(最小割)

1213
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

2131
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

2058
来自专栏从流域到海域

迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

2277
来自专栏聊聊技术

原 初学图论-DAG单源最短路径算法

38312

扫码关注云+社区

领取腾讯云代金券