原题
六度分离是一个哲学问题，说的是每个人每个东西可以通过六步或者更少的步数建立联系。
现在给你一个友谊关系，查询两个人可以通过几步相连，如果不相连返回 -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 -> 用Queue来实现
- 加入hash map去重，并且巧妙的将step当作值存入每一个节点为key的hash map中，这样通过节点A找到的相邻节点的步数即map[A] + 1
完整代码
# Definition for Undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
import Queue
class Solution:
'''
@param {UndirectedGraphNode[]} graph a list of Undirected graph node
@param {UndirectedGraphNode} s, t two Undirected graph nodes
@return {int} an integer
'''
def sixDegrees(self, graph, s, t):
# Write your code here
members = {}
q = Queue.Queue(maxsize = len(graph))
q.put(s)
members[s] = 0
while not q.empty():
x = q.get()
if x == t:
return members[x]
for y in x.neighbors:
if y not in members:
members[y] = members[x] + 1
q.put(y)
return -1
