在许多计算机应用中，由相连的节点所表示的模型起到了关键的作用。这些结点之间的连接很自然地会产生一连串的疑问：

• 沿着这些连接能否从一个结点到达另一个结点
• 有多少个结点和指定的结点相连
• 两个结点之间最短的连接是哪一条

要描述这些问题，我们要使用一种抽象的数学对象，叫做图。

图论作为数学领域的一个重要分支已经有了数百年的历史。人们发现了图的很多重要而实用的性质，发现了许多重要的算法，其中许多困难问题的研究仍然十分活跃。

首先为了展示图论应用的广泛领域，我们先看以下几个示例：

• 地图：正在计划旅行的人想知道A地到B地的最短路径。对最短路径上堵塞的人来说：从A地到B地那条路最快。

• 网页信息：当我们在浏览网页时，页面上都会包含其他网页的引用，通过单机链接，我们可以从一个页面跳转到另一个页面。

• 电路：在一块电路板上，晶体管、电阻、电容等各种元件是精密连接在一起的。我们使用计算机来控制制造电路板的机器并检查电路板的功能是否正常。我们既要检查短路这类简单问题，也要检查这幅电路图中的导线在蚀刻到芯片上是否会出现交叉等复杂问题。第一类问题的答案仅取决于连接(导线)的属性，而第二个问题则会涉及导线、各种元件以及芯片的物理特性等详细信息。

• 任务调度：商品的生产过程包含了许多工序以及一些限制条件，这些条件会决定某些任务的先后次序。如何安排才能在满足限制条件的情况下用最小的时间完成这些生产工序呢？

• 商业交易：零售商和金融机构都会跟踪市场中的买卖信息。在这种情况下，一条连接可以表示现金和商品在买方和卖方之间的转移。在此情况下，理解图的连接结构原理可能有助于增强人们对市场的理解。

• 配对：学生可以申请加入各种机构，例如社交俱乐部、大学或是医学院等。这些结点就对应学生和机构，而连接则对应递交的申请。我们希望找到申请者与他们感兴趣的空位之间配对的方法。

• 计算机网络：计算机网络是由能够发送，转发和接收各种消息的站点互相连接组成的。我们感兴趣的是这种互联结构的性质，因为我们希望网络中的线路和交换设备能够高效率地处理网络流量

• 软件：编译器会使用图来表示大型软件中各个模块之间的关系。图中的结点即构成整个系统的各种类和模块，连接则为类的方法之间的可能调用关系(静态分析)，或是系统运行时的实际调用关系(动态分析)。我们需要分析这幅图来决定如何以最优的方式来为程序分配资源。

• 社交网络：当你在使用社交网站时，会和你的网络之间建立明确的关系。

而在图数据结构中，我们会依次展开4种最重要的图模型

1. 无向图(简单连接)
2. 有向图(连接有方向性)
3. 加权图(连接带有权值)
4. 加权有向图(连接既有方向性又带有权值)