2
以下代碼使用鄰接列表結構執行寬度優先搜索算法。我很好奇。如果我要實現這個鄰接矩陣，那麼我需要對代碼進行哪些編輯？java中的鄰接矩陣，寬度優先搜索
我知道我將不得不創建一個網格（n×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