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

查看:37
本文介绍了使用邻接表对图中所有路径进行 BFS 遍历的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我目前正在尝试在使用邻接矩阵的图中遍历从源到目的地的所有路径.我一直在尝试以 BFS 方式进行操作.感谢您的帮助.我只有一条路.我如何才能打印其他路径?

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);
                }
            }
        }
    }
}

推荐答案

使用下面的类,你可以运行 BFS 来查找单个路径 (findPath) 或查找多个路径 (findAllPaths).见评论:

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:

运行测试:

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);
}

输出:

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

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆