《数据结构与算法》——拓扑排序
本帖最后由 luciferzf 于 2017-8-20 22:02 编辑拓扑排序：
建立一个有向图，我们称之为AOV图。我们需要将AOV图中每个点进行排序，按照入度的多少的顺序。我们用栈结构来储存点，首先我们先将入度为0的点压入栈中，然后把压入栈中的点从AOV图中删除，与其相邻的点的度减一。
在代码实现的过程中，我们使用数组来储存每个点，用链表的方式来储存每个点的出度。当进行遍历的时候，我们将所有入度为0的点压入栈中，然后把改点的出度的点的入度减一。循环至所有点都被压入栈中。
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int stack;
int N;
class graph
{
public:
int low;
graph *np=NULL;
};
class VERTEX
{
public:
int power=0;
graph *np = NULL;
};
void Input(VERTEX vertex[])
{
int a, b;
printf("input the edge of graph and end with double -1:\n");
cin >> a >> b;
graph *cp=NULL;
while (a != -1)
{
if (vertex.np == NULL)
{
vertex.np = new graph;
cp = vertex.np;
}
else
{
cp->np = new graph;
cp = cp->np;
}
cp->low = b;
vertex.power++;
cin >> a >> b;
}
}
void print(VERTEX vertex[])
{
for (int i = 0; i < N; i++)
{
printf("%d",stack);
if (i != N-1)
{
printf("——>");
}
else
{
cout << endl;
}
}
}
int main()
{
int count=0;
cout << "input the numbers of the vertexes:";
cin >> N;
int edge=0;
cout<<"input the numbers of the edge:";
cin>>edge;
VERTEX vertex;
Input(vertex);
graph *cp;
while (count < N)
{
int precount = count;
for (int i = 1; i <= N; i++)
{
if (vertex.power == 0)
{
stack = i;
vertex.power = -1;
}
}
while (precount != count)
{
cp = vertex].np;
while (cp != NULL)
{
vertex.power--;
cp = cp->np;
}
precount++;
}
}
print(vertex);
system("PAUSE");
}
页:
[1]