google電面

一開始先簡單介紹project

接著便馬上進入考試了

題目是給一個graph, 跟一個起點node, 找出包含這個起點node在內, 長度最小的cycle, 並且是要return 整個cycle 的path

我一開始先用dfs 做搜索 並用一個list<node> global variable 作為儲存目前找到的最短cycle path

有趣的是寫code過

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

node, 有的話就等於找到cycle了

但時間不夠改, 且我一開始寫出來的是求長度的方法, 後來想想應該是弄個二維list存目前搜索到的所有path, 加上面試官似乎有點不太明白我的想法, 不斷試著解釋給他聽

應該是跪了qq

这道题确实有点绕， 我面试的也是这个题目   

bfs 记录 path 可以用 predecessor 数组

这个还是比较好想到BFS吧，可以保证每个节点都以最短的路径被访问，这样再次遇到起点node时就是最短的环了；路径方面，用一个map<cur_node, pre_node>记录每个node是通过哪个邻居加入queue的，对该map进行backtracking就可以找到路径了

可以不用backtracking，直接用个list记录历史路径
我试着用BFS写了一下：
Class GraphNode(object):
    def __init__(self, label):
        self.label = label
        self.neighbors = []
def bfs(node):
    if not node:
        return []
    queue = [(node, [])]
    while queue:
        each, pre_path = queue.pop(0)
        if each in pre_path: return pre_path
        for nei in each.neighbors:
             queue.append((nei, pre_path + [each]))
    return []

有向图还是无向图？两者解法不一样的