Найти все пути в диаграмме FlowChart?

Question

Найти все пути в диаграмме FlowChart?

Я сделал редактор диаграмм FlowChart на Java. Он создает потоковые диаграммы и соединяет их друг с другом и создает два массива. Один из них показывает соединительные узлы и линии, другой показывает соединительные элементы друг за другом. Я должен найти все способы, начиная с начала, а. Например, если у меня есть какой-то бриллиант для принятия решения, у меня есть два отдельных способа... Я хочу получить все это... Какие алгоритмы я должен использовать?

Редактировать 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

Это мой массив соединений.. Я пытаюсь найти все пути от запуска А до Е

Есть 2 пути

A->B->C-> Е

A->B->D-> Е

Я могу найти первый способ поиска в массиве слева направо. Если я вижу 1, я взял значение J и перейду к строке J-го элемента в i, создаю этот элемент 2 и начинаю searchign с [i,j+1], а если достигну E, отправляю результат.

Но здесь моя проблема заключается во втором поиске в первой строке, он не увидит 1 и пойдет во вторую строку, и есть первый элемент 1, но он ссылается на первую строку, и это будет цикл.

Также я пытался использовать DFS с использованием backtrack, но это не относится к отображению всех путей, только один путь.

И я попытался сделать все столбцы ниже до 0, если я основал 1 и начал seaching [i,j], но во втором поиске он ничего не увидит, и моя таблица 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("");
    }

}

}

Конец это вывод

Основано основано основано

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

2 означает посещение и изменение. Проблема в том, что вы видите в списке посещений, который добавляет

00, 01, 12, 24 это первый путь, но только 13,34 . Это потому, что я изменяю остаток массива на 0, чтобы не искать. Как я могу решить это? это должно 00,01,12,24 и 00,01 или 10,13,34.. Любая идея? И я не понимаю, это DFS или BFS? или что-то другое??

1

java algorithm depth-first-search flowchart

Источник

user295213 16 мар '10 в 22:09

2 ответа

Другие вопросы по тегам java algorithm depth-first-search flowchart

user226917 16 мар '10 в 22:33 2010-03-16 22:33 · Answer 1 · 2010-03-16 22:33

Алгоритм Флойда-Варшалла будет вычислять кратчайшие пути между всеми вершинами. Если вы не ищете кратчайшие пути, только все пути, вы можете достичь этого с помощью исчерпывающего поиска в глубину между двумя вашими узлами.

Я очень рекомендую посмотреть страницу алгоритмов графов в Википедии.

user188704 16 мар '10 в 22:18 2010-03-16 22:18 · Answer 2 · 2010-03-16 22:18

То, о чем вы думаете, очень похоже на анализ, используемый оптимизаторами компиляторов. Вместо значков блок-схем эти оптимизаторы работают с "базовыми блоками" инструкций на языке ассемблера. "Базовые блоки", как и значки потоковых диаграмм, определяются ребрами управления потоком, которые очерчивают границы как базовых блоков, так и значков потоковых диаграмм.

По этой причине я рекомендую вам взглянуть на литературу по компиляторам, чтобы получить идеи о том, как вы можете работать с диаграммой потоков. В частности, вы захотите прочитать о проблемах "анализа потоков данных", таких как "def-use" и "достижение определений".

В ответ на ваш вопрос вы можете реализовать алгоритм обхода ориентированного графа следующим образом:

/* 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 Design Compiler by Steven Muchnik.
Изображение книги Мучника http://ecx.images-amazon.com/images/I/51UmGvP2XDL._BO2,204,203,200_PIsitb-sticker-arrow-click,TopRight,35,-76_AA240_SH20_OU01_.jpg