大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
拓扑排序是对有向无环图的一种排序。表示了顶点按边的方向出现的先后顺序。假设有环，则无法表示两个顶点的先后顺序。
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却是遍历了全部顶点，甚至已经删除的顶点。
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;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118755.html原文链接：https://javaforall.net
