БлогNot. Топологическая сортировка вершин графа

Топологическая сортировка вершин графа

Топологическая сортировка вершин графа с направленными рёбрами (ориентированного) позволяет упорядочить вершины в частичном порядке, заданном последовательностями обхода графа по рёбрам.

Программка ниже реализует алгоритм топологической сортировки для консоли Visual Studio и проверяет его на графе Мозера из этой заметки, только все рёбра сделаны направленными от вершины с меньшим номером к вершине с большим.

Граф описан простым классом Graph, построенным на основе списков смежности.

#include <iostream> 
#include <list> 
#include <stack> 
using namespace std;

class Graph {
 int V; //вершин
 list <int> *adj; //список смежности вершин
 void topologicalSortUtil (int v, bool visited[], stack <int> &Stack);
public:
 Graph(int V);
 void addEdge(int v, int w); //добавить ребро
 void topologicalSort();
};

Graph::Graph(int V) {
 this->V = V;
 adj = new list <int> [V];
}

void Graph::addEdge(int v, int w) {
 adj[v].push_back(w);
}

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) {
 visited[v] = true;
 list<int>::iterator i;
 for (i = adj[v].begin(); i != adj[v].end(); ++i)
  if (!visited[*i])
   topologicalSortUtil(*i, visited, Stack);
 Stack.push(v);
}

void Graph::topologicalSort() {
 stack<int> Stack;
 bool *visited = new bool[V];
 for (int i = 0; i < V; i++) visited[i] = false; //все метим как непосещенные
 for (int i = 0; i < V; i++)
  if (visited[i] == false)
   topologicalSortUtil(i, visited, Stack);
 while (Stack.empty() == false) {
  cout << Stack.top() << " ";
  Stack.pop();
 }
}

int main() {
 Graph g(7);
 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 4); g.addEdge(0, 5);
 g.addEdge(1, 2); g.addEdge(1, 3);
 g.addEdge(2, 3);
 g.addEdge(3, 6);
 g.addEdge(4, 5); g.addEdge(4, 6);
 g.addEdge(5, 6);
 cout << "Topological Sorting" << endl;
 g.topologicalSort();

 Graph g2(8);
 g2.addEdge(1, 4); g2.addEdge(1, 6); 
 g2.addEdge(2, 7);
 g2.addEdge(3, 7); g2.addEdge(3, 4);
 g2.addEdge(4, 5);
 g2.addEdge(7, 0); g2.addEdge(7, 5); g2.addEdge(7, 6);
 cout << endl << "Topological Sorting, test 2" << endl;
 g2.topologicalSort();

 cin.get(); return 0;
}

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

второй граф из Вики
второй граф из Вики

27.12.2019, 15:06 [1872 просмотра]


теги: c++ список алгоритм математика

К этой статье пока нет комментариев, Ваш будет первым