一道图论算法题 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 一道图论算法题

相关主题
● 上道图论的吧	● 再问一个IBM的题
● NPC中的P是什么缩写,如何判断一个问题是NPC	● 有好的图论算法书推荐吗？（内空）
● 一道算法问题求教。	● 求教google 电面 answer
● a question regarding finding all paths with a common sum	● A家电面题
● 检查graph里面是否有circle，是用BFS，还是DFS?	● A家电面被拒贡献个题攒人品吧
● 一道算法题求教，关于全连通图	● 【图论】某startup，Cactus graph求多少loops
● 有没有人讲讲图论里的BFS & DFS算法及应用?	● Amazon电面纪实
● 求教一道算法题	● 请教图论面试题

相关话题的讨论汇总
话题: 路径话题: npc话题: 图论话题: 一条话题: 其权

进入JobHunting版参与讨论

1

(共1页)

i********r 发帖数: 12113	1 在一个无向有权图里, 是否存在一条路径其权之和为M? 有的话找出该路径. 这是不是个NPC问题?
g*******y 发帖数: 1930	2 找一条路径？不是回路？可以用subset sum归约吧假设有一条链，每条边的weight就是subset sum问题中数组的每个数，然后任意两个顶点之间，如果没有边，就用一个weight=0的边连接。
k***e 发帖数: 556	3 老大，你怎么经常提些npc问题啊。如果这个问题多项式时间可解，那么就可以多项式时间解longest path in the graph

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 请教图论面试题	● 检查graph里面是否有circle，是用BFS，还是DFS?
● 求一个老帖子 amazon面试FAQ	● 一道算法题求教，关于全连通图
● 实在理解不了DP、图论等题，可以死记硬背么？	● 有没有人讲讲图论里的BFS & DFS算法及应用?
● 请大牛们介绍几个面试常考得高级数据结构吧	● 求教一道算法题
● 上道图论的吧	● 再问一个IBM的题
● NPC中的P是什么缩写,如何判断一个问题是NPC	● 有好的图论算法书推荐吗？（内空）
● 一道算法问题求教。	● 求教google 电面 answer
● a question regarding finding all paths with a common sum	● A家电面题

相关话题的讨论汇总
话题: 路径话题: npc话题: 图论话题: 一条话题: 其权

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)