Алгоритм Тарьяна

Алгоритм Тарьяна позволяет за линейное время найти компоненты сильной связности в графе, то есть, группы вершин, взаимно имеющих ориентированные пути из одной в другую.

Код основан на рекомендациях из Вики и примере графа с той же страницы. Описание алгоритма по-русски.

Классы в коде, проверявшемся в актуальной сборке Visual Studio 2019, шаблонны, а методы add_way и add_ways позволяют добавить для вершины одну или несколько связанных с ней вершин-"соседей". Сами вершины можно добавлять методом add_vertex шаблонного класса graph.

#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <vector>

struct basicTarjan {
 basicTarjan() {}
 basicTarjan(const basicTarjan&) = delete;
 basicTarjan& operator=(const basicTarjan&) = delete;
};

template <typename T> class tarjan;

template <typename T> class vertex : private basicTarjan { //Вершина
private:
 friend tarjan<T>;
 T data_;
 int index_ = -1;
 int lowlink_ = -1;
 bool on_stack_ = false;
 std::vector<vertex*> neighbours_; //Связанные вершины
public:
 explicit vertex(const T& t) : data_(t) {}
 void add_way(vertex* v) {
  neighbours_.push_back(v);
 }
 void add_ways(const std::initializer_list<vertex*>& vs) {
  neighbours_.insert(neighbours_.end(), vs);
 }
 const T& get_data() {
  return data_;
 }
};

template <typename T> class graph : private basicTarjan { //Граф
private:
 friend tarjan<T>;
 std::list<vertex<T>> vertexes_; //Вершины
public:
 vertex<T>* add_vertex(const T& t) {
  vertexes_.emplace_back(t);
  return &vertexes_.back();
 }
};

template <typename T> class tarjan : private basicTarjan { //Алгоритм
public:
 using component = std::vector<vertex<T>*>;
private:
 void strongconnect(vertex<T>* v) { //Поиск связей
  v->index_ = index_;
  v->lowlink_ = index_;
  ++index_;
  stack_.push_back(v);
  v->on_stack_ = true;
  for (auto w : v->neighbours_) {
   if (w->index_ == -1) {
    strongconnect(w);
    v->lowlink_ = std::min(v->lowlink_, w->lowlink_);
   }
   else if (w->on_stack_) {
    v->lowlink_ = std::min(v->lowlink_, w->index_);
   }
  }
  if (v->lowlink_ == v->index_) {
   strongly_connected_.push_back(component());
   component& c = strongly_connected_.back();
   for (;;) {
    auto w = stack_.back();
    stack_.pop_back();
    w->on_stack_ = false;
    c.push_back(w);
    if (w == v)
     break;
   }
  }
 }
 int index_ = 0;
 std::list<vertex<T>*> stack_;
 std::list<component> strongly_connected_;
public:
 std::list<component> run(graph<T>& graph) { //Основной метод
  index_ = 0;
  stack_.clear();
  strongly_connected_.clear();
  for (auto& v : graph.vertexes_) {
   if (v.index_ == -1)
    strongconnect(&v);
  }
  return strongly_connected_;
 }
};

template <typename T> void print_vector(const std::vector<vertex<T>*>& vec) {
 //Вывод вектора в консоль
 if (!vec.empty()) {
  auto i = vec.begin();
  std::cout << (*i)->get_data();
  for (++i; i != vec.end(); ++i)
   std::cout << ' ' << (*i)->get_data();
 }
 std::cout << '\n';
}

int main() {
 //Формирование теста
 graph <std::string> g;
 auto node1 = g.add_vertex("1"),
  node2 = g.add_vertex("2"),
  node3 = g.add_vertex("3"),
  node4 = g.add_vertex("4"),
  node5 = g.add_vertex("5"),
  node6 = g.add_vertex("6"),
  node7 = g.add_vertex("7"),
  node8 = g.add_vertex("8");
 node1->add_way(node2);
 node2->add_way(node3);
 node3->add_way(node1);
 node4->add_ways({ node2, node3, node5 });
 node5->add_ways({ node4, node6 });
 node6->add_ways({ node3, node7 });
 node7->add_way(node6);
 node8->add_ways({ node5, node7, node8 });
 //Запуск и результаты 
 tarjan <std::string> t;
 for (auto&& s : t.run(g)) print_vector(s);
 return 0;
}

Граф из примера

Вывод программы:

3 2 1
7 6
5 4
8

20.04.2022, 13:19 [949 просмотров]