每日算法题 - Find Cycles in a Graph

文件: root - text - article - 2019 - 10 - find-cycles-in-a-graph.txt
标签: 每日算法题, 算法, 数据结构, 面试题, Daily Interview Problem, Data Structures and Algorithms, Computer Programming, | 英文 | 主页 | 类别: 计算机科学 | 332 次阅读, 18987 次搜索 | 72 个单词

| 浏览 | 博客存档

Hi, here's your problem today. This problem was recently asked by Facebook:

Given an undirected graph, determine if a cycle exists in the graph.

Here is a function signature:



def find_cycle(graph):

  # Fill this in.



graph = {

  'a': {'a2':{}, 'a3':{} },

  'b': {'b2':{}},

  'c': {}

}

print find_cycle(graph)

# False

graph['c'] = graph

print find_cycle(graph)

# True

Can you solve this in linear time, linear space?