Skip to content

Commit 2890949

Browse files
xubenhaoxubenhao
committed
算法--图的强连通分量
图的强连通分量算法完整实现
1 parent 63031f7 commit 2890949

File tree

2 files changed

+154
-0
lines changed

2 files changed

+154
-0
lines changed

‎Algorithm/Graph/DepthFirstVisit.h‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,7 @@ namespace AlLib
9797
~DepthFirstVisit();
9898

9999
DataStruct::Array::DynArray<Node*> Run();
100+
DataStruct::Array::DynArray<Node*> Run(const DataStruct::Array::DynArray<Key>& arrKeys_);
100101
private:
101102
DepthFirstVisit(const DepthFirstVisit& nDFV_) = default;
102103
DepthFirstVisit& operator=(const DepthFirstVisit& nDFV_) = default;
@@ -173,6 +174,39 @@ namespace AlLib
173174
return _arrpNodes;
174175
}
175176

177+
template<typename Key, typename Value>
178+
DataStruct::Array::DynArray<typename DepthFirstVisit<Key, Value>::Node*> DepthFirstVisit<Key, Value>::Run(const DataStruct::Array::DynArray<Key>& arrKeys_)
179+
{
180+
DataStruct::Array::DynArray<Node*> _arrpNodes;
181+
DataStruct::Array::DynArray<InnerTree::Pair>_arrTreePairs = m_nNodeMappingTree.GetArray();
182+
for (int _i = 0; _i < _arrTreePairs.GetSize(); _i++)
183+
{
184+
_arrpNodes.Add(_arrTreePairs[_i].m_nValue);
185+
_arrpNodes[_i]->Reset();
186+
}
187+
188+
int _nTime = 0;
189+
// 对于图中所有节点执行迭代处理
190+
for (int _i = 0; _i < arrKeys_.GetSize(); _i++)
191+
{
192+
InnerTree::Node* _pTreeNode = m_nNodeMappingTree.Search(arrKeys_[_i]);
193+
if (_pTreeNode == nullptr
194+
|| _pTreeNode->GetPair().m_nValue == nullptr)
195+
{
196+
throw "some key cannot relating to graph node";
197+
}
198+
199+
Node* _pNode = _pTreeNode->GetPair().m_nValue;
200+
// 未访问节点才执行迭代处理
201+
if (_pNode->m_nState == State::UnVisit)
202+
{
203+
Visit(_pNode, _nTime);
204+
}
205+
}
206+
207+
return _arrpNodes;
208+
}
209+
176210
template<typename Key, typename Value>
177211
void DepthFirstVisit<Key, Value>::Visit(Node* pNode_, int& nTime_)
178212
{

‎Algorithm/Graph/StrongConnectGraph.h‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
// Author : XuBenHao
2+
// Version : 1.0.0
3+
// Mail : xbh370970843@163.com
4+
// Copyright : XuBenHao 2020 - 2030
5+
6+
#ifndef AILIB_ALGORITHM_GRAPH_STRONGCONNECTGRAPH_H
7+
#define AILIB_ALGORITHM_GRAPH_STRONGCONNECTGRAPH_H
8+
#include "..\..\stdafx.h"
9+
#include "..\..\DataStruct\Graph\Graph.h"
10+
#include "DepthFirstVisit.h"
11+
#include "ReverseGraph.h"
12+
13+
namespace AlLib
14+
{
15+
namespace Algorithm
16+
{
17+
namespace Graph
18+
{
19+
template<typename Key, typename Value>
20+
class StrongConnectGraph
21+
{
22+
public:
23+
typename typedef DataStruct::GraphStruct::Graph<Key, Value> InnerGraph;
24+
StrongConnectGraph(const InnerGraph& nGraph_);
25+
~StrongConnectGraph();
26+
27+
DataStruct::Array::DynArray<typename DepthFirstVisit<Key, Value>::Node*> Run();
28+
private:
29+
StrongConnectGraph(const StrongConnectGraph& nSCG_) = default;
30+
StrongConnectGraph& operator=(const StrongConnectGraph& nSCG_) = default;
31+
private:
32+
const InnerGraph& m_nGraph;
33+
InnerGraph* m_pReverseGraph;
34+
typename DepthFirstVisit<Key, Value>* m_pDepthFirstVisit;
35+
};
36+
37+
template<typename Key, typename Value>
38+
StrongConnectGraph<Key, Value>::StrongConnectGraph(const InnerGraph& nGraph_)
39+
: m_nGraph(nGraph_), m_pReverseGraph(nullptr), m_pDepthFirstVisit(nullptr)
40+
{
41+
42+
}
43+
44+
template<typename Key, typename Value>
45+
StrongConnectGraph<Key, Value>::~StrongConnectGraph()
46+
{
47+
if (m_pReverseGraph != nullptr)
48+
{
49+
delete m_pReverseGraph;
50+
m_pReverseGraph = nullptr;
51+
}
52+
53+
if (m_pDepthFirstVisit == nullptr)
54+
{
55+
delete m_pDepthFirstVisit;
56+
m_pDepthFirstVisit = nullptr;
57+
}
58+
}
59+
60+
template<typename Key, typename Value>
61+
DataStruct::Array::DynArray<typename DepthFirstVisit<Key, Value>::Node*> StrongConnectGraph<Key, Value>::Run()
62+
{
63+
DepthFirstVisit<Key, Value> _alDepthFirstVisit(m_nGraph);
64+
DataStruct::Array::DynArray<typename DepthFirstVisit<Key, Value>::Node*> _arrNodes = _alDepthFirstVisit.Run();
65+
_arrNodes.Sort([](typename DepthFirstVisit<Key, Value>::Node* pNode1_, typename DepthFirstVisit<Key, Value>::Node* pNode2_)->int
66+
{
67+
int _nRet = pNode1_->GetLastVisitTime() - pNode2_->GetLastVisitTime();
68+
if (_nRet > 0)
69+
{
70+
return -1;
71+
}
72+
else if (_nRet < 0)
73+
{
74+
return 1;
75+
}
76+
else
77+
{
78+
return 0;
79+
}
80+
});
81+
82+
DataStruct::Array::DynArray<Key> _arrKeys;
83+
for (int _i = 0; _i < _arrNodes.GetSize(); _i++)
84+
{
85+
typename InnerGraph::Pair _nPair = _arrNodes[_i]->GetGraphNode()->GetPair();
86+
_arrKeys.Add(_nPair.m_nKey);
87+
}
88+
89+
ReverseGraph<Key, Value> _alReverseGraph(m_nGraph);
90+
if (m_pReverseGraph != nullptr)
91+
{
92+
delete m_pReverseGraph;
93+
m_pReverseGraph = nullptr;
94+
}
95+
96+
if (m_pDepthFirstVisit == nullptr)
97+
{
98+
delete m_pDepthFirstVisit;
99+
m_pDepthFirstVisit = nullptr;
100+
}
101+
102+
try
103+
{
104+
m_pReverseGraph = new InnerGraph(_alReverseGraph.Run());
105+
m_pDepthFirstVisit = new DepthFirstVisit<Key, Value>(*m_pReverseGraph);
106+
}
107+
catch (...)
108+
{
109+
throw "out of memory";
110+
m_pReverseGraph = nullptr;
111+
m_pDepthFirstVisit = nullptr;
112+
}
113+
114+
return m_pDepthFirstVisit->Run(_arrKeys);
115+
}
116+
}
117+
}
118+
}
119+
120+
#endif

0 commit comments

Comments
 (0)