1

我目前正在使用无向图编写程序。我通过创建连接的邻接矩阵来表示这一点。

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));
}
4

2 回答 2

2

您正在尝试做的事情称为“找到传递闭包”。Floyd-Warshall 算法用于找到这个（尽管可能有更新、更快的算法，但我对这个主题并不是很了解）。

以下是一些您可以使用的代码：

#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;
}
于 2015-04-27T14:18:17.480 回答
1

正如 Linxi 的评论所说，您seen在每次调用递归函数时复制向量，以便返回给main函数的值在 index 处恰好有一个非零条目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);
        }
    }
}

在递归结束时，您最初传递的向量包含连接到 node 的每个节点的非零条目i。

一旦人们意识到邻接矩阵(i,j)的幂的条目描述了从一个节点到另一个节点的路径数量，就会出现另一种非常巧妙的解决方案。因此，可以通过简单地将邻接矩阵 的幂相加来同时计算所有节点的连接集，其中是节点的数量（不同节点之间的路径不能比这更长）。要获得连接到 node 的节点数，只需计算' 的第 ' 列（或行）中的非零数。A^nAijnB = A + A^2 + ... + A^NNiiB

于 2015-04-27T14:11:41.777 回答