Подсчет узлов в наибольшем цикле матрицы смежности
В настоящее время я пишу программу с использованием неориентированного графика. Я представляю это, создавая матрицу смежности соединений.
if(adjacency_matrix[i][j] == 1){
//i and j have and edge between them
}
else{
//i and j are not connected
}
То, что я пытаюсь сделать, — это найти все узлы, к которым данный узел подключен (любой серией ребер). Я попытался написать функцию, которая делает это для данного узла и возвращает вектор, который содержит 1 или 0 в каждой точке вектора, определяемой тем, является ли узел доступным для данного узла любым путем в графе. Затем я хочу взять этот вектор и сложить в нем все значения, которые будут возвращать количество узлов, достижимых этим узлом. Затем я хочу взять все эти значения для каждого узла в графе и поместить их в вектор, а затем найти максимальное значение, которое будет представлять количество узлов в наибольшем цикле.
Моя проблема не в том, что я получаю ошибки с моим кодом определения функции (хотя я есть), а в том, что я понимаю, что пишу эту рекурсивную функцию неправильно, но не знаю, как изменить ее, чтобы удовлетворить мою потребность. Я включил свой код ниже, любое руководство будет высоко ценится.
Определение функции:
vector<int> get_conn_vect(int u, int conns, vector<vector<int>> vv, vector<int> seen)
{
seen.at(u) = 1;
while(v < conns)
{
if(seen.at(v) == 0 && vv.at(u).at(v) == 1)
{
get_conn_vect(v, conns, vv, seen);
v++;
}
else
{
v++;
}
}
return seen;
}
Звоните в main.cpp:
std::vector<int> conn_vect;
int sum_of_elems = 0;
for(int i = 0; i < num_nodes; i++)
{
std::vector<int> seen_vect(matrix.size());
sum_of_elems = 0;
seen_vect = get_conn_vect(i, num_conn, matrix, seen_vect);
conn_vect.push_back(sum_of_elems = std::accumulate(seen_vect.begin(), seen_vect.end(), 0));
}
Решение
Как говорится в комментарии Линси, вы копируете seen Vector при каждом вызове вашей рекурсивной функции, чтобы значение возвращалось обратно в ваш main функция имеет ровно одну ненулевую запись в индексе i, Вместо этого передайте ссылку (я также передал матрицу как ссылку на const, чтобы предотвратить ненужные копии):
void get_conn_vect(int u, const vector< vector<int> > &vv, vector<int> &seen)
{
seen.at(u) = 1;
// Assuming that vv is square.
for(int v = 0; v < vv.size(); ++v)
{
if(seen.at(v) == 0 && vv.at(u).at(v) == 1)
{
get_conn_vect(v, conns, vv, seen);
}
}
}
В конце рекурсии вектор, который вы изначально передали, содержит ненулевую запись для каждого узла, который подключен к узлу i,
Другое очень аккуратное решение, использующее другой подход, появляется, когда понимаешь, что записи (i,j) силы A^n матрицы смежности A Опишите количество путей, чтобы получить от узла i в узел j в точности n шаги. Следовательно, можно одновременно вычислять наборы связности всех узлов, просто складывая степени матрицы смежности. B = A + A^2 + ... + A^N, где N число узлов (путь между разными узлами не может быть длиннее). Чтобы получить количество узлов, подключенных к узлу i просто посчитайте количество ненулевых в iстолбец (или строка) B,
Другие решения
То, что вы пытаетесь сделать, называется «найти транзитивное замыкание». Алгоритм Флойда-Варшалла используется, чтобы найти это (хотя могут быть более новые, более быстрые, я не совсем в курсе этой темы).
Вот код, который вы можете использовать:
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
static const size_t NUM_NODES = 4;
// test case, four nodes, A, B, C, D
// A is connected to B which is connected to D
// C is not connected to anyone
// A B C D
unsigned int adjacency_matrix[NUM_NODES][NUM_NODES] =
{{1, 1, 0, 0},
{1, 1, 0, 1},
{0, 0, 1, 0},
{0, 1, 0, 1}};void Warshalls() {
size_t len = NUM_NODES;
for (size_t k=0; k<len; ++k) {
for (size_t i=0; i<len; ++i) {
for (size_t j=0; j<len; ++j) {
unsigned int& d = adjacency_matrix[i][j];
unsigned int& s1 = adjacency_matrix[i][k];
unsigned int& s2 = adjacency_matrix[k][j];
if (s1 != 0 && s2 != 0) {
unsigned int sum = s1 + s2;
if (d == 0 || d > sum) {
d = sum;
}
}
}
}
}
}
vector<size_t> GetNodes(size_t index) {
if (index >= NUM_NODES) { throw runtime_error("invalid index"); }
vector<size_t> ret;
for (size_t i=0; i<NUM_NODES; ++i) {
if (adjacency_matrix[index][i] != 0) {
ret.push_back(i);
}
}
return ret;
}
void PrintNodes(const vector<size_t>& nodes) {
for (auto i=nodes.begin(); i!=nodes.end(); ++i) {
cout << *i << endl;
}
}
int main() {
Warshalls();
// where can you get to from D
cout << "Possible destinations for D" << endl;
vector<size_t> nodes_reachable = GetNodes(3);
PrintNodes(nodes_reachable);
// where can you get from C
cout << "Possible destinations for C" << endl;
nodes_reachable = GetNodes(2);
PrintNodes(nodes_reachable);
return 0;
}