Graph Sortability C++

Question

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

Пусть G ориентированный граф на n вершин.

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

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

---

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

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

---

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

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

Is not Sortable. 

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

Is Sortable. 

---

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

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

Answer 1

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

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

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

1 2 3 
1 0 1 0 
2 0 0 1 
3 1 0 0 

    1 2 3 4 
1 0 1 0 0 
2 0 0 1 0 
3 0 0 0 1 
4 0 1 0 0 

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

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).

Answer 2

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

GCC 4.7.3: г ++ -Wall -Wextra -std = C++ 0x Сортируемый-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"); 
}