强连通分量的Garbow算法

本文主要是介绍强连通分量的Garbow算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、数据集形式

这里写图片描述
其中：1595446（节点个数）
0（起始边） 1（终边）

二、数据集

上传中等待审核成功再链接过来

三、实现代码

// Tarjan.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include "time.h"
#include <fstream>
#include<iostream>
#include <stack>
using namespace std;
#define PATH "E://dataset//MapSet//quanliantongfenliang//uniprot150m.txt"
class CTreeNode
{
public:CTreeNode(){}~CTreeNode() {}int value;CTreeNode *next;
};
class CTree
{
public:CTree() {}~CTree() {}int value;CTreeNode *next;CTree *before;int state;
};
CTree* createTree(char* filename, int &length)
{CTree *tree;ifstream ReadFile;int temp;ReadFile.open(filename, ios::in);//ios::in 表示以只读的方式读取文件ReadFile >> length;//第一个字符是数组长度tree = new CTree[length];//为树赋初值for (int i = 0; i < length; i++){tree[i].next = NULL;tree[i].value = i;tree[i].state = 0;}CTreeNode *nt;while (!ReadFile.eof())            //按空格读取，遇到空白符结束{nt = new CTreeNode;     //读出的数据新建一个节点ReadFile >> temp >> (nt->value);nt->next = tree[temp].next;tree[temp].next = nt;}return tree;
}CTree *tree;
int length;
int t;
stack<int> ss;
stack<int> root;
int ij;//用来记录数量void DfsVisit(CTree*tNode)
{tNode->state = 1;ss.push(tNode->value);root.push(tNode->value);CTreeNode *p = tNode->next;while (p != NULL){if (tree[p->value].state == 0){tree[p->value].before = tNode;DfsVisit(&tree[p->value]);}p = p->next;}tNode->state = 2;//回溯父节点,判断bool iflag = true;p = tNode->next;while (p != NULL){if (tree[p->value].state == 1){while (tree[p->value].value != tree[root.top()].value){root.pop();}iflag = false;break;}p = p->next;}if (iflag&&!ss.empty()){ij++;//cout << "第" << ij << "组强连通分量为："  ;while (ss.top()!=root.top()){//      cout<<ss.top()<<" ";tree[ss.top()].state = 2;ss.pop();}//  cout <<ss.top()<< endl;tree[ss.top()].state = 2;ss.pop();root.pop();}
}
void Garbow()
{ij = 0;//用于记录强连通分量的数量for (int i = 0; i < length; i++){if (tree[i].state == 0)DfsVisit(&tree[i]);}
}int main()
{//读取了文本中的内容，并根据建立其邻接链表tree = createTree(PATH, length);//Garbow算法，深度优先搜索得出值double useTime;clock_t start, finish;start = clock();Garbow();cout << "共" << ij << "组强连通分量" << endl;finish = clock();useTime = (double)(finish - start) / CLOCKS_PER_SEC * 1000;printf("%f 毫秒\n", useTime);system("pause");return 0;
}