在阅读了 Stevey Yegge 的在 Google 获得那份工作的文章后，我发现这句话很有趣：
每当有人给你一个问题时，想想图表。它们是表示任何类型关系的最基本和最灵活的方式，因此任何有趣的设计问题都需要一个 50 到 50 个镜头，其中包含一个图表。在转向其他解决方案类型之前，请绝对确保您想不出使用图表来解决它的方法。这个提示很重要！
图数据结构/算法最能代表和/或解决的问题有哪些示例？
我能想到的一个例子：导航单元（ala Garmin，TomTom），提供从您当前位置到另一个位置的道路方向，利用图表和高级路径算法。
还有一些是什么？
Computer Networks: Graphs model intuitively model computer networks and the Internet. Often nodes will represent end-systems or routers, while edges represent connections between these systems.
Data Structures: Any data structure that makes use of pointers to link data together is making use of a graph of some kind. This includes tree structures and linked lists which are used all the time.
Pathing and Maps: Trying to find shortest or longest paths from some location to a destination makes use of graphs. This can include pathing like you see in an application like Google maps, or calculating paths for AI characters to take in a video game, and many other similar problems.
Constraint Satisfaction: A common problem in AI is to find some goal that satisfies a list of constraints. For example, for a University to set it's course schedules, it needs to make sure that certain courses don't conflict, that a professor isn't teaching two courses at the same time, that the lectures occur during certain timeslots, and so on. Constraint satisfaction problems like this are often modeled and solved using graphs.
Molecules: Graphs can be used to model atoms and molecules for studying their interaction and structure among other things.
我对图论非常感兴趣，我用它解决了很多不同类型的问题。您可以使用图解决很多与路径相关的问题、匹配问题、结构问题。
路径问题有很多应用。
这是在职业杯的面试问题中。假设您想找到子数组的最长和。例如，[1, 2, 3, -1]最长的总和为 6。将其建模为有向无环图( DAG )，添加虚拟源、虚拟目标。将每个节点与一条边连接起来，边的权重与数字对应。现在使用 DAG 中的最长路径算法来解决这个问题。
同样，金融世界中的套利问题，甚至寻找最长重叠结构的几何问题都是类似的路径问题。
一些明显的问题是网络问题（您的网络可能有计算机人员、组织结构图等）。
您可以收集很多结构信息，例如
我已经使用图表解决了很多与项目管理相关的问题。一系列事件可以被描绘成一个有向图（如果你没有循环，那就更好了）。所以，现在你可以
很多匹配问题都可以通过图来解决。例如，如果您需要将处理器与工作负载相匹配或将工人与其工作相匹配。在我的期末考试中，我必须将人们与餐馆的桌子相匹配。它遵循相同的原则（二分匹配 -> 网络流算法）。它简单而强大。
一个特殊的图，一棵树，在计算机科学领域有很多应用。例如，在编程语言的语法中，或在数据库索引结构中。
最近，我还在编译器优化问题中使用了图表。我正在使用摩根的书，它教会了我迷人的技巧。
这份清单真的不胜枚举。图是关系的美丽数学抽象。如果你能正确地建模，你真的可以创造奇迹。并且由于图论已经找到了如此多的应用，该领域也有许多积极的研究。由于大量的研究，我们看到更多的应用正在推动研究。
如果你想开始学习图论，买一本很好的初学者离散数学书（我想到了Rosen ），你可以从Fould或Even等作者那里购买书籍。CLRS也有很好的图算法。
您的源代码是树结构的，树是一种图。每当您听到人们谈论 AST（抽象语法树）时，他们都在谈论一种图。
指针形成图结构。任何带指针的东西都在做某种图形操作。
网络是一个巨大的有向图。谷歌在搜索中占据主导地位的关键洞察力是，网络的图形结构与页面的文本内容具有可比性或更重要的重要性。
状态机是图。状态机用于网络协议、正则表达式、游戏和各种其他领域。
很难想到您所做的任何事情不涉及某种图形结构。
一个大多数人都熟悉的例子：构建系统。Make 是典型的例子，但几乎所有好的构建系统都依赖于有向无环图。基本思想是方向对源和目标之间的依赖关系进行建模，并且您应该以特定顺序“遍历”图形以正确构建事物->这是拓扑排序的示例。
另一个例子是源代码控制系统：同样基于 DAG。它用于合并，例如，找到共同的父级。
好吧，编译器使用的许多程序优化算法都是基于图的（例如，找出调用图、流控制、大量静态分析）。
许多优化问题都是基于图的。由于许多问题可以简化为图形着色和类似问题，因此许多其他问题也是基于图形的。
我不确定我是否同意图表是表示每个关系的最佳方式，我当然会尽量避免这些“有钉子，让我们找锤子”的方法。图通常具有较差的内存表示，并且许多算法在使用矩阵、位集和其他东西实现时实际上更有效（在实践中）。
光学字符识别。想象以一定角度扫描的一页文本，图像中有一些噪点，您必须在其中找到文本行之间的空间。一种方法是制作像素图，并找到从页面一侧到另一侧的最短路径，其中亮度的差异是像素之间的距离。
这个例子来自Algorithm Design Manual，其中有很多其他真实世界的图问题例子。
以下是基于图论的：
一个流行的例子是垃圾收集。
收集器从一组引用开始，然后遍历它们引用的所有对象，然后遍历那里引用的所有对象，依此类推。它找到的所有东西都被添加到可达对象的图中。所有其他对象都无法访问和收集。
图不是数据结构。它们是关系的数学表示。是的，您可以使用图来思考和理论化问题，并且有大量关于它的理论。但是当你需要实现一个算法时，你选择的是最能代表问题的数据结构，而不是图表。有许多数据结构可以表示一般图，对于特殊类型的图甚至更多。
在您的问题中，您将这两件事混合在一起。相同的理论解决方案可能在图方面，但实际解决方案可能使用不同的数据结构来表示图。
找出两个分子是否可以结合在一起。在开发药物时，人们通常对药物分子是否可以融入体内更大的分子感兴趣。确定这是否可能的问题是分子不是静态的。分子的不同部分可以围绕它们的化学结合旋转，因此分子可以变成很多不同的形状。
每个形状都可以说是表示由形状组成的空间中的一个点。解决这个问题需要找到一条穿过这个空间的路径。您可以通过创建一个穿越空间的路线图来做到这一点，该路线图本质上是一个由合法形状组成的图表，并说明一个形状可以变成哪种形状。通过此路线图使用 A* 图搜索算法，您可以找到解决方案。
好吧，那是很多可能不是很容易理解或清楚的喋喋不休。但我的观点是，各种问题都会出现图表。
图表非常适合管理依赖项。
我最近开始使用 Castle Windsor Container，在检查内核后发现了一个 GraphNodes 属性。Castle Windsor 使用图表来表示对象之间的依赖关系，以便注入能够正常工作。看看这篇文章。
我还使用简单的图论开发了一个插件框架，每个图节点代表一个插件，一旦定义了依赖关系，我就可以遍历图来创建插件加载顺序。
我计划更改算法以实现 Dijkstra 的算法，以便每个插件都以特定版本加权，因此简单的更改只会加载最新版本的插件。
我和我更早发现了这一点。我喜欢这句话“每当有人给你一个问题，想想图表。” 我绝对认为这是真的。
恕我直言，我们在正常应用程序中使用的大多数领域模型在某些方面都是图表。如果您查看 UML 图，您会注意到，使用有向标记图，您可以轻松地将它们直接转换为持久性模型。Neo4j有一些这样的例子
干杯
/彼得
人与人之间的社会联系是一个有趣的图表示例。我尝试使用传统的 RDMS 在数据库级别对这些连接进行建模，但发现它太难了。我最终选择了一个图形数据库，这是一个很好的选择，因为它可以很容易地跟踪人（节点）之间的连接（边）。
任何可以在关系数据库中建模为外键的东西本质上都是图中的边和节点。
也许这会帮助您思考示例，因为大多数事物都可以轻松地在 RDBMS 中建模。
在代码中分析和/或基准测试算法和实现。
您可以查看 Neo4j wiki 中的一些示例，
以及 Neo4j 使用的项目（已知项目）
否则，推荐算法对图很有用，参见例如 PageRank 和其他东西
您可以在任何可以将问题域对象定义为节点并将解决方案定义为节点之间的控制和/或数据流的地方使用图形。
考虑到树确实是连通无环图这一事实，您可以使用图论的领域甚至更多。
分析数据库理论中的事务可串行性。
基本上几乎所有常见的数据结构，如树、列表、队列等，都可以被认为是图的类型，有些具有不同类型的约束。
根据我的经验，我在网络流问题中大量使用了图，它被用于许多领域，如电信网络路由和 优化、工作负载分配、匹配、供应链优化和公共交通规划。
另一个有趣的领域是前面提到的社交网络建模。
还有更多，例如集成电路优化等。