地图C 中地图的有效循环

Question

我试图通过地图数据结构找到一个有效的循环。

地图结构映射以下整数：

1 2, 2 3, 3 1, 4 1, 4 5, 5 3, 5 6, 5 7, 5 8, 6 4, 7 6, 8 9, 9 10

生成的地图看起来如下：

1| 2   
2| 3   
3| 1   
4| 1   5   
5| 3   6   7   8   
6| 4   
7| 6   
8| 9   
9| 10
Start : 4
Result : 
1(1) 2(2) 5(1) 3(2) 6(2) 7(2) 8(2)

任何人都可以建议如何有效地循环（可能是递归方法），以便考虑到第4个开始，结果将为

1(1), 2(2), 5(1), 3(2), 6(2), 7(2), 8(2), 9(3), 10(4)

因此，这个想法是将每个内部键作为一个外部键，从给定的外键开始。例如，使用外部4，内键为5和1。因此，将5和1用作外部键以获得内键（3 6 7 8）和（2），该过程应继续将内键映射到外键。应按照"跳跃"保留运行的总数。因此，它可能解决了递归问题，而不是循环。

如果您到达起点，则该过程应停止。

从第44行开始的循环，仅执行以上，最多两个级别，这是不足的。

#include <iostream>
#include <map>
#include <sstream>
int digit_count(int number) {
  int digits = 0;
  if (number < 0) digits = 1; // remove this line if '-' counts as a digit
  while (number) {
      number /= 10;
      digits++;
  }
  return digits;
}
int main() {
  int v1, v2;
  std::map< int, std::map< int, int> > m;
  std::istringstream  stm {"1 2  2 3  3 1  4 1  4 5  5 3  5 6  5 7  5 8  6 4  7 6  8 9  9 10"};
  while (stm >> v1 >> v2) {
    m[v1];
    m[v1][v2] = 1;
  }
  std::cout << "Map layout " << "n";
  std::string ss = "";
  int dc = digit_count(m.rbegin()->first); // equals max number
  for (const auto & p : m) {
    std::cout << p.first << ss.append(" ",  (dc - digit_count(p.first))) << "| ";
    for (const auto & val : p.second)
      std::cout << val.first << "   ";
    ss = "";
    std::cout << "n";
  }
  int start {4};
  std::cout << "nStart : " << start << "n";
  std::cout << "Result : " << "n";
  // efficient loop
  for (const auto & e : m[start]) {
    std::cout << e.first << "(" << e.second << ") ";
    for (const auto & x : m[e.first])
      std::cout << x.first << "(" << (e.second + x.second) << ") ";
  }
  std::cout << "n";
  return 0;
}

任何帮助都将不胜感激。

Answer 1

花了我一段时间，但是我已经回答了自己的问题，并认为我会更新帖子。我想到解决方案的唯一方法是创建递归功能。我认为循环无法实现。我没有选择Dijkstra的算法，因为没有权重要考虑，并且此递归函数的结果是对红色黑树的输入，其中红色黑树的每个节点都有Hash表（unordered_map）。因此，在合并的红色黑树/哈希表上查询的结果是log n，以找到最短路径。正如您可以从下面看到的那样，问题是提供输入，这是递归且效率低下的。

#include <iostream>
#include <map>
#include <sstream>
#include <set>
#include <vector>
#include <fstream>
int digit_count(int number) {
  int digits = 0;
  if (number < 0) digits = 1; // remove this line if '-' counts as a digit
  while (number) {
      number /= 10;
      digits++;
  }
  return digits;
}
struct vertex {
  int point;
  mutable bool visited{false};
  int id; 
};
void clear_visited(std::map<int, vertex>& verteces) {
  for (const auto & e : verteces) {
    e.second.visited = false;
  }
}
void traverse_graph(std::map<int, vertex>& verteces, const vertex & v, std::map< vertex, std::map< vertex, int> >& graph, int& counter) {
  if (verteces[v.id].visited)
    return;
  ++counter;
  verteces[v.id].visited = true;
  std::cout << v.point << "(" << counter << ") ";
  for (const auto & e : graph[v]) {
    traverse_graph(verteces, e.first, graph, counter);
  }  
}
void start_traverse_graph(std::map<int, vertex>& verteces, const vertex & v, std::map< vertex, std::map< vertex, int> >& graph) {
  if (verteces[v.id].visited)
    return;
  verteces[v.id].visited = true;
  for (const auto & e : graph[v]) {
    int counter{0};
    clear_visited(verteces);
    verteces[v.id].visited = true;
    traverse_graph(verteces, e.first, graph, counter);
  } 
}
bool operator<(vertex a, vertex b) { return a.point < b.point; }
int main (int argc, char *argv[]) {
  vertex v1, v2;
  std::map< vertex, std::map< vertex, int> > m;
  std::istringstream  stm {"1 2  2 3  3 1  4 1  4 5  5 3  5 6  5 7  5 8  6 4  7 6  8 9  9 10"};
  std::set<vertex> vertecesSet;
  std::map<int, vertex> verteces;
  while (stm >> v1.point >> v2.point) {
    v1.id = v1.point;
    v2.id = v2.point;
    m[v1];
    m[v1][v2] = 1;
    vertecesSet.insert({v1.point, false, v1.point});
    vertecesSet.insert({v2.point, false, v2.point});
  }
  for(auto & el : vertecesSet)
    verteces[el.id] = std::move(el); // dont need set objects anymore so move them
  std::cout << "Map layout " << "n";
  std::string ss = "";
  int dc = digit_count(m.rbegin()->first.point); // equals max number
  for (const auto & p : m) {
    std::cout << p.first.point << ss.append(" ",  (dc - digit_count(p.first.point))) << "| ";
    for (const auto & val : p.second)
      std::cout << val.first.point << "  ";
    ss = "";
    std::cout << "n";
  }
  vertex start {5,false,5};
  std::cout << "nStart : " << start.point << "n";
  start_traverse_graph( verteces, start, m);
  std::cout << "n";
  return 0;
}