原題
六度分離是一個(gè)哲學(xué)問題秧秉，說的是每個(gè)人每個(gè)東西可以通過六步或者更少的步數(shù)建立聯(lián)系赖钞。
現(xiàn)在給你一個(gè)友誼關(guān)系，查詢兩個(gè)人可以通過幾步相連妒茬，如果不相連返回 -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
解題思路
- 本題相當(dāng)于求圖中兩點(diǎn)的最短路徑仰美，BFS -> 用Queue來(lái)實(shí)現(xiàn)
- 加入hash map去重迷殿，并且巧妙的將step當(dāng)作值存入每一個(gè)節(jié)點(diǎn)為key的hash map中，這樣通過節(jié)點(diǎn)A找到的相鄰節(jié)點(diǎn)的步數(shù)即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
