《算法导论》广度优先搜索，深度优先搜索之强联通分支

问题越来越复杂，《算法导论》一书给出的伪代码越来越坑爹，计算强联通分支几句英语就给俺打发了。

于是邻接表的转置和强联通分支的输出都成了待自行解决的问题，期间因为一些逻辑错误导致一直出不了正确结构，翻看了将用作大二教材的《数据结构（c语言版）》一书，话说俺一直觉得上面给出的代码排版和粗体的标识各种难看，而其对该算法实现的底层也用了几个结构体，google来的实现代码一看也均是参照《数据结构（c语言版）》进行的实现，和我自己用C++搞的相去甚远。只得自己纠结纠结再纠结，睡觉也在想，好在终于守得拨云见日。
实现过程中对《算法导论》书上描述的伪代码和数据结构做了轻微改动，比如结构体中增加了一个卫星数据child，方便输出强连通分支。
强连通分支又叫深度优先森林，说是森林，其实每棵树都是一条线，没有任何分支来着，所以输出时直接用child遍历下去就行。
代码整理如下，详见注释，不再赘述。
测试一下：

#include "stdafx.h"
#include <iostream>
#include <queue> // 广度优先搜索中管理灰色顶点的先进先出队列
#include <vector> // 邻接表容器
#include <string>
#include <limits> // INT_MAX
#include <algorithm> // 泛型算法sort的谓词版本进行拓扑排序
using namespace std;

enum COLOR {WHITE, GRAY, BLACK};

struct Vertex {
trueint no; // 结点序号
truestring name; // 结点名称
trueCOLOR color;
truevector<int>* Adj; // 邻接表，包含所有满足条件(u, v)∈E的顶点v
true// 用于广度优先搜索
trueint distence; // 广度优先树中从s到v的路径长，对应于图G中从从s到v的一条最短路径长
trueVertex* parent; // 广度优先树中结点的父母
true// 用于深度优先搜索
trueVertex* child; // 深度优先树中结点的孩子，方便输出强联通分支，算是数据结构的扩张的一个应用。。。
trueint begin; // 顶点v第一次被发现时记下该时间戳
trueint finish; // 结束检查v的邻接表时记下该时间戳
};

// sort的谓词函数，用作拓扑排序
inline bool isLarge(const Vertex* v1, const Vertex* v2)
{
truereturn v1->finish > v2->finish;
}

class Graph {
public:
true// 构造邻接表
truevoid creatGraph();
trueinline void displayGraph() const;

true// 广度优先搜索
truevoid BFS(const int);
truevoid printPath(const int, const int) const;

true// 深度优先搜索
truevoid DFS();
truevoid DFSVisit(Vertex*);
trueinline void topologicalSort(); // 有向无回路图的拓扑排序
truevoid transposition(); // 转置
truevoid stronglyConnectedComponents(); // 强连通分支

private:
trueint time;
truevector<Vertex*> vertexs; // 储存邻接表
};

void Graph::creatGraph()
{
trueint verNum;
truecout << "输入顶点数：";
truecin >> verNum;
truecout << "输入" << verNum << "个顶点的名称：";
truefor (int i = 0; i != verNum; ++i) {
truetrueVertex* newNode = new Vertex;
truetruenewNode->no = i + 1;
truetruecin >> newNode->name;
truetruevertexs.push_back(newNode);
true}
truefor (int i = 0; i != verNum; ++i) {
truetruevector<int>* ivec = new vector<int>;
truetruevertexs[i]->Adj = ivec;
truetruecout << "输入第" << i + 1 << "个结点" << vertexs[i]->name << "的邻接节点个数和序号：";
truetrueint j;
truetruecin >> j;
truetruewhile (j-- != 0) {
truetruetrueint k;
truetruetruecin >> k;
truetruetruevertexs[i]->Adj->push_back(k);
truetrue}
true}
}
void Graph::displayGraph() const
{
truefor (vector<Vertex*>::const_iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter) {
truetruecout << (*iter)->no << " -> ";
truetruefor (vector<int>::const_iterator adjIter = (*iter)->Adj->begin(); adjIter != (*iter)->Adj->end(); ++adjIter)
truetruetruecout << *adjIter << " -> ";
truetruecout << "NULL" << endl;
true}
}

void Graph::BFS(const int start)
{
trueVertex* startNode = vertexs[start - 1];
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter) {
truetruetrue(*iter)->color = WHITE;
truetruetrue(*iter)->distence = INT_MAX;
truetruetrue(*iter)->parent = NULL;
true}
truestartNode->color = GRAY;
truestartNode->distence = 0;

truequeue<Vertex*> vertexsQueue;
truevertexsQueue.push(startNode);
truewhile (!vertexsQueue.empty()) {
truetrueVertex* thisNode = vertexsQueue.front();
truetruevertexsQueue.pop();
truetruefor (vector<int>::iterator iter = thisNode->Adj->begin(); iter != thisNode->Adj->end(); ++iter)
truetruetrueif (vertexs[*iter - 1]->color == WHITE) {
truetruetruetruevertexs[*iter - 1]->color = GRAY;
truetruetruetrue++vertexs[*iter - 1]->distence;
truetruetruetruevertexs[*iter - 1]->parent = thisNode;
truetruetruetruevertexsQueue.push(vertexs[*iter - 1]);
truetruetrue}
truetruethisNode->color = BLACK;
true}
}
void Graph::printPath(const int start, const int end) const
{
trueif (start == end)
truetruecout << "The path from " << start << " to " << end << " is " << start;
trueelse if (vertexs[end - 1]->parent == NULL)
truetruecout << "No path from " << start << " to " << end << " exist.";
trueelse {
truetrueprintPath(start, vertexs[end - 1]->parent->no);
truetruecout << " -> " << end;
true}
}

void Graph::DFS()
{
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter) {
truetrue(*iter)->color = WHITE;
truetrue(*iter)->parent = NULL;
truetrue(*iter)->child = NULL;
true}
truetime = 0;
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter)
truetrueif ((*iter)->color == WHITE)
truetruetrueDFSVisit(*iter);
}
void Graph::DFSVisit(Vertex* thisNode)
{
truethisNode->color = GRAY;
truethisNode->begin = ++time;
truefor (vector<int>::iterator iter = thisNode->Adj->begin(); iter != thisNode->Adj->end(); ++iter)
truetrue// 拓扑排序会打乱顺序
truetruefor (vector<Vertex*>::iterator iter2 = vertexs.begin(); iter2 != vertexs.end(); ++iter2)
truetruetrueif ((*iter2)->no == *iter)
truetruetruetrueif ((*iter2)->color == WHITE) {
truetruetruetruetrue(*iter2)->parent = thisNode;
truetruetruetruetruethisNode->child = *iter2;
truetruetruetruetrueDFSVisit(*iter2);
truetruetruetrue}
truethisNode->color = BLACK;
truethisNode->finish = ++time;
}
void Graph::topologicalSort()
{
true// 通过比较finish时间，从而完成拓扑排序
truesort(vertexs.begin(), vertexs.end(), isLarge); // 排序算法的谓词版本，使用isLarge函数进行比较
}
void Graph::transposition()
{
truevector<Vertex*> tmpVertexs;
truefor (int i = 0; i != vertexs.size(); ++i) {
truetrueVertex* newVertex = new Vertex;
truetruenewVertex->Adj = new vector<int>;
truetruetmpVertexs.push_back(newVertex);
true}
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter)
truetruefor (vector<int>::iterator adjIter = (*iter)->Adj->begin(); adjIter != (*iter)->Adj->end(); ++adjIter)
truetruetruetmpVertexs[*adjIter - 1]->Adj->push_back(iter - vertexs.begin() + 1);
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter)
truetrue(*iter)->Adj = tmpVertexs[iter - vertexs.begin()]->Adj;
}
void Graph::stronglyConnectedComponents()
{
trueDFS(); // 第一轮深度优先搜索，计算finish时间戳
truetransposition(); // 转置vertexs
truetopologicalSort(); // 根据finish时间戳进行拓扑排序
truecout << endl << "转置后：" << endl;
truedisplayGraph();
trueDFS(); // 第二轮深度优先搜索，构造强联通分支
true// 输出强连通分支（深度优先森林），森林中的每一颗树就是一个强连通分支
trueint i = 1;
truefor (vector<Vertex*>::iterator iter = vertexs.begin(); iter != vertexs.end(); ++iter)
truetrueif ((*iter)->parent == NULL && (*iter)->Adj->size() != 0) {
truetruetruecout << "第" << i++ << "组强联通分支：";
truetruetruecout << "<" << (*iter)->no << ":" << (*iter)->name << ">";
truetruetrueVertex* iter2 = *iter;
truetruetruewhile (iter2->child != NULL) {
truetruetruetrueiter2 = iter2->child;
truetruetruetruecout << "<" << iter2->no << ":" << iter2->name << ">";
truetruetrue}
truetruetruecout << endl;
truetrue}
}

int main()
{
trueGraph graph;
truegraph.creatGraph();
truegraph.displayGraph();
truegraph.stronglyConnectedComponents();
truesystem("pause");
truereturn 0;
}