找到流程图中的所有方法？

Question

我用 Java 做了一个流程图编辑器。它绘制流程图并将它们相互连接并创建两个数组。其中之一显示连接节点和线，另一张显示相互连接的元素。我必须找到从 Begin Two And 开始的所有方法。 例如，如果我有一些钻石可供决策，我有两种不同的方式..我想得到所有这些方式..我必须使用哪种算法？

编辑3：已解决 再次嗨，我自己解决了我的问题..这是我的代码..））

 public void search(){
  //  System.out.print(map.length);

for(i=0;i<map.length;i++)

    visit[i]=0;

    visit[0]=1;

    find(0,map.length-1,1);
}



  public void  find(int i,int d,int step){

for(int j=0;j<map.length;j++){
 System.out.println(">>"+i+"->"+j);
    if(visit[j]!=0 || map[i][j]==0)

        continue;

    if(j==d){
        visit[j]=step;
        OutputCycle();
      visit[j]=0;
        return;

    }
System.out.println(""+i+" to "+j);
    visit[j]=step;
    find(j,d,step+1);
    visit[j]=0;




}


  }
public void OutputCycle(){
    System.out.println("OUTPUT");

    for(k=0;k<visit.length;k++){

         for(int i=0;i<visit.length;i++){
             if(visit[i]==k+1){
                 System.out.print(i);
             }
         }
    }
    System.out.println();
}

编辑1：当我解决我的问题时，我解决了一部分，不，也有错误...这里我的问题更深入描述 ： 我有一个描述元素之间连接的数组

          j

       A  B  C  D  E 

    A  0  1  0  0  0 

    B  1  0  1  1  0 

i   C  0  1  0  0  1

    D  0  1  0  0  1

    E  0  0  1  1  0     

这是我的连接数组..我试图找到从A开始到E的所有方法

有2种方法

A->B->C->E

A->B ->D->E

我可以找到第一种从左到右搜索数组的方法。如果我看到 1，我就取出 J 的 walu e 并转到 i 中的第 J 个元素行，将该元素设置为 2 并从 [i,j+1] 开始搜索，如果到达 E，则发送结果。

但这里我的问题是在第一行的第二个搜索中它不会看到 1 并且会进入第二行并且有第一个元素 1 但它引用第一行并且它将是循环。

我还尝试将 DFS 与回溯一起使用，但它并不是指显示所有路径，而是仅显示一条路径。

如果我发现 1 并开始搜索 [i,j]，我尝试将下面的所有列都设置为 0，但在第二次搜索中它不会看到任何内容，并且我的 arry 表出现了一个空白表））。

我知道我错过了一件事，但我无法弄清楚..

编辑2：

现在我关闭了解决方案，但又出现了问题。我使用这段代码来计算矩阵的路径

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
*
* @author Meko
*/
public class Main {

List visited = new ArrayList();
List allObjects = new ArrayList();
int map[][] = {{3, 1, 0, 0, 0},
    {1, 0, 1, 1, 0},
    {0, 1, 0, 0, 3},
    {0, 1, 0, 0, 3},
    {0, 0, 1, 1, 0}};
int i, j, k;

public Main() {

    ShowArray();
    System.out.println();
    find(0, 0);
    System.out.println();
    result();
    System.out.println();
    afterFind();
    System.out.println();
}

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here

    new Main();

}

public void ShowArray() {

    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map.length; j++) {

            System.out.print(" " + map[i][j]);
        }
        System.out.println("");
    }


}

public void find(int sRow, int sCol) {


    for (i = sRow; i < map.length; i++) {
        for (j = sCol; j < map.length; j++) {


            if (map[i][j] == 1) {
                map[i][j] = 2;
                visited.add(" " + i + " " + j);
                for (k = i; k < map.length; k++) {
                    map[k][i] = 0;

                }
                find(j, i);
            } else if (map[i][j] == 3) {
                visited.add(" " + i + " " + j);
              for (k = i; k < map.length; k++) {
                    map[k][i] = 0;

                }
                System.out.println("Founded");
                map[i][j] = 2;
                find(0, 0);
            }
        }

    }
}

public void result() {
    System.out.println(visited);
}

public void afterFind() {

    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map.length; j++) {

            System.out.print(" " + map[i][j]);
        }
        System.out.println("");
    }

}

}

结束它的输出是

3 1 0 0 0
1 0 1 1 0
0 1 0 0 3
0 1 0 0 3
0 0 1 1 0

成立的 成立 创建

[ 0 0, 0 1, 1 2, 2 4, 1 3, 3 4]

0 2 0 0 0
0 0 2 2 0
0 0 0 0 2
0 0 0 0 2
0 0 0 0 0

2 表示已访问并更改。问题是正如您在已访问列表中看到的那样，它添加了

00 , 01 , 12, 24 这是第一个路径，但随后只有 13,34 。这是因为我将数组的其余部分更改为 0 以不搜索。我该如何解决这个问题？它必须是 00,01,12,24 和 00,01 或 10,13,34..有什么想法吗？ 我不知道这是 DFS 还是 BFS ？或者其他什么？

Answer 1

Floyd-Warshall 算法将计算所有顶点之间的最短路径。如果您不寻找最短路径，而只是寻找所有路径，则可以通过在两个节点之间进行详尽的深度优先搜索来实现此目的。

我强烈建议您查看图形算法的维基百科页面。

Answer 2

您所考虑的与编译器优化器使用的分析非常接近。这些优化器不是在流程图图标上工作，而是在汇编语言指令的“基本块”上工作。就像流程图图标一样，“基本块”由流程控制边缘定义，该边缘描绘了基本块和流程图图标的边界。

因此，我建议您查看编译器文献，以了解如何在流程图上进行操作。特别是，您将需要阅读有关“数据流分析”的内容，例如“定义使用”和“达到定义”问题。

为了回答您的问题，您可以实现有向图遍历算法，如下所示：

/* Marks all flowchart icons as "unvisited." */
for (int i = 0; i < nodes.Count(); i++):
   node[i].visited = false

/* Schedule the Start node for processing. */
node_queue.push(nodes.start_node())

/* Traverse the graph. */
while (node_queue.not_empty()):
    current_node = node_queue.pop_front()

    calculations_on_node(current_node)

    current_node.visited = true

    for (int i = 0; i < current_node.outgoing_edges.Count(); i++):
        edge  = current_node.outgoing_edges[i]
        if (!edge.destination_node.visited):
            node_queue.push_back(edge.destination_node)

您可以实现calculations_on_node来执行您想要的每个节点工作。

我建议您阅读一本关于编译器优化的优秀教科书，它是 Advanced Compiler Design and实施，作者：Steven Muchnik。