数据结构和算法基础之图论基础

一、基本概念

  • 图是有顶点和边组成的,如果边是有方向的,图就是有向图。
  • 路径是从一个顶点到另一个顶点,经过的边数是路径的长,如果边有权,路径是权的和。
  • 一个图的每一个顶点到其他顶点都存在一条路径,那么这个图就是连通的。

  • 邻接矩阵可以用来表示图,如果A[u][v]为true则表示u和v之间有边。

  • 图的邻接表表示是表示出所有邻接的顶点,然后组成一个邻接表。

    二、经典算法

    1.求单源最短路径的Dijkstra算法

    求单源最短路径问题经典算法是Dijkstra算法,也是经典的贪婪算法。贪婪算法分阶段处理问题,每个阶段都选择一个当前的最优解,最后的解就有很大可能是最优的。
    Dijkstra算法求解单源最短路径的步骤是从一个点开始,先找到所有和这个点邻接的点,然后在邻接的点中确定出可以确定的和顶点距离最短路径的点(即确定第一阶段最优解),然后再从确定的点出发,确定出这个点可以确定的邻接点和顶点距离最短路径的点(即确定第二阶段最优解),然后进行第三阶段······一直到所有点的最短路径都被确定。

    2.求最小生成树的Prim算法和Kruskal算法

    Prim算法和Dijkstra算法很相似,只不过是把最优解的确定由和顶点的最短路径改为求到已知的根节点距离最短的节点。而Kruskal算法是改变了贪婪策略,改为连续选择最小权的边,只要不产生圈,就把这条边选定组成最小生成树的边。

    三、图论的应用

    在应用图论解决实际问题之前,首先要有从实际问题中抽象出数据结构的能力。常见的可以抽象为图的实际问题有很多,比如城市之间的航线,最短路径算法就可以用来求解城市之间最短航行的最优解,又比如城市之间铺设光缆,最小生成树算法就可以求解出铺设距离最短并且每个城市之间都可以进行通信的最优解。这样的例子还有很多,以上只是很简单直观的抽象,当然还有很多抽象层次更高的实际问题,这就需要对图和图论算法更深入的理解了。