拓扑排序

拓扑排序

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。假设有环,则无法表示两个顶点的先后顺序。

在现实生活中,也会有不少应用样例,比方学校课程布置图,要先修完一些基础课,才干够继续修专业课。
一个简单的求拓扑排序的算法:首先要找到随意入度为0的一个顶点,删除它及全部相邻的边,再找入度为0的顶点,以此类推,直到删除全部顶点。顶点的删除顺序即为拓扑排序。
    非常easy得到拓扑排序的伪代码:
    void TopSort(Graph g)
    {
        for (int i=0; i<vertexnum; i++)
        {
            vertex v = FindZeroIndegree(g);
            if (v is not vertex)        
                cout <<“the graph has cycle”<<endl;
            cout << v ;
            foreach vertex w adjacent to v
                w.indegree–;
        }
    }
拓扑排序   
    相同以上图为例,对于该图进行拓扑排序会得到:v1 v2 v5 v4 v3 v7 v6 或者v1 v2 v5 v4 v7 v3 v6 。
    仍然利用上一贴图的构建方法,进行验证。
    代码实现:
 

 
#include <iostream>

using
namespace
std;

#define MAX_VERTEX_NUM    20

struct
adjVertexNode

{

   
int
adjVertexPosition;

   
adjVertexNode
*
next;

};

struct
VertexNode

{

   
char
data
[
2
];

   
adjVertexNode
*
list;

   
int
indegree;

};

struct
Graph

{

   
VertexNode
VertexNode
[
MAX_VERTEX_NUM
];

   
int
vertexNum;

   
int
edgeNum;

};

void
CreateGraph (
Graph
&
g)

{

    
int
i
,
j
,
edgeStart
,
edgeEnd;

    
adjVertexNode
*
adjNode;

    
cout
<<
“Please input vertex and edge num (vnum enum):”
<<
endl;

    
cin
>>
g
.
vertexNum
>>
g
.
edgeNum;

    
cout
<<
“Please input vertex information (v1)
/n
note: every vertex info end with Enter”
<<
endl;

    
for (
i
=
0;
i
<
g
.
vertexNum;
i
++)

    
{

        
cin
>>
g
.
VertexNode
[
i
].
data;
// vertex data info.

        
g
.
VertexNode
[
i
].
list
=
NULL;

        
g
.
VertexNode
[
i
].
indegree
=
0;

    
}

    
cout
<<
“input edge information(start end):”
<<
endl;

    
for (
j
=
0;
j
<
g
.
edgeNum;
j
++)

    
{

        
cin
>>
edgeStart
>>
edgeEnd;

        
adjNode
=
new
adjVertexNode;

        
adjNode
->
adjVertexPosition
=
edgeEnd

1;
// because array begin from 0, so it is j-1

        
adjNode
->
next
=
g
.
VertexNode
[
edgeStart

1
].
list;

        
g
.
VertexNode
[
edgeStart

1
].
list
=
adjNode;

        
//每添加�一条边,则边的End顶点的入度加1

        
g
.
VertexNode
[
edgeEnd

1
].
indegree
++;

    
}

}

void
PrintAdjList(
const
Graph
&
g)

{

   
cout
<<
“The adjacent list for graph is:”
<<
endl;

   
for (
int
i
=
0;
i
<
g
.
vertexNum;
i
++)

   
{

       
cout
<<
g
.
VertexNode
[
i
].
data
<<
“->”;

       
adjVertexNode
*
head
=
g
.
VertexNode
[
i
].
list;

       
if (
head
==
NULL)

           
cout
<<
“NULL”;

       
while (
head
!=
NULL)

       
{

           
cout
<<
head
->
adjVertexPosition
+
1
<<
” “;

           
head
=
head
->
next;

       
}

       
cout
<<
endl;

   
}

}

VertexNode
&
FindZeroIndegree(
Graph
&
g)

{

   
for (
int
i
=
0;
i
<
g
.
vertexNum;
i
++)

   
{

       
if (
g
.
VertexNode
[
i
].
indegree
==
0)

           
return
g
.
VertexNode
[
i
];

   
}

   
return
g
.
VertexNode
[
0
];

}

void
TopSort(
Graph
&
g)

{

   
cout
<<
“The topsort is:”
<<
endl;

   
for (
int
i
=
0;
i
<
g
.
vertexNum;
i
++)

   
{

       
VertexNode
&
v
=
FindZeroIndegree(
g);

       
if (
v
.
indegree
!=
NULL)

           
cout
<<
“The graph has cycle, can not do topsort”
<<
endl;

       
// print graph as topsort.

       
cout
<<
v
.
data
<<
” “;

       
// for each vertex w adjacent to v, –indegree

       
adjVertexNode
*
padjv
=
v
.
list;

       
while (
padjv
!=
NULL)

       
{
//!!这个算法这里破坏了原图中的入度信息。最后入度均为1

           
g
.
VertexNode
[
padjv
->
adjVertexPosition
].
indegree
;

           
padjv
=
padjv
->
next;

       
}

       
//避免入度信息均为零FindZeroIndegree找到删除的顶点,将删除的顶点入度置为1

       
v
.
indegree
++;

   
}

   
cout
<<
endl;

}

void
DeleteGraph(
Graph
&
g)

{

   
for (
int
i
=
0;
i
<
g
.
vertexNum;
i
++)

   
{

       
adjVertexNode
*
tmp
=
NULL;

       
while(
g
.
VertexNode
[
i
].
list
!=
NULL)

       
{

           
tmp
=
g
.
VertexNode
[
i
].
list;

           
g
.
VertexNode
[
i
].
list
=
g
.
VertexNode
[
i
].
list
->
next;

           
delete
tmp;

           
tmp
=
NULL;

       
}

   
}

}

int
main(
int
argc
,
const
char
**
argv)

{

   
Graph
g;

   
CreateGraph(
g);

   
PrintAdjList(
g);

   
TopSort(
g);

   
DeleteGraph(
g);

   
return
0;

}

 执行结果:
拓扑排序
 

     从上面的代码能发现
FindZeroIndegree的时间复杂度为O(|V|),TopSort的时间复杂度为O(|V|2)
     原因在于,每次删除顶点,仅仅有邻接点须要调整入度,但
FindZeroIndegree却是遍历了全部顶点,甚至已经删除的顶点。
     更为合理的方法是将每次遍历得出的入度为0的顶点放入一个队列。
void
TopSort2(
Graph
&
g)

{

   
queue
<
VertexNode
>
q;

   
for (
int
i
=
0;
i
<
g
.
vertexNum;
i
++)

   
{

       
if (
g
.
VertexNode
[
i
].
indegree
==
0)

           
q
.
push(
g
.
VertexNode
[
i
]);

   
}

   
int
count
=
0;

   
cout
<<
“The topsort is:”
<<
endl;

   
while (
!
q
.
empty())

   
{

       
VertexNode
v
=
q
.
front();

       
q
.
pop();

       
cout
<<
v
.
data
<<
” “;

       
count
++;

       
adjVertexNode
*
padjv
=
v
.
list;

       
while (
padjv
!=
NULL)

       
{
//!!这个算法这里破坏了原图中的入度信息。最后入度均为1

           
if (
(
g
.
VertexNode
[
padjv
->
adjVertexPosition
].
indegree)
==
0)

               
q
.
push(
g
.
VertexNode
[
padjv
->
adjVertexPosition
]);

           
padjv
=
padjv
->
next;

       
}

   
}

   
if (
count
!=
g
.
vertexNum)

       
cout
<<
“The graph has cycle, can not do topsort”
<<
endl;

}
     内部的while循环最多运行|E|次,即每条边运行一次。队列对每一个顶点最多运行一次操作,所以新算法的时间复杂度为O(|E|+|V|). 优于O(|V|2)由于拓扑图边数最多有n(n-1)/2,即O(|E|+|V|)<=O(|V|2)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118755.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Word2007怎样从随意页開始设置页码 word07页码设置毕业论文

    Word2007怎样从随意页開始设置页码 word07页码设置毕业论文

    2021年11月15日
  • 海量数据处理分析

    海量数据处理分析 笔者在实际工作中,有幸接触到海量的数据处理问题,对其进行处理是一项艰巨而复杂的任务。原因有以下几个方面:一、数据量过大,数据中什么情况都可能存在。如果说有10条数据,那么大不了每条去逐一检查,人为处理,如果有上百条数据,也可以考虑,如果数据上到千万级别,甚至过亿,那不是手工能解决的了,必须通过工具或者程序进行处理,尤其海量的数据中,什么情况都可能存在,例如,数据中某处格式出了问题

  • JMH初探

    JMH初探JMH入门(很多情况下需要做性能基准测试(benchmark)。简单的说就是,在几种类似的解决方案中,寻找效率较高的。比如对比一下thrift,protobuf,avro在对象序列化时的效率等。这种测试通常需要对被测的代码段反复执行,最后取平均值,然后横向对比几种方案。如果能有(时间、CPU、内存、IO)曲线图表输出就更加直观了。一开始考虑用JMeter来做,但是这个框架似乎有点大,看了几次都

  • camera密码错误_camera filter

    camera密码错误_camera filter01flicker(banding)现象出现flicker(banding)问题时,从视频上看会发现有规律的明暗相间的条纹,这种现象也叫做牛顿环。如下图所示。02产生flicker(ban…

    2022年10月13日
  • datagrip 2022.01.13 激活码【2022最新】2022.03.10

    (datagrip 2022.01.13 激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~1M…

  • vue项目管理_vue适合做管理系统吗

    vue项目管理_vue适合做管理系统吗口述vue后台管理系统流程(面试可用)后台页面的权限验证与安全性是非常重要的,可以说是一个后台项目一开始就必须考虑和搭建的基础核心功能我们前端所要做的是:不同的权限对应着不同的路由,同时侧边栏也需要根据不同的权限,异步生成.技术栈主要有:vue,vue-router,vuex,axios,vue-cli3.x(没有webpack.config.js配置文件,取而代之的是vue.c…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号