目录
- Chat
- 图解
- 基于栈实现（dfs）
- 基于队列实现（bfs）
- 基于递归实现（dfs）
Chat
1.代码所属的类在数据结构代码整理_基于邻接表存储结构的有向图的实现(C++) 2.拓扑排序的思想就是不断找入度为0的节点并将其输出并标记，标记后与他相连的节点的入度都会减一，不断进行标记直至所有的节点都被输出为止。（如果不是很理解，看下面的图）
3.我在写代码的时候发现了一个比较神奇的东西，不知道你在读代码的时候有没有发现下面三段代码非常相似，基于栈实现和队列实现的两段代码几乎是一模一样的，只是把stack改成了queue，top()改为front()，其余都没有变动，因为代码的思想是一模一样的只是换了个容器换了一种处理顺序而已。而且递归实现的拓扑排序也是从栈实现改过来的，因为递归就指一种栈结构，递归的过程就是压栈的过程，就相当于把push()换成了递归语句，回溯的过程就是出栈的过程，相当于把pop()换成了return。这是一种思想的转化，但是在写寻常递归的时候最好不要这么想，递归有递归的写法，我这个只是偷懒把栈实现的代码进行了一些改动而已。
4.写的比较仓促，优化的余地比较大，有bug请评论。
图解
图片来自：拓扑排序入门（真的很简单）
基于栈实现（dfs）
template <class TYPE, class KTYPE>
void Graph<TYPE, KTYPE>::sort_1(void (*process)(TYPE dataProc)) {//栈实现拓扑排序
Vertex<TYPE>* p = first;
stack<Vertex<TYPE>*> st;
vector<int>v;//暂存初始入度
while (p) {
p->processed = 0;
v.push_back(p->inDegree);
if (p->inDegree == 0) {
st.push(p);
p->processed = 1;
}
p = p->pNextVertex;
}
while (!st.empty()) {
p = first;
Vertex<TYPE>* tempv = st.top();
process(tempv->data);
st.pop();
Arc<TYPE>* tempa = tempv->pArc;
while (tempa) {
if (!tempa->destination->processed)
tempa->destination->inDegree--;
tempa = tempa->pNextArc;
}
while (p) {
if (p->inDegree == 0 && !p->processed) {
st.push(p);
p->processed = 1;
}
p = p->pNextVertex;
}
}
int cnt = 0;
p = first;
while (p) {
p->inDegree = v[cnt++];
p->processed = 0;
p = p->pNextVertex;
}
}基于队列实现（bfs）
Vertex<TYPE>* p = first;
queue<Vertex<TYPE>*> st;
vector<int>v;//暂存初始入度
while (p) {
p->processed = 0;
v.push_back(p->inDegree);
if (p->inDegree == 0) {
st.push(p);
p->processed = 1;
}
p = p->pNextVertex;
}
while (!st.empty()) {
p = first;
Vertex<TYPE>* tempv = st.front();
process(tempv->data);
st.pop();
Arc<TYPE>* tempa = tempv->pArc;
while (tempa) {
if (!tempa->destination->processed)
tempa->destination->inDegree--;
tempa = tempa->pNextArc;
}
while (p) {
if (p->inDegree == 0 && !p->processed) {
st.push(p);
p->processed = 1;
}
p = p->pNextVertex;
}
}
int cnt = 0;
p = first;
while (p) {
p->inDegree = v[cnt++];
p->processed = 0;
p = p->pNextVertex;
}
}基于递归实现（dfs）
template <class TYPE, class KTYPE>
void Graph<TYPE, KTYPE>::sort_3(void (*process)(TYPE dataProc), Vertex<TYPE>* tempv, int cnt, int num){//递归实现拓扑排序
if (num == count)
return;
if (!cnt)
tempv = first;
cnt++;
Vertex<TYPE>* p = first;
while (p) {//找到为零节点
if (p->inDegree == 0 && !p->processed) {
p->processed = 1;
sort_3(process, p, cnt, num);
p = first;//保证每次递归后都从头搜索
}
p = p->pNextVertex;
}
process(tempv->data);
num++;
Arc<TYPE>* tempa = tempv->pArc;//更改度值
while (tempa) {
if (!tempa->destination->processed)
tempa->destination->inDegree--;
tempa = tempa->pNextArc;
}
}