强连通分量的tarjan算法

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

一、数据集形式

这里写图片描述
其中：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//qiangliantongfenliang//test.txt"
class CTreeNode
{
public:CTreeNode(){}~CTreeNode() {}int value;CTreeNode *next;
};
class CTree
{
public:CTree() {}~CTree() {}int value;CTreeNode *next;CTree *before;int state;//tarjan特有变量int low;int dfn;
};
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;tree[i].before = NULL;}CTreeNode *nt;while (!ReadFile.eof())            //按空格读取，遇到空白符结束{nt = new CTreeNode();       //读出的数据新建一个节点ReadFile >> temp;ReadFile>> (nt->value);nt->next = tree[temp].next;tree[temp].next = nt;}return tree;
}CTree *tree;
int length;
int t;
stack<int> ss;
int ij;//用来记录数量void DfsVisit(CTree*tNode)
{tNode->state = 1;t++;tNode->dfn = t;tNode->low = t;ss.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]);}if (tree[p->value].state == 1){//深度优先搜索，向下查找if (tree[p->value].dfn < tNode->low){tNode->low = tree[p->value].dfn;}}p = p->next;}tNode->state = 2;//回溯父节点if (tNode->before!=NULL&&(tNode->before->low) > (tNode->low)){tNode->before->low=tNode->low;}if (tNode->dfn == tNode->low){ij++;//cout << "第" << ij << "个强连通分量：";int temp;do {temp = ss.top();//cout << temp << " ";ss.pop();} while (tNode->value!=temp);//cout << endl;}}
void Tarjan()
{t = 0;ij = 0;//用于记录强连通分量的数量for (int i = 0; i < length; i++){if (tree[i].state == 0)DfsVisit(&tree[i]);}
}int main()
{//读取了文本中的内容，并根据建立其邻接链表tree = createTree(PATH, length);//tarjan算法，深度优先搜索得出值double useTime;clock_t start, finish;start = clock();Tarjan();cout << "共" << ij << "组强连通分量" << endl;finish = clock();useTime = (double)(finish - start) / CLOCKS_PER_SEC * 1000;printf("%f 毫秒\n", useTime);system("pause");return 0;
}