输出有向无环图的所有拓扑序列
1，基本思想2，代码实现
1，基本思想
输出有向无环图的其中一个拓扑序列比较简单，输出所有的拓扑序列则要用到回溯的思想和递归的方法。这里暂不对回溯法做解释。
2，代码实现
#include<iostream>
#include<vector>
using namespace std
;
#define Max 9999
vector
<int> result
;
int n
, m
;
int G
[Max
][Max
];
bool visited
[Max
];
int inDegree
[Max
];
void dfs()
{
if (result
.size() == n
)
{
for (int i
= 0; i
< n
; ++i
)
{
cout
<< result
[i
] << " ";
}
cout
<< endl
;
return;
}
for (int i
= 0; i
< n
; ++i
)
{
if (!visited
[i
] && inDegree
[i
] == 0)
{
result
.push_back(i
);
visited
[i
] = true;
for (int j
= 0; j
< n
; ++j
)
{
if (G
[i
][j
] > 0)
{
inDegree
[j
]--;
}
}
dfs();
result
.pop_back();
visited
[i
] = false;
for (int j
= 0; j
< n
; ++j
)
{
if (G
[i
][j
] > 0)
{
inDegree
[j
]++;
}
}
}
}
return;
}
int main()
{
cout
<< "输入顶点数：";
cin
>> n
;
cout
<< "输入边数：";
cin
>> m
;
fill(G
[0], G
[0] + Max
* Max
, 0);
fill(visited
, visited
+ Max
, false);
fill(inDegree
, inDegree
+ Max
, 0);
cout
<< "输入各条边的信息：";
int u
, v
;
for (int i
= 0; i
< m
; ++i
)
{
cin
>> u
>> v
;
G
[u
][v
]++;
inDegree
[v
]++;
}
dfs();
return 0;
}
输入输出信息：
