java - java中的邻接矩阵，广度优先搜索

Question

以下代码使用邻接表结构执行广度优先搜索算法。我很好奇。如果我要实现这个邻接矩阵，我必须对代码进行哪些类型的编辑？

我知道我必须创建一个网格(n x n 矩阵)，但我的数据文件是否必须与该网格结构相对应？或者我会只填充一个空的网格结构并实现我的文本文件已有的关卡设计吗？

我觉得在实际代码中实现这一点是我最困惑的地方，关于下面的代码(使用堆栈)。我从来没有用矩阵做过 bfs，只做过邻接表。

这里是:

import java.io.*;
import java.util.*;

public class MainM {

    private Graph graph;

    /**
     * Constructor.
     */
    public MainM(Graph g) {
        graph = g;
    }

    /**
     * 1 - Create a stack to store all the vertices of our path on.
     * 2 - First push the 'end' vertex on our stack.
     * 3 - Now loop from the highest level back to the first level and
     *     a. loop through each level and
     *     b. check each vertex in that level if it's connected to the
     *        vertex on the top of our stack, if we find a match, push that
     *        match on the stack and break out of the loop.
     * 4 - Now we only need to reverse the collection (stack) before returning 
     *     the path in the "correct" order (from start to finish).
     * 
     * Here's an example ASCII drawing of backtracking from the end vertex "n" 
     * to the starting vertex "g". The arrows, <-, denote the path that was 
     * found.
     * 
     * level:  0      1      2      3       4      5      6    7     8
     *        ---------------------------------------------------------
     *         g <-+  IV     e      I       a   +- III <- o <- VI <- n 
     *             +- V <-+  f   +- II <-+  b   |         p
     *                    +- c <-+       |  d   |
     *                       j           +- h <-+
     *                                      q
     *                                      r
     */
    private List<String> backTrack(List<List<String>> container, String end) {
        Stack<String> path = new Stack<String>();                     // 1
        path.push(end);                                               // 2
        for(int i = container.size()-1; i >= 0; i--) {                // 3
            List<String> level = container.get(i);
            String last = path.peek();
            for(String s : level) {                                   // a
                if(graph.isConnectedTo(last, s)) {                     // b
                    path.push(s);
                    break;
                }
            }
        }
        Collections.reverse(path);                                    // 4
        return path;
    }

    /**
     * 1 - Get the level from the 'container' which was added last.
     * 2 - Create a new level to store (possible) unexplored verices in.
     * 3 - Loop through each of the vertices from the last added level, and
     *     a. get the neighboring vertices connected to each vertex,
     *     b. loop through each connecting vertex and if the connecting vertex
     *        has not yet been visited,
     *     c. only then add it to the newly created level-list and mark it as 
     *        visited in our set.
     * 4 - We don't need to search any further if we stumble upon the 'end' 
     *     vertex. In that case, just "return" from this method.
     * 5 - Only make the recursive call if we have found vertices which have 
     *     not been explored yet.
     */
    private void bfs(List<List<String>> container, 
            String end, Set<String> visited) {

        List<String> lastLevel = container.get(container.size()-1);   // 1
        List<String> newLevel = new ArrayList<String>();              // 2

        for(String vertex : lastLevel) {                              // 3
            List<String> edges = graph.getEdges(vertex);              // a
            for(String edge : edges) {                                // b
                if(!visited.contains(edge)) {                         // c
                    visited.add(edge);
                    newLevel.add(edge);
                }
                if(edge.equals(end)) return;                          // 4
            }
        }  
        if(newLevel.size() > 0) {                                     // 5
            container.add(newLevel);
            bfs(container, end, visited);
        }
    }

    /**
     * 1 - Create an empty 'container' to store all the levels from the 
     *     'start'-vertex in. A level is also a list with one or more vertices.
     * 2 - The first level only holds the 'start' vertex, which is added first,
     *     this is the 'init' list.
     * 3 - The 'start' vertex is also stored in a Set which keeps track of all 
     *     the vertices we have encountered so that we don't traverse vertices
     *     twice (or more).
     * 4 - Once we initialized the steps 1-3, we can call the actual BFS-
     *     algorithm.
     * 5 - Once the BFS-algorithm is done, we call the backTrack(...) method 
     *     to find the shortest path between 'end' and 'start' between the 
     *     explored levels of the graph. 
     */
    public List<String> getShortestPath(String start, String end) {
        List<List<String>> container = new ArrayList<List<String>>(); // 1
        List<String> init = new ArrayList<String>();                  // 2
        init.add(start);
        container.add(init);
        Set<String> visited = new HashSet<String>();                  // 3
        visited.add(start);
        bfs(container, end, visited);                                 // 4
        return backTrack(container, end);                             // 5
    }

    /**
     * Main method:
     *  1 - Create a Graph.
     *  2 - Get a shortest path between two vertices.
     *  3 - Print the shortest path.
     */
    public static void main(String[] args) throws FileNotFoundException {
        Graph graph = new Graph("data.txt");                          // 1
        MainM bfsAlgorithm = new MainM(graph);
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter starting city: ");
        String shortPath = sc.nextLine();

        System.out.println("Please enter ending city: ");
        String shortPath2 = sc.nextLine();
        List<String> shortestPath = bfsAlgorithm.getShortestPath(shortPath, shortPath2);
        //List<String> shortestPath = 
          //  bfsAlgorithm.getShortestPath("g", "n");                   // 2
        for(int i = 0; i < shortestPath.size(); i++) {
            System.out.print(shortestPath.get(i));                    // 3
            System.out.print(i < shortestPath.size()-1 ? " --> " : " ");
        }
    }
}

这是图形类:

import java.io.*;
import java.util.*;

public class Graph {

    private Map<String, List<String>> adjacencyList;

    /**
     * Instatiates the 'adjacencyList' and then parse the data file.
     */
    public Graph(String fileName) throws FileNotFoundException {
        adjacencyList = new HashMap<String, List<String>>();
        parseDataFile(fileName);
    }

    /**
     * This is an undirected graph, so we connect 'vertexA' to 'vertexB' 
     * and the other way around.
     */
    public void addConnection(String vertexA, String vertexB) {
        connect(vertexA, vertexB);
        connect(vertexB, vertexA);
    }

    /**
     * A private helper-method to connect 'vertexA' to 'vertexB'.
     * If 'vertexA' alreay exists in our 'adjacencyList', get it's 
     * edges-list and add 'vertexB' to it. If it doesn't exist,  
     * create a new ArrayList, add 'vertexB' to it and put it all 
     * in our 'adjacencyList'.
     */
    private void connect(String vertexA, String vertexB) {
        List<String> edges;
        if(adjacencyList.containsKey(vertexA)) {
            edges = adjacencyList.get(vertexA);
            edges.add(vertexB);
        } else {
            edges = new ArrayList<String>();
            edges.add(vertexB);
            this.adjacencyList.put(vertexA, edges);
        }
    }

    /**
     * Returns true iff 'vertexA' poits to to 'vertexB'.
     * Note that since this is an undirected graph, we do not 
     * need to check the other way around, the case if 'vertexB' 
     * is points to 'vertexA'.
     */
    public boolean isConnectedTo(String vertexA, String vertexB) {
        List<String> edges = getEdges(vertexA);
        return edges.contains(vertexB);
    }

    /**
     * Returns all the edges of a certain vertex, or throws an 
     * exception if the vertex doesn't exist in this graph.
     */
    public List<String> getEdges(String vertex) {
        List<String> edges = adjacencyList.get(vertex);
        if(edges == null) {
            throw new RuntimeException(vertex+" not present in the graph.");
        }
        return edges;
    }

    /**
     * Reads a text file with the graph-data. The text file contains 
     * N-blocks of lines where each block starts with the city followed
     * by N-lines of text representing the city2s and ending with an 
     * empty line.
     */
    private void parseDataFile(String fileName) throws FileNotFoundException {
        Scanner file = new Scanner(new File(fileName));
        while(file.hasNextLine()) {
            String city = file.nextLine().trim();
            while(file.hasNextLine()) {
                String city2 = file.nextLine().trim();
                if(city2.length() == 0) break;
                addConnection(city, city2);
            }
        }
    }

    /**
     * A Sting representation if this Graph.
     */
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Iterator<String> vertices = adjacencyList.keySet().iterator();
        while(vertices.hasNext()) {
            String vertex = vertices.next();
            List<String> edges = adjacencyList.get(vertex);
            builder.append(vertex);
            builder.append(" --> ");
            builder.append(edges);
            builder.append('\n');
        }
        return builder.toString();
    }

    /**
     * main
     */
    public static void main(String[] args) {
        try {
            Graph graph = new Graph("data.txt");
            System.out.println(graph);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}

这是一个文本测试文件:

Seattle
  a
  b
  01
  d
  e

II
  c
  h
  q
  r

III
  h
  o
  p

IV
  e
  f
  g

V
  c
  g
  j

VI
  k
  m
  n
  o

Answer 1

这是面向对象编程的有趣部分:-)

如果您为 Graph 创建一个通用接口(interface)并提供 2 个实现(例如，AdjListGraph 和 AdjMxGraph)，您没有更改 MainM 类中除声明之外的任何内容。只需在新的基于邻接矩阵的实现中实现常用函数(addConnection()、isConnectedTo() 等)即可。

我不会考虑更改我的输入数据结构。顺便说一句，有很多选项可以使用，最常见的是 Pajek format -- 乍一看可能有点奇怪。

此外，还有许多图形库(GraphStream、JUNG 等)，请查看它们。只需浏览这些代码库，您就可以学到很多东西。

希望有所帮助;]