描述
六度分离是一个哲学问题，说的是每个人每个东西可以通过六步或者更少的步数建立联系。
现在给你一个友谊关系，查询两个人可以通过几步相连，如果不相连返回 -1
样例
给出图
1------2-----4
\ /
\ /
\--3--/
{1,2,3#2,1,4#3,1,4#4,2,3} s = 1, t = 4 返回 2
给出图二
1 2-----4
/
/
3
{1#2,4#3,4#4,2,3} s = 1, t = 4 返回 -1
思路
普通的BFS按层遍历的问题
代码
- 自己的答案
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
* }
* };
*/
public class Solution {
/**
* @param graph a list of Undirected graph node
* @param s, t two Undirected graph nodes
* @return an integer
*/
public int sixDegrees(List<UndirectedGraphNode> graph,
UndirectedGraphNode s,
UndirectedGraphNode t) {
if (s == t) {
return 0;
}
Queue<UndirectedGraphNode> queue = new LinkedList<>();
Set<UndirectedGraphNode> hash = new HashSet<>();
queue.offer(s);
hash.add(s);
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
steps++;
for (int i = 0; i < size; i++) {
UndirectedGraphNode node = queue.poll();
for (UndirectedGraphNode neighbor : node.neighbors) {
if (hash.contains(neighbor)) {
continue;
}
if (neighbor == t) {
return steps;
}
queue.offer(neighbor);
hash.add(neighbor);
}
}
}
return -1;
}
}
- 九章的答案
/**
* Definition for Undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) {
* label = x;
* neighbors = new ArrayList<UndirectedGraphNode>();
* }
* };
*/
public class Solution {
/**
* @param graph a list of Undirected graph node
* @param s, t two Undirected graph nodes
* @return an integer
*/
public int sixDegrees(List<UndirectedGraphNode> graph,
UndirectedGraphNode s,
UndirectedGraphNode t) {
// Write your code here
if (s == t)
return 0;
Map<UndirectedGraphNode, Integer> visited = new HashMap<UndirectedGraphNode, Integer>();
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
queue.offer(s);
visited.put(s, 0);
while (!queue.isEmpty()) {
UndirectedGraphNode node = queue.poll();
int step = visited.get(node);
for (int i = 0; i < node.neighbors.size(); i++) {
if (visited.containsKey(node.neighbors.get(i))) {
continue;
}
visited.put(node.neighbors.get(i), step + 1);
queue.offer(node.neighbors.get(i));
if (node.neighbors.get(i) == t) {
return step + 1;
}
}
}
return -1;
}
}
