Переполнение стека сортировки графов

Question

Переполнение стека сортировки графов

Итак, у меня проблема с домашним заданием:

Позволять G быть ориентированным графом на n Вершины.

Вызов G сортируется, если вершины могут быть четко пронумерованы от 1 в n (нет двух вершин с одинаковым номером), так что каждая вершина с входящими ребрами имеет по крайней мере один предшественник с меньшим номером. Например, пусть NUM(v) быть номером, присвоенным вершине v и рассмотрим вершину x с входящими ребрами из трех других вершин r, y, а также z, затем NUM(x) должен быть больше, чем хотя бы один из NUM(r), NUM(y), а также NUM(z),

Кроме того, алгоритм должен быть линейным; O(|V|+|E|),

Обход графа достаточно прост, но я понятия не имею, как проверить родителей вершины, чтобы увидеть, является ли число любой из родителей ниже, чем у ребенка.

Как мне сохранить ссылку на родителей вершины, на которой я работаю?

Следующие списки смежности являются входными файлами (просто образцы реальных тестовых случаев имеют около 8 тыс. Вершин).

1->2
2->3
3->1

Is not Sortable.

1->2
2->3
3->4
4->2

Is Sortable.

Проблема может быть решена в C ++ / C, и я выбрал C ++ для использования STL.

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

1

c++graph theory

Решение

Другие решения

Возьми два! Это O (| V | + | E |).

GCC 4.7.3: g ++ -Wall -Wextra -std = c ++ 0x sortable-graph.cpp

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

std::string trim(const std::string& str) {
std::string s;
std::stringstream ss(str);
ss >> s;
return s;
}

using edges = std::vector<std::pair<int, int>>;

void read(std::istream& is, edges& E, int& max) {
std::map<std::string, int> labels;
max = -1;

// Assume input is a list of edge definitions, one per line. Each line is:
// "label -> label" where white space is optional, "->" is a literal, and
// "label" does not contain "->" or white space.

// This can be vastly simplified if we can assume sensible int labels.

std::string l;
while (std::getline(is, l)) {
// Parse the labels.
const auto n = l.find("->");
const auto lhs = trim(l.substr(0, n));
const auto rhs = trim(l.substr(n + 2));

// Convert the labels to ints.
auto i = labels.find(lhs);
if (i == labels.end()) { labels[lhs] = ++max; }
auto j = labels.find(rhs);
if (j == labels.end()) { labels[rhs] = ++max; }

// Remember the edge.
E.push_back({labels[lhs], labels[rhs]});
}
}

bool isSortable(const edges& E, int max) {
std::vector<int> num(max+1, max+1);
for (const auto& e : E) {
num[e.second] = std::min(e.first, num[e.second]);
}

for (int i = 0; i < num.size(); ++i) {
if (num[i] != max + 1 && i <= num[i]) { return false; }
}

return true;
}

int main() {
edges E;
int max;
read(std::cin, E, max);
const auto b = isSortable(E, max);

std::cout << (b ? "Is Sortable.\n" : "Is not Sortable.\n");
}

0

Источник

Accepted Answer

Будет ли это сделать это?

Создать матрицу смежности. Если row указывает на col, а затем положить 1
там.
Сканирование каждого col к первому 1, Если col <знак равно row затем fail,
Иначе, pass,

Вот таблицы для ваших двух примеров:

Если вас беспокоит пространство, потому что оно должно обрабатывать 8k вершин, то вы можете использовать разреженное представление, если знаете, что входные данные редкие. Но на самом деле, я думаю, что 64 млн. Целых не должны вызывать беспокойство.

GCC 4.7.3: g ++ -Wall -Wextra -std = c ++ 0x sortable-graph.cpp

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

std::string trim(const std::string& str) {
std::string s;
std::stringstream ss(str);
ss >> s;
return s;
}

using graph = std::vector<std::vector<int>>;

graph read(std::istream& is) {
graph G;
std::vector<std::pair<int, int>> edges;
std::map<std::string, int> labels;
int max = -1;

// Assume input is a list of edge definitions, one per line. Each line is:
// "label -> label" where white space is optional, "->" is a literal, and
// "label" does not contain "->" or white space.

// This can be vastly simplified if we can assume sensible int labels.

std::string l;
while (std::getline(is, l)) {
// Parse the labels.
const auto n = l.find("->");
const auto lhs = trim(l.substr(0, n));
const auto rhs = trim(l.substr(n + 2));

// Convert the labels to ints.
auto i = labels.find(lhs);
if (i == labels.end()) { labels[lhs] = ++max; }
auto j = labels.find(rhs);
if (j == labels.end()) { labels[rhs] = ++max; }

// Remember the edge.
edges.push_back({labels[lhs], labels[rhs]});
}

// Resize the adjacency matrix.
G.resize(max+1);
for (auto& v : G) { v.resize(max+1); }

// Mark the  edges.
for (const auto& e : edges) { G[e.first][e.second] = 1; }

return G;
}

bool isSortable(const graph& G) {
const int s = G.size();
for (int col = 0; col < s; ++col) {
for (int row = 0; row < s; ++row) {
if (G[row][col] == 1) {
if (col <= row) { return false; }
break;
}
}
}
return true;
}

void print(std::ostream& os, const graph& G) {
const int s = G.size();
for (int row = 0; row < s; ++row) {
for (int col = 0; col < s; ++col) {
os << G[row][col] << " ";
}
os << "\n";
}
}

int main() {
const auto G = read(std::cin);
print(std::cout, G);
const auto b = isSortable(G);

std::cout << (b ? "Is Sortable.\n" : "Is not Sortable.\n");
}

Теперь, когда я смотрю на это, я думаю, что это O (V ^ 2).

0