我正在学校的一个项目中工作，当我试图回溯一个死角节点（没有连接到另一个节点的边）时，我被卡住了。我的想法是使用一个堆栈作为引用来跟踪我导航过的节点和我首先导航的最后一个节点。不过，我还是不知道如何实施。
我设法将图形文件读入嵌套的Map中，并创建了一个在节点之间具有边（连接）的Map。我也可以从一些节点导航到目标节点（“z”），但是当我碰到一个没有连接的节点时，我会在一个无限循环中从没有边的节点反弹到上一个节点。我不希望得到这个问题的答案，但任何建议/建议都将不胜感激。
见矩阵和直接距离列表和我的代码下面，谢谢和保持安全！
矩阵
A B C D E F G H I J K L M N O P Q R S T Z
A 0 71 0 0 0 0 0 0 0 151 0 0 0 0 0 0 0 0 0 0 0
B 71 0 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
C 0 75 0 118 0 0 0 0 0 140 0 0 0 0 0 0 0 0 0 0 0
D 0 0 118 0 111 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
E 0 0 0 111 0 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
F 0 0 0 0 70 0 75 0 0 0 0 0 0 0 0 0 0 0 0 0 0
G 0 0 0 0 0 75 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 120 0 146 0 0 138 0 0 0 0 0 0 0 115 0
I 0 0 0 0 0 0 0 146 0 80 0 97 0 0 0 0 0 0 0 0 0
J 151 0 140 0 0 0 0 0 80 0 99 0 0 0 0 0 0 0 0 0 0
K 0 0 0 0 0 0 0 0 0 99 0 0 0 0 0 0 0 0 0 0 211
L 0 0 0 0 0 0 0 138 97 0 0 0 0 0 0 0 0 0 0 0 101
M 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 90
N 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 98 142 0 0 0 85
O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 86 0 0 0 0 0
P 0 0 0 0 0 0 0 0 0 0 0 0 0 98 86 0 0 0 0 0 0
Q 0 0 0 0 0 0 0 0 0 0 0 0 0 142 0 0 0 92 0 0 0
R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 92 0 87 0 0
S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 87 0 0 0
T 0 0 0 0 0 0 0 115 0 0 0 0 0 0 0 0 0 0 0 0 0
Z 0 0 0 0 0 0 0 0 0 0 211 101 90 85 0 0 0 0 0 0 0直接距离列表
A 380
B 374
C 366
D 329
E 244
F 241
G 242
H 160
I 193
J 253
K 176
L 100
M 77
N 80
O 161
P 151
Q 199
R 226
S 234
T 92
Z 0java代码
import java.io.File;
import java.util.*;
public class Temp2 {
private HashMap<String, Integer> ddMap = new HashMap<>();
private HashMap<Integer, String> columnReferenceMap = new HashMap<>();
private HashMap<String, HashMap<String,Integer>> nodes = new HashMap<>();
private HashMap<String, HashMap<String, Integer>> ddNodes = new HashMap<>();
// Method to read the file and create a map for direct distance dd
public void readFileDdToMap() {
String lineFromFile = "";
String[] tokens;
int count = 0;
try {
Scanner fileInput = new Scanner(new File("src/direct_distance.txt"));
while (fileInput.hasNext()) {
lineFromFile = fileInput.nextLine();
tokens = lineFromFile.split("\\s+");
String key = tokens[0];
Integer dd = Integer.parseInt(tokens[1].trim());
ddMap.put(key, dd);
// count++;
}
// System.out.println(ddMap);
}
catch (Exception e) {
System.out.println(e);
}
}
// Method to create an index column and add to a map
public void indexColumnToMap() {
String headerFromFile = "";
String[] token;
try {
Scanner headerInput = new Scanner(new File("src/graph_input.txt"));
headerFromFile = headerInput.nextLine();
token = headerFromFile.split("\\s+");
for(int i = 0; i < token.length; i++) {
// System.out.print(token[i]);
columnReferenceMap.put(i,token[i]);
}
// System.out.println(columnReferenceMap);
}
catch (Exception e) {
System.out.println(e);
}
}
// Method to read the graph file and populate a map with kay as a letter "A" and value the nodes that have edges with "A"
public void createEdgeNodeMap() {
String lineFromFile = "";
String[] tokens;
try {
Scanner fileInput = new Scanner(new File("src/graph_input.txt"));
lineFromFile = fileInput.nextLine(); // reading but not using the first line read
while(fileInput.hasNext()) {
HashMap<String, Integer> tempNodeMap = new HashMap<>();
tempNodeMap.clear();
lineFromFile = fileInput.nextLine();
tokens = lineFromFile.split("\\s+");
for (int i = 1; i < tokens.length; i++) {
int e = Integer.parseInt(tokens[i]);
if(e == 0) { //ignore zeros read from the file, no edge
continue;
}
tempNodeMap.put(columnReferenceMap.get(i), e);
}
// System.out.println(tokens[0]+" "+tempNodeMap);
nodes.put(tokens[0],tempNodeMap);
}
// System.out.println(nodes);
}
catch (Exception e) {
System.out.println(e);
}
}
// Method to read the graph file and populate a map with edges (nodes) with direct distances
public void createDdNodeMap() {
String lineFromFile = "";
String[] tokens;
try {
Scanner fileInput = new Scanner(new File("src/graph_input.txt"));
lineFromFile = fileInput.nextLine(); // reading but not using the first line read
while(fileInput.hasNext()) {
HashMap<String, Integer> tempEdgeMap = new HashMap<>();
tempEdgeMap.clear();
lineFromFile = fileInput.nextLine();
tokens = lineFromFile.split("\\s+");
for (int i = 1; i < tokens.length; i++) {
int e = Integer.parseInt(tokens[i]);
if(e == 0) { //ignore zeros read from the file, no edge
continue;
}
// tempEdgeMap used to get edges
tempEdgeMap.put(columnReferenceMap.get(i), ddMap.get(columnReferenceMap.get(i)));
}
// System.out.println(tokens[0]+" "+tempEdgeMap);
// direct distance node map
ddNodes.put(tokens[0], tempEdgeMap);
}
// System.out.println(ddNodes);
}
catch (Exception e) {
System.out.println(e);
}
}
//This is not Algorithm 1 or 2. This just finding the shortest edge.
public String findShortestEdge(String node) {
// Get the map contained for this node (passed into the method as a String, like "A")
Map<String, Integer> connections = nodes.get(node);
// Our closest Node found so far (like A, B, etc)
String closestNode = null;
// Set this to a ridiculously high number.
int closestEdge = Integer.MAX_VALUE;
// Loop through each key in the map. Maps have a key,value structure. We're looking at each key / node.
for(String currentNode : connections.keySet()) {
// Get the edge value for the node
int currentEdge = connections.get(currentNode);
// Is the currentEdge (of the node we're looking at now) shorter than the closestEdge we've found so far?
if(currentEdge < closestEdge) {
closestEdge = currentEdge;
closestNode = currentNode;
}
}
return closestNode;
}
// This method is the same as find ShortestDistance but used direct distance node map
public String findShortestDd(String node) {
// Get the map contained for this node (passed into the method as a String, like "A")
Map<String, Integer> connections = ddNodes.get(node);
// Our closest Node found so far (like A, B, etc)
String closestNode = null;
// Set this to a ridiculously high number.
int closestEdge = Integer.MAX_VALUE;
// Loop through each key in the map. Maps have a key,value structure. We're looking at each key / node.
for(String currentNode : connections.keySet()) {
// Get the edge value for the node
int currentEdge = connections.get(currentNode);
// Is the currentEdge (of the node we're looking at now) shorter than the closestEdge we've found so far?
if(currentEdge < closestEdge) {
closestEdge = currentEdge;
closestNode = currentNode;
}
}
return closestNode;
}
public String findDestination(String currentNode) {
Map<String, Integer> edges = ddNodes.get(currentNode);
String nextNode = null;
String destination = "Z";
System.out.println(currentNode);
while(currentNode.compareTo(destination) != 0) {
nextNode = findShortestDd(currentNode);
currentNode = nextNode;
System.out.println(currentNode);
}
return currentNode;
}
public static void main(String[] args) {
/**creating instance of class */
Temp2 t = new Temp2();
/**read direct distance file into a map - ddMap */
t.readFileDdToMap();
/**create an index to vertex(coulmn name A, B, C etc) to a map - columnReferenceMap */
t.indexColumnToMap();
/**create an edge node map - nodes */
t.createEdgeNodeMap();
/**create a direct distance node map - ddNodes */
t.createDdNodeMap();
/**other tests */
/**getting all keys from ddNodes map */
for(Map.Entry kv : t.ddNodes.entrySet()) {
System.out.println(kv.getKey() + " "+ kv.getValue());
}
System.out.println();
/***/
Stack st = new Stack();
List pathTraveledList = new ArrayList();
String currentNode = "O";
String prevNode = null;
String nextNode = null;
String destination = "Z";
System.out.println(currentNode);
while(currentNode.compareTo(destination) != 0) {
prevNode = currentNode;
nextNode = t.findShortestDd(currentNode);
currentNode = nextNode;
st.push(t.ddNodes.get(currentNode));
pathTraveledList.add(t.ddNodes.get(currentNode));
System.out.println("prev node: "+prevNode);
System.out.println("curr node: "+currentNode);
System.out.println("from stack: "+st);
System.out.println("from list: "+ pathTraveledList);
System.out.println();
}
/**get user input via the keyboard */
// Scanner keyboardIn = new Scanner(System.in);
// System.out.println("Enter a letter form A-Z to start ");
// String startNode = keyboardIn.next().toUpperCase();
// System.out.println(t.findShortestEdge(startNode));
}
}
暂无答案！
目前还没有任何答案，快来回答吧！