Question:
https://aaronice.gitbooks.io/lintcode/content/graph_search/six_degrees.html
My code:
public int sixDegrees(UndirectedGraphNode s, UndirectedGraphNode t) {
Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
Map<UndirectedGraphNode, Integer> map = new HashMap<UndirectedGraphNode, Integer>();
q.offer(s);
map.put(s, 0);
while (!q.isEmpty()) {
UndirectedGraphNode curr = q.poll();
if (curr == t) {
return map.get(curr) + 1;
}
for (UndirectedGraphNode next : curr.neighbors) {
if (map.containsKey(next)) {
continue;
}
q.offer(next);
map.put(next, map.get(curr) + 1);
}
}
return -1;
}
class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
}
};
設(shè)計一個 HashMap 用來存到當(dāng)前結(jié)點，需要的 step
也有做法是，拿一個更大的類把 GraphNode 包起來狐榔，同時包含一個step成員變量。表明到這個結(jié)點需要的step兰绣。
Anyway, Good luck, Richardo! -- 09/27/2016
