拓扑排序

拓扑排序

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

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

在现实生活中,也会有不少应用样例,比方学校课程布置图,要先修完一些基础课,才干够继续修专业课。
一个简单的求拓扑排序的算法:首先要找到随意入度为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)
blank

相关推荐

  • 菜鸟教程 python 正则表达式_python正则表达式替换

    菜鸟教程 python 正则表达式_python正则表达式替换正则表达式正则表达式(RegularExpression,在代码中常简写为regex、regexp、RE或re)是预先定义好的一个“规则字符率”,通过这个“规则字符串”可以匹配、查找和替换那些

  • 开源商城系统带app源码_萌果APP源码

    开源商城系统带app源码_萌果APP源码直接下载导入工程即可直接运行.包含服务器源码(服务器已经在线配置)主要功能如下:首页:从上到下分别是:广告轮播、菜单按钮、品牌推介、推介、热销商品分类:类似京东商品三级分类,左边是一级分类,右边是二级分类,二级分类下面包含三级子分类商城功能:商品详情、购物车、确认订单、支付功能商品详情:商品大图轮播、商品规格(选择不同规格显示不同价格,

  • torch mseloss_pytorch conv1d

    torch mseloss_pytorch conv1dMSELOSSCLASStorch.nn.MSELoss(size_average=None,reduce=None,reduction:str=’mean’)创建一个标准来测量输入x和目标y中每个元素之间的均方误差(L2范数平方)。未减少的损失(即reduction设置为’none’)可以描述为:其中N是batchsize.如果reduction不是’none'(默认为’mean’),那么:x和y是任意形状的张量,每个张量总共有n个元素…

  • 浙江python课程_浙江八年级新增Python编程课程!是谁将少儿编程推上风口?

    浙江python课程_浙江八年级新增Python编程课程!是谁将少儿编程推上风口?浙江消息,今年9月份开始的新学期,三到九年级信息技术课将同步替换新器材。其中,八年级将新增Python课程内容。新高一信息技术编程语言由VB替换为Python,大数据、人工智能、程序设计与算法按照教材规划五六年级开始接触。不得不说,在“少儿编程”这条路上,浙江省算是“死磕”到底了。早在2014年,浙江就发布了《浙江省深化高校考试招生制度综合改革试点方案》,方案提到:把信息技术(含编程)正式纳入高考…

  • java代码是怎么运行的_java代码是什么

    java代码是怎么运行的_java代码是什么1.Java代码有很多不同的运行方式1)可以在开发工具中运行2)可以双击执行jar文件运行,3)也可以在命令行中运行4)甚至可以在网页中运行这些执行方式都离不开JRE,也就是Java的运

  • l1正则化为什么稀疏(特征值重根与秩的关系)

    L1正则化与稀疏性L1正则化使得模型参数具有稀疏性的原理是什么?机器学习经典之作《patternrecognitionandmachinelearning》中的第三章作出的一个解释无疑是权威且直观的,我们也经常都是从这个角度出发,来解释L1正则化使得模型参数具有稀疏性的原理。再回顾一下,以二维为例,红色和黄色的部分是L1、L2正则项约束后的解空间,蓝色的等高线是凸优化问题中的目标函数(…

发表回复

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

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