主页 / 问题 / 752401
Accepted
NTP
Asked:2020-12-01 22:37:11 +0000 UTC2020-12-01 22:37:11 +0000 UTC

记录从一个图形顶点到另一个顶点的路径

  • 772

有一个有向图，你需要找到从它的一个顶点到另一个顶点的所有可能路径。我在网上找到了一个深度优先搜索的例子，但是它并没有寻找路径本身，而是寻找可能路径的数量，并且由于递归，我仍然无法弄清楚如何编写路径。所以我的问题是，如何做到这一点？在下面的代码中a - 邻接矩阵（布尔），visited- 访问数组（布尔），n- 矩阵大小，v- 起点，x- 终点，cnt- 可能路径的数量

procedure dfs(var a:TArray; var visited: Tmas; n, v, x: integer; var cnt: integer);
var i: integer;
begin
    if v = x then begin
        Inc(cnt);
        exit;
    end;

    visited[v] := true;

    for i := 1 to n do begin
        if a[v, i] and not visited[i] then begin
            Route[v][i] := v;
            dfs(a, visited, n, i, x, cnt);
        end;
    end;

    visited[v] := false;
end;
delphi

1 个回答

  1. Best Answer

    没有什么可检查的，手头没有 IDE 或测试数据。但是根据评论的结果，请看以下方向：

    visited- 由图顶点数组成的整数数组。0- 顶点没有被访问过，否则数字是路径中的序号1..M，其中是路径M的长度。在函数参数中我们输入递归深度z，这是路径的每一步。

    procedure dfs(var a:TArray; var visited: Tmas; n, v, x: integer; 
              var cnt: integer; 
              z : integer = 1);
var i: integer;

     procedure printPath();
     var k,m : integer;  
     begin

        for k := 1 to z do begin              // количество узлов в пути 
           for m := 1 to n do begin           // длина visited, число вершин
               if visited[m] = k then begin   // нашли номер шага пути 
                  write('->', m);           // номер вершины
                  break;
               end;
           end;
        end;
        writeln();
     end;

begin 
    if v = x then begin             // дошли в конечную точку Х
        Inc(cnt);                   // увеличили число путей
        printPath();                // напечатали путь
        exit;                       // вернулись к предыдущему шагу пути
    end;

    visited[v] := z;                // сейчас мы посещаем вершину v

    for i := 1 to n do begin                     // просматриваем другие точки
        if a[v, i] and                           // если i-я и текущая связаны
           (visited[i] = 0) then begin           // и i-я еще не посещалась  
            dfs(a, visited, n, i, x, cnt, z+1);  // то идем в i-ю
        end;
    end;

    visited[v] := 0;     // возвращаемся к предыдущему шагу пути
                         // выходим из рекурсии, 
                         // освобождая вершину v        
end;

    该算法以这样一种方式工作，即每个新的递归调用都会转换到下一个深度点。当我们遇到新一轮的递归时，我们过去只记得给定的顶点被访问过。现在我们在那里写下一个数字，通知它被访问了 step z。
    当我们到达所需的点时，我们的路径就完成了，并且在数组visitedy 中，它以必须通过顶点的顺序写入才能到达这里。数组索引就是这个顶点，值就是步数。

    现在剩下的就是绘制路径了。我们知道它的长度等于当前的长度z（即我们进行了多少次深度转换）。所以我们从 1 循环到 z 以在数组中找到对应的值。并输出顶部（索引）。

    PS：算法本身就像毡靴一样简单。如果你对递归有困难，那么在纸上画一个简单的图形，画出数据数组，然后用铅笔在一张纸上解决这个算法。这将很快把所有东西放在它的位置。

    • 2

相关问题