图论算法

图论算法是一种研究图论结构与图论性质的一种学科，它对于解决众多现实问题有着重要的意义。图论算法在计算机科学、工程学、数学等领域都发挥着很重要的作用。

一、 概述

图论是一种运用于解决问题的数学领域，它可用于建立计算机网络、物流规划、道路交通、ADM（算法决策制图）、流程图等现代计算机应用系统。与传统的数学学科（如代数学、解析几何等）不同，图形理论目标是研究 “只有结点和连接的网络”，而不是“空间中存在的结构”，图形理论属于离散数学的范畴。

图包括 有向图和无向图，因此也有对应无向图算法和有向图算法。图中还有连通性、强连通性、最小生成树、最短路径甚至网络流等概念，而每个概念都对应一个相应的算法。

二、最短路径算法

在图的算法中，求最短路径的算法是最基础的一种。其中最著名的是Dijkstra算法和Bellman-Ford算法。Dijkstra算法复杂度为O(n^2)，但是如果使用堆优化可以将复杂度降为O(nlogn)。Bellman-Ford算法的复杂度为O(ne)。

三、 最小生成树算法

最小生成树算法主要有两种，一种是Prim算法，另一种是Kruskal算法。它们解决的问题就是在有权的连接图（边带权值）中找出一棵生成树，使得树的各边上权值之和最小。

四、DAG和拓扑排序

在所有可能的路径上不重不漏地处理点（或边）的问题中，DAG（有向无环图）及拓扑排序方法可解决。

五、图的着色问题

对于一个给定的图，找出最小的颜色数，使得相邻的点之间的颜色不相同。这就是图的着色问题。这个问题是NP问题，还没有有效的算法被发现，也没有解决此问题的通用算法。