BFS使用邻接列表遍历图中的所有路径 [英] BFS traversal of all paths in graph using adjacency list

问题描述

我目前正试图在使用邻接矩阵的图中遍历从源到目的地的所有路径。我一直试图以BFS的方式做到这一点。感谢您的帮助。我只有一条路。如何打印其他路径？

  public class AllPossiblePaths {
 static int v; 
 static ArrayList< Integer>形[]; 
 
 public AllPossiblePaths（int v）{
 this.v = v; 
 adj = new ArrayList [v]; 
 for（int i = 0; i  adj [i] = new ArrayList<>（）; 
 
 
 
 //将边添加到v 
 public static void addEdge（int u，int v）{
 adj [u] 。新增（v）; 
 
 
 public static void findpaths（int source，int destination）{
 LinkedList< ArrayList< Integer>> q = new LinkedList<>（）; 
布尔值visited [] = new boolean [v]; 
 
 LinkedList<整数> queue = new LinkedList< Integer>（）; 
 
 queue.add（source）; 
 visited [source] = true; 
 ArrayList<整数> localPath = new ArrayList<>（）; 
 while（！queue.isEmpty（））{
 //从队列中取出一个顶点并打印它
 int src = queue.poll（）; 
 if（！localPath.contains（src））{
 localPath.add（src）; 
} 
 if（src == destination）{
 System.out.println（localPath）; 
 localPath.remove（localPath.size（） -  1）; 
 visited [src] = false; 
} 
 
迭代器<整数> i = adj [src] .listIterator（）; 
 while（i.hasNext（））{
 int n = i.next（）; 
 if（！visited [n]）{
 queue.add（n）; 
} 
} 
} 
} 
} 
  

findPath ）或查找多个路径（ findAllPaths ）。查看评论：

  import java.util.ArrayList; 
 import java.util.Iterator; 
 import java.util.LinkedList; 
 import java.util.List; 
 
 public class AllPossiblePaths {
 
 private boolean [] visited; 
 //跟踪已包含在路径中的节点
 private boolean [] includedInPath; 
私人LinkedList<整数>队列; 
 private int numberOfNodes; 
私人列表< Integer> [] adj; 
 //找到你需要存储路径的路径
 private List< Integer> [] pathToNode; 
 
 public AllPossiblePaths（int numberOfNodes）{
 
 this.numberOfNodes = numberOfNodes; 
 adj = new ArrayList [numberOfNodes]; 
 pathToNode = new ArrayList [numberOfNodes]; （int i = 0; i< numberOfNodes; i ++）{
 adj [i] = new ArrayList<>（）; 
 
。 
 
 
 
 //将边添加到v 
 public AllPossiblePaths addEdge（int from，int to）{
 adj [from]。添加）; 
 //除非单向：//如果a连接到b 
 //比b应连接到
 adj [to] .add（from）; 
返回此; //可以方便地添加多条边
 
 $ b public void findPath（int source，int destination）{
 
 System.out.println（ - ----------单一路径搜索---------------）; 
 initializeSearch（source）; 
 
 while（！queue.isEmpty（））{
 //从队列中取出一个顶点并打印它
 int src = queue.poll（）; 
 visited [src] = true; 
 
 if（src == destination）{
 System.out.println（Path from + source +to
 + destination +： - + pathToNode [src] ）; 
休息; //找到目标后退出循环
} 
 
迭代器<整数> i = adj [src] .listIterator（）; 
 while（i.hasNext（））{
 int n = i.next（）; 
 if（！visited [n]&&！queue.contains（n））{
 queue.add（n）; 
 pathToNode [n] .addAll（pathToNode [src]）; 
 pathToNode [n] .add（src）; 
 
 
 
 
 $ b public void findAllpaths（int source，int destination）{
 
 System.out .println（----------- Multiple path search --------------）; 
 includedInPath = new boolean [numberOfNodes]; 
 initializeSearch（source）; 
 int pathCounter = 0; $！
 $ b while（！queue.isEmpty（））{
 $ while（！allVisited（）&&！queue.isEmpty（））{
 
从队列中取出一个顶点并打印它
 int src = queue.poll（）; 
 visited [src] = true; 
 
 if（src == destination）{
 
 System.out.println（Path +++ pathCounter +from+ source +to
 + destination +： - + pathToNode [src]）; 
 //标记包含在路径中的节点，所以它们不会被包含在任何其他路径中
 // 
（int i = 1; i< pathToNode [src]）。 size（）; i ++）{
 includedInPath [pathToNode [src] .get（i）] = true; 
} 
 initializeSearch（source）; //在重新启动
 break之前初始化; //找到目标后退出循环
} 
 
迭代器<整数> i = adj [src] .listIterator（）; 
 while（i.hasNext（））{
 int n = i.next（）; 
 if（！visited [n]&&！queue.contains（n）
&&！includedInPath [n] / *忽略路径中已存在的节点* /）{
 queue.add（n）; 
 pathToNode [n] .addAll（pathToNode [src]）; 
 pathToNode [n] .add（src）; 
 
 
 
 
 
 $ b private void initializeSearch（int source）{
 
 queue = new LinkedList<>（）; 
 queue.add（source）; 
 visited = new boolean [numberOfNodes]; （int i = 0; i< numberOfNodes; i ++）{
 pathToNode [i] = new ArrayList<>（）; 
 
 
 
 private boolean allVisited（）{
 
 for（boolean b：visited）{
 if（！b）return假; 
} 
返回true; 
 
 
  

要测试它，请考虑下图：

I am currently trying to traverse all paths from source to destination in a graph which uses adjacency matrix. I have been trying to do it in BFS way.Thanks for the help. I am getting only one path. How do I get to print other paths as well ?

public class AllPossiblePaths {
    static int v;
    static ArrayList<Integer> adj[];

    public AllPossiblePaths(int v) {
        this.v = v;
        adj = new ArrayList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public static void addEdge(int u, int v) {
        adj[u].add(v);
    }

    public static void findpaths(int source, int destination) {
        LinkedList<ArrayList<Integer>> q = new LinkedList<>();
        boolean visited[] = new boolean[v];

        LinkedList<Integer> queue = new LinkedList<Integer>();

        queue.add(source);
        visited[source] = true;
        ArrayList<Integer> localPath = new ArrayList<>();
        while (!queue.isEmpty()) {
            // Dequeue a vertex from queue and print it
            int src = queue.poll();
            if (!localPath.contains(src)) {
                localPath.add(src);
            }
            if (src == destination) {
                System.out.println(localPath);
                localPath.remove(localPath.size() - 1);
                visited[src] = false;
            }

            Iterator<Integer> i = adj[src].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    queue.add(n);
                }
            }
        }
    }
}

解决方案

Using the following class you can run a BFS to find a single path (findPath) or find multiple paths (findAllPaths). See comments:

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

public class AllPossiblePaths {

    private  boolean[] visited;
    //keep track of nodes already included in a path
    private  boolean[] includedInPath;
    private LinkedList<Integer> queue;
    private int numberOfNodes;
    private List<Integer>[] adj;
    //to find a path you need to store the path that lead to it
    private List<Integer>[] pathToNode;

    public AllPossiblePaths(int numberOfNodes) {

        this.numberOfNodes = numberOfNodes;
        adj = new ArrayList[numberOfNodes];
        pathToNode = new ArrayList[numberOfNodes];

        for (int i = 0; i < numberOfNodes; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    // add edge from u to v
    public AllPossiblePaths addEdge(int from, int to) {
        adj[from].add(to);
        //unless unidirectional: //if a is connected to b
        //than b should be connected to a
        adj[to].add(from);
        return this; //makes it convenient to add multiple edges
    }

    public void findPath(int source, int destination) {

        System.out.println("------------Single path search---------------");
        initializeSearch(source);

        while (!queue.isEmpty()) {
            // Dequeue a vertex from queue and print it
            int src = queue.poll();
            visited[src] = true;

            if (src == destination) {
                System.out.println("Path from "+source+" to "
                        + destination+ " :- "+ pathToNode[src]);
                break; //exit loop if target found
            }

            Iterator<Integer> i = adj[src].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (! visited[n] && ! queue.contains(n)) {
                    queue.add(n);
                    pathToNode[n].addAll(pathToNode[src]);
                    pathToNode[n].add(src);
                }
            }
        }
    }

    public void findAllpaths(int source, int destination) {

        System.out.println("-----------Multiple path search--------------");
        includedInPath = new boolean[numberOfNodes];
        initializeSearch(source);
        int pathCounter = 0;

        while(! allVisited() && !queue.isEmpty()) {

            while (!queue.isEmpty()) {
                // Dequeue a vertex from queue and print it
                int src = queue.poll();
                visited[src] = true;

                if (src == destination) {

                    System.out.println("Path " + ++pathCounter + " from "+source+" to "
                            + destination+ " :- "+ pathToNode[src]);
                    //mark nodes that are included in the path, so they will not be included
                    //in any other path
                    for(int i=1; i < pathToNode[src].size(); i++) {
                        includedInPath[pathToNode[src].get(i)] = true;
                    }
                    initializeSearch(source); //initialize before restarting
                    break; //exit loop if target found
                }

                Iterator<Integer> i = adj[src].listIterator();
                while (i.hasNext()) {
                    int n = i.next();
                    if (! visited[n] && ! queue.contains(n)
                            && ! includedInPath[n] /*ignore nodes already in a path*/) {
                        queue.add(n);
                        pathToNode[n].addAll(pathToNode[src]);
                        pathToNode[n].add(src);
                    }
                }
            }
        }
    }

    private void initializeSearch(int source) {

        queue = new LinkedList<>();
        queue.add(source);
        visited = new boolean[numberOfNodes];
        for (int i = 0; i < numberOfNodes; i++) {
            pathToNode[i]= new ArrayList<>();
        }
    }

    private boolean allVisited() {

        for( boolean b : visited) {
            if(! b ) return false; 
        }
        return true;
    }
}

For testing it, consider this graph:

Run test:

public static void main(String[] args){

    AllPossiblePaths app = new AllPossiblePaths(6);
    app.addEdge(0, 4)
    .addEdge(0, 1)
    .addEdge(1, 2)
    .addEdge(1, 4)
    .addEdge(4, 3)
    .addEdge(2, 3)
    .addEdge(2, 5)
    .addEdge(3, 5);

    app.findPath(0,5);
    app.findPath(5,0);
    app.findAllpaths(0,5);
}

output:

这篇关于BFS使用邻接列表遍历图中的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！