logo标签列表

图表能够比其他方法更好地解决哪些问题？请举出一些良好的例子。

data-structuresgraphgraph-theory
50

阅读了 Stevey Yegge 的 Get That Job At Google 文章后，我发现这句话很有意思：

每当有人给你一个问题时，想到图形。它们是表示任何关系的最基本和灵活的方式，所以任何有趣的设计问题都有50%的可能涉及图形。在尝试其他解决方案之前，请确保无法考虑使用图形解决它。这个提示很重要！

哪些问题最适合使用图形数据结构/算法来表示和/或解决？

我能想到的一个例子是：导航设备（如 Garmin、TomTom），提供从当前位置到另一个位置的路线指示，利用图形和高级路径算法。

还有哪些例子？

3
顺便说一下，不要相信关于谷歌面试的那些神话。与其他公司相比，他们有时会问非常简单直接的问题，这实际上可能会使你迷惑。 - Uri
19个回答
3

人与人之间的社交关系是一个有趣的图形示例。我曾尝试使用传统的关系型数据库模拟这些连接，但发现太难了。最终我选择了图形数据库，这是个很好的选择，因为它使得在人（节点）之间跟踪连接（边）变得容易。

3

图形对于管理依赖关系非常有用。

最近我开始使用Castle Windsor容器，在检查内核后，我发现了一个GraphNodes属性。Castle Windsor使用图形来表示对象之间的依赖关系，以便注入可以正确地工作。请查看这个文章。

我还使用简单的图形理论开发插件框架，每个图形节点代表一个插件，一旦定义了依赖关系，我就可以遍历图形来创建插件加载顺序。

我计划改变算法，实现Dijkstra算法，使每个插件都带有特定版本的权重，因此简单的更改将只加载插件的最新版本。

我希望我早点发现这个。我喜欢那句话“每当有人给你一个问题时，想想图形。”我绝对认为这是真的。

3

我认为我们在普通应用程序中使用的大部分领域模型在某种程度上都是图形。如果您查看UML图表，您会注意到使用有向标记图可以轻松地将它们直接转换为持久化模型。在Neo4j上有一些相关示例。

祝好

/彼得

2
2
这个回答是为什么链接式回答不应该在Stack Overflow上受到好评的一个很好的例子。你所有的链接现在都失效了。 - mikeazo
2

在关系型数据库中，任何可以被建模为外键的内容本质上都是图中的节点和边。

也许这可以帮助您想到示例，因为大多数事物都可以在RDBMS中轻松建模。

2

对代码中的算法和实现进行性能分析和基准测试。

1

在数据库理论中分析序列化事务。

1

您可以在任何定义问题域对象为节点，将解决方案作为节点之间控制和/或数据流的地方利用图形。

考虑到树确实是连通无环图，因此您甚至可以在更多领域使用图论。

0

基本上，几乎所有常见的数据结构，如树、列表、队列等，都可以被视为一种图形类型，其中一些具有不同类型的约束。

根据我的经验，在网络流问题中我广泛使用了图形，这在许多领域中都得到了应用，例如电信网络路由和优化、工作负载分配、匹配、供应链优化和公共交通规划。

另一个有趣的领域是社交网络建模，正如之前的回答所提到的。

还有更多的领域，例如集成电路优化等。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接