devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

有向图找环的递归/非递归算法_有向图邻接矩阵查询所有的环

作者：不正经 | 2024-02-06 20:54:16

赞

踩

有向图邻接矩阵查询所有的环

参考网址：有向图找环_c语言有向图里面找环-CSDN博客

实验数据

算法运行结果

递归 + 邻接矩阵 

参数：

  • map，图的邻接表；
  • visit, 记录每一个点的访问状态；
  • path, 已遍历的点列表；
  • m,当前遍历的点，即在path的索引位置；
  • k, 起始遍历点的点索引，即对应map的行
  • fun，回调函数，当找到一个环时调用，回调函数的参数表示path中环的起点和终点的位置索引
  1. //递归算法
  2. //优点：结构简单，缺点：递归太深容易爆栈
  3. void route_searching1(Eigen::MatrixXi& map, std::vector<int>& visit, std::vector<int>&path, int& m, int k, std::function<void(int,int)>fun){
  4.     visit[k]=1;
  5.     //正在访问
  6.     path[m++]=k;
  7.     for(int i=0;i<map.cols();i++){
  8.         if(map(k,i)==1){
  9.             //2个点之间有边
  10.             if(visit[i]==0){
  11.                 route_searching1(map, visit, path, m, i, fun);
  12.                 //递归去访问
  13.             }
  14.             if(visit[i]==1){
  15.                 //出现环 打印出来
  16.                 for(int j=m-1;;j--){
  17.                     if(path[j]==i){
  18.                         fun(j, m-1);
  19.                         break;
  20.                     }
  21.                 }
  22.             }
  23.             //表示当前点访问过
  24.             if(visit[i]==-1)
  25.             {
  26.                 continue;
  27.             }
  28.         }
  29.     }
  30.     visit[k]=-1;
  31.     //访问结束
  32.     m--;
  33. }

非递归 + 邻接矩阵 

参数：

  • map，图的邻接表；
  • visit, 记录每一个点的访问状态；
  • fun，回调函数，当找到一个环时调用，回调函数的参数表示path，以及环的起点和终点的位置索引
  1.  
  2. //使用栈，非递归
  3. //优点：不会爆栈
  4. void route_searching2(Eigen::MatrixXi& map, std::vector<int>& visit, std::function<void(std::vector<int>&,int,int)>fun){
  5.     std::vector<int> path(map.rows(),0);
  6.     //路径
  7.     int m = 0;
  8.     //路径中当前位置
  9.     std::vector<std::pair<int,int>>stack;
  10.     //栈
  11.  
  12.     for(int i=0;i<map.rows();i++){
  13.         stack.push_back({i, m});
  14.  
  15.         while(stack.size()){
  16.             std::pair<int,int> pair = stack.back();
  17.             stack.pop_back();
  18.  
  19.             //回溯（将当前点后面的路径设置为已访问过）
  20.             while(pair.second < m){
  21.                 visit[path[--m]] = -1;
  22.             }
  23.  
  24.             int id =  pair.first;
  25.             if(visit[id]==0){
  26.                 //未访问
  27.                 path[m++] = id;
  28.                 //添加路径
  29.                 visit[id] = 1;
  30.                 //正在访问
  31.                 //下一个点（有可能有多个）
  32.                 for(int j = 0; j < map.cols(); ++j){
  33.                     if(map(id,j)){
  34.                         stack.push_back({j, m});
  35.                     }
  36.                 }
  37.             }
  38.             else if(visit[id]==1){
  39.                 //找到环
  40.                 for(int j=m-1;;j--){
  41.                     if(path[j]==id){
  42.                         fun(path, j, m-1);
  43.                         break;
  44.                     }
  45.                 }
  46.             }
  47.             else if(visit[id]==-1){
  48.                 //已访问过
  49.                 continue;
  50.             }
  51.         }
  52.         //清空路径并设置已访问
  53.         while(m){
  54.             visit[path[--m]] = -1;
  55.         }
  56.     }
  57. }

非递归+邻接表

参数：

  • n：点的个数
  • adjacency_list、first,、next,：邻接表
out：输出
  1. struct STACK {
  2.     int idx;
  3.     int m;
  4. };
  5.  
  6. //使用栈，非递归
  7. //优点：不会爆栈,内存占用少
  8.  
  9. void route_searching3(int n, std::vector<std::pair<int, int>>&adjacency_list,std::vector<int>&first,std::vector<int>&next, std::function<void(int*, int, int)>fun) {
  10.     std::vector<int> visit(n, 0);
  11.     std::vector<int> path(n, -1);
  12.     int m = 0;
  13.     //路径中当前位置
  14.     std::vector<STACK>stack;
  15.     //栈
  16.  
  17.     for (int i = 0; i < n; i++) {
  18.         if (visit[i] == -1)
  19.             continue;
  20.  
  21.         stack.push_back({ i, m });
  22.  
  23.         while (stack.size()) {
  24.             STACK cur_pt = stack.back();
  25.             stack.pop_back();
  26.  
  27.             //回溯（将当前点后面的路径设置为已访问过）
  28.             while (cur_pt.m < m) {
  29.                 visit[path[--m]] = -1;
  30.             }
  31.  
  32.             int idx = cur_pt.idx;
  33.             if (visit[idx] == 0) {
  34.                 //未访问
  35.                 path[m++] = cur_pt.idx;
  36.                 //添加路径
  37.                 visit[idx] = 1;
  38.                 //正在访问
  39.  
  40.                 int next_id = first[idx];
  41.                 while (next_id != -1) {
  42.                     stack.push_back({ adjacency_list[next_id].second, m });
  43.                     next_id = next[next_id];
  44.                 }
  45.             }
  46.             else if (visit[idx] == 1) {
  47.                 //找到环
  48.                 for (int j = m - 1;; j--) {
  49.                     if (path[j] == idx) {
  50.                         fun(path.data(), j, m-1);
  51.                         break;
  52.                     }
  53.                 }
  54.             }
  55.             else if (visit[idx] == -1) {
  56.                 //已访问过
  57.                 continue;
  58.             }
  59.         }
  60.         while (m) {
  61.             visit[path[--m]] = -1;
  62.         }
  63.     }
  64. }

QT完整代码

  1. //.h
  2. //数据结构
  3. struct holeEdge{
  4.     QPoint p1;
  5.     QPoint p2;
  6. };
  7.  
  8. //类成员变量
  9. std::vector<holeEdge*> circularNodes;//有向线段
  10. std::vector<std::vector<QPoint>>out_pts;//输出
  11. std::vector<QPoint>pts;
  12.  
  13. //.cpp
  14.  
  15. bool operator < (const QPoint& p1,const QPoint& p2){
  16.     if(p1.x() != p2.x())
  17.         return p1.x() < p2.x();
  18.     if(p1.y() != p2.y())
  19.         return p1.y() < p2.y();
  20.     return false;
  21. }
  22.  
  23. void Widget::getCircular(std::vector<holeEdge*> &circularNodes, int flag ){
  24.     //递归算法 + 邻接矩阵
  25.     if(flag == 0){
  26.         std::map<QPoint, int>pts_map;
  27.         std::vector<std::pair<int,int>>pairs;
  28.  
  29.         pts.clear();
  30.         for(auto& edge : circularNodes){
  31.             auto pair1 = pts_map.insert(std::make_pair(edge->p1, pts.size()));
  32.             if(pair1.second){
  33.                 pts.push_back(edge->p1);
  34.             }
  35.             auto pair2 = pts_map.insert(std::make_pair(edge->p2, pts.size()));
  36.             if(pair2.second){
  37.                 pts.push_back(edge->p2);
  38.             }
  39.             pairs.push_back(std::make_pair(pair1.first->second, pair2.first->second));
  40.         }
  41.  
  42.         Eigen::MatrixXi map(pts.size(),pts.size());//邻接矩阵
  43.         map.setZero();
  44.  
  45.         std::vector<int> visit(pts.size(),0);//访问标记 -1：已访问；0为访问；1正在访问
  46.         std::vector<int> path(pts.size(), -1);
  47.  
  48.         int m = 0;
  49.  
  50.         for(int i = 0; i < pairs.size(); ++i){
  51.             auto pair = pairs[i];
  52.             map(pair.first,pair.second) = 1;
  53.         }
  54.  
  55.         out_pts.clear();
  56.         for(int i=0;i<pts.size();i++){
  57.             if(visit[i]!=-1)
  58.                 route_searching1(map, visit, path, m, i,[&](int a, int b){
  59.                     std::vector<QPoint> pt;
  60.                     for(int j = a; j <= b; j++)
  61.                         pt.push_back(pts[path[j]]);
  62.                     out_pts.push_back(pt);
  63.                 });
  64.         }
  65.     }
  66.     //非递归 + 邻接矩阵
  67.     else if (flag == 1){
  68.         std::map<QPoint, int>pts_map;
  69.         std::vector<std::pair<int,int>>pairs;
  70.  
  71.         pts.clear();
  72.         for(auto& edge : circularNodes){
  73.             auto pair1 = pts_map.insert(std::make_pair(edge->p1, pts.size()));
  74.             if(pair1.second){
  75.                 pts.push_back(edge->p1);
  76.             }
  77.             auto pair2 = pts_map.insert(std::make_pair(edge->p2, pts.size()));
  78.             if(pair2.second){
  79.                 pts.push_back(edge->p2);
  80.             }
  81.             pairs.push_back(std::make_pair(pair1.first->second, pair2.first->second));
  82.         }
  83.  
  84.         Eigen::MatrixXi map(pts.size(),pts.size());//邻接矩阵
  85.         map.setZero();
  86.  
  87.         std::vector<int> visit(pts.size(),0);//访问标记 -1：已访问；0为访问；1正在访问
  88.         std::vector<int> path(pts.size(), -1);
  89.  
  90.         int m = 0;
  91.  
  92.         for(int i = 0; i < pairs.size(); ++i){
  93.             auto pair = pairs[i];
  94.             map(pair.first,pair.second) = 1;
  95.         }
  96.  
  97.         out_pts.clear();
  98.  
  99.         for(int i=0;i<pts.size();i++){
  100.             if(visit[i]!=-1)
  101.                 route_searching2(map, visit,[&](std::vector<int>&path, int a, int b){
  102.                     std::vector<QPoint> pt;
  103.                     for(int j = a; j <= b; j++)
  104.                         pt.push_back(pts[path[j]]);
  105.                     out_pts.push_back(pt);
  106.                 });
  107.         }
  108.     }
  109.     //非递归 + 邻接表
  110.     else if (flag == 2){
  111.         std::vector<std::vector<int>> points_out;
  112.  
  113.         std::map<QPoint, int>map_pt;
  114.         std::vector<QPoint>vertices;
  115.  
  116.         for (int i = 0; i < circularNodes.size(); i++) {
  117.             holeEdge* edge = circularNodes[i];
  118.             auto pair1 = map_pt.insert({ edge->p1, vertices.size()});
  119.             if (pair1.second) {
  120.                 vertices.push_back(edge->p1);
  121.             }
  122.             auto pair2 = map_pt.insert({ edge->p2, vertices.size() });
  123.             if (pair2.second) {
  124.                 vertices.push_back(edge->p2);
  125.             }
  126.         }
  127.  
  128.         std::vector<std::pair<int,int>>adjacency_list;//邻接表
  129.         std::vector<int>first(vertices.size(),-1);
  130.         std::vector<int>next(circularNodes.size(), -1);
  131.  
  132.         for (int i = 0; i < circularNodes.size(); i++) {
  133.             holeEdge* edge = circularNodes[i];
  134.             int u = map_pt[edge->p1];
  135.             int v = map_pt[edge->p2];
  136.             adjacency_list.push_back({u,v});
  137.  
  138.             int idx = adjacency_list.size() - 1;
  139.             next[idx] = first[u];
  140.             first[u] = idx;
  141.         }
  142.  
  143.         route_searching3(vertices.size(), adjacency_list, first, next, [&points_out](int *path, int start, int end) {
  144.             if (end - start >= 2) {
  145.                 std::vector<int>& vec = points_out.emplace_back();
  146.                 while (start <= end)
  147.                     vec.push_back(path[start++]);
  148.             }
  149.         });
  150.  
  151.         out_pts.clear();
  152.         for(auto& vec : points_out){
  153.             std::vector<QPoint> vec2;
  154.             for(int i : vec){
  155.                 vec2.push_back(vertices[i]);
  156.             }
  157.             out_pts.push_back(vec2);
  158.         }
  159.     }
  160. }
  161.  
  162.  
  163. Widget::Widget(QWidget *parent)
  164.     : QWidget(parent)
  165.     , ui(new Ui::Widget)
  166. {
  167.     ui->setupUi(this);
  168.  
  169.     //构建实验数据
  170.     //1
  171.     circularNodes.push_back(new holeEdge{QPoint(146,431),QPoint(270,461)});
  172.     circularNodes.push_back(new holeEdge{QPoint(270,461),QPoint(254,321)});
  173.     circularNodes.push_back(new holeEdge{QPoint(254,321),QPoint(163,338)});
  174.     circularNodes.push_back(new holeEdge{QPoint(163,338),QPoint(146,431)});
  175.  
  176.     //2
  177.     circularNodes.push_back(new holeEdge{QPoint(254,321),QPoint(309,388)});
  178.     circularNodes.push_back(new holeEdge{QPoint(309,388),QPoint(425,407)});
  179.     circularNodes.push_back(new holeEdge{QPoint(425,407),QPoint(465,337)});
  180.     circularNodes.push_back(new holeEdge{QPoint(465,337),QPoint(404,268)});
  181.     circularNodes.push_back(new holeEdge{QPoint(404,268),QPoint(254,321)});
  182.  
  183.     //3
  184.     circularNodes.push_back(new holeEdge{QPoint(254,321),QPoint(326,241)});
  185.     circularNodes.push_back(new holeEdge{QPoint(326,241),QPoint(308,158)});
  186.     circularNodes.push_back(new holeEdge{QPoint(308,158),QPoint(162,160)});
  187.     circularNodes.push_back(new holeEdge{QPoint(162,160),QPoint(125,255)});
  188.     circularNodes.push_back(new holeEdge{QPoint(125,255),QPoint(254,321)});
  189.  
  190.     //4
  191.     circularNodes.push_back(new holeEdge{QPoint(308,158),QPoint(370,94)});
  192.     circularNodes.push_back(new holeEdge{QPoint(370,94),QPoint(238,49)});
  193.     circularNodes.push_back(new holeEdge{QPoint(238,49),QPoint(197,118)});
  194.     circularNodes.push_back(new holeEdge{QPoint(197,118),QPoint(308,158)});
  195.  
  196.     //5
  197.     circularNodes.push_back(new holeEdge{QPoint(577,528),QPoint(712,515)});
  198.     circularNodes.push_back(new holeEdge{QPoint(712,515),QPoint(713,395)});
  199.     circularNodes.push_back(new holeEdge{QPoint(713,395),QPoint(577,528)});
  200.     circularNodes.push_back(new holeEdge{QPoint(569,406),QPoint(577,528)});
  201.  
  202.     //6
  203.     circularNodes.push_back(new holeEdge{QPoint(519,211),QPoint(625,298)});
  204.     circularNodes.push_back(new holeEdge{QPoint(625,298),QPoint(719,247)});
  205.  
  206.     //7
  207.     circularNodes.push_back(new holeEdge{QPoint(480,94),QPoint(574,131)});
  208.     circularNodes.push_back(new holeEdge{QPoint(574,131),QPoint(543,21)});
  209.     circularNodes.push_back(new holeEdge{QPoint(543,21),QPoint(480,94)});
  210.  
  211.     //getCircular(circularNodes, 0);
  212.     //getCircular(circularNodes, 1);
  213.     getCircular(circularNodes, 2);
  214. }
  215.  
  216. Widget::~Widget()
  217. {
  218.     delete ui;
  219. }
  220.  
  221.  
  222. void Widget::paintEvent(QPaintEvent *event)
  223. {
  224.     QPainter painter(this);
  225. #if 0
  226.     painter.setPen(Qt::red);
  227.     for(auto& edge : circularNodes){
  228.         painter.drawLine(edge->p1, edge->p2);
  229.     }
  230. #else
  231.     for(auto& path : out_pts){
  232.         painter.setBrush(QColor(rand()%255,rand()%255,rand()%255));
  233.         painter.drawPolygon(path.data(), path.size());
  234.     }
  235. #endif
  236. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/64531
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号