Java数据结构之图(动力节点Java学院整理)

Java数据结构之图是动力节点Java学院整理的一篇关于图的攻略教程，该教程包含以下主要内容：

一、图的定义

图是由若干个顶点以及它们之间的相互关系所构成的数学模型。它包含了许多实际生活中的应用，如社交网络、地图、电子邮件网络等。

二、图的存储方式

图的存储方式有两种：邻接矩阵和邻接表。

邻接矩阵

邻接矩阵以二维数组的形式存储图。对于有n个顶点的图，其邻接矩阵大小为n×n。如果顶点i和顶点j之间存在边，则矩阵元素a[i][j]=1，否则a[i][j]=0。此外，当图是有向图时，要注意邻接矩阵的对称性。

邻接表

邻接表是一种链表数组，每个链表中存储了与该顶点相连的其他顶点。它只考虑存在的边，所以用邻接表可以节约存储空间。如果涉及到有向图，还需要使用逆邻接表。

三、图的遍历算法

图的遍历有两种算法：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

DFS从某个顶点口开始沿着图的某一分支往下遍历，直到一条路走到黑。当该节点的所有后继节点都访问完成后，回溯到该节点的前一个节点重复以上过程。

广度优先搜索（BFS）

BFS从某个顶点开始，先遍历所有与该节点相邻的节点，然后再遍历这些节点所有未访问过的后继节点。也就是说，BFS先遍历距离起始节点近的节点。

四、基本算法

基本算法包括：最短路径、最小生成树、拓扑排序和关键路径。

最短路径

最短路径是指两个顶点之间连接所需的最小步数或最小权值的路径。最短路径算法常见的有Dijstra算法和Floyd算法。

最小生成树

最小生成树是指在一个无向图中生成一个子图，使得这个子图可以连通所有点，且边的权值之和最小。最小生成树算法常见的有Kruskal算法和Prim算法。

拓扑排序

拓扑排序是对于有向无环图来说的，它有多种具体实现算法。它的目的是给顶点下一个有限的偏序编号，使得对于每一条有向边（u，v），节点u在序列中比节点v先出现。拓扑排序算法常见的有深度优先排序算法和Kahn算法。

关键路径

关键路径是与项目完成时间相关的路径，它是贯穿整个项目的关键路径。在关键路径上任何一项活动的完成时间延误都会导致整个项目的完成时间延误。关键路径算法常见的有AOE网络图和AOV网络图。

五、示例说明

下面以一个最短路径的示例来说明图的应用。

假设有如下图所示的无向图，其每个边的权值表示该边的长度。

                1
            /       \
           2         3
        /    \     /   \
       4     5   6      7
      /     / \   
     8    9    10

我们要求顶点1到顶点8的最短路径，可以使用Dijkstra算法来解决。首先，对每个顶点设立一个距离值，初始化距离值为无穷大，再将起始顶点的距离值设为0。然后，采用贪心策略，每次找出距离起点最近的一个顶点，并判断是否能够松弛（减少）其邻接节点的距离值。

以此类推，直到所有顶 点的距离值都被确定为止。在该图中，经过Dijkstra算法计算得出1到8的最短路径为1-2-4-8，路径长度为14。

另一个示例是拓扑排序的应用。假设有以下两个活动：

活动    1    2    3    4    5
时间    4    2    5    8    6

活动    前置活动    1    2    3    4   
       相关活动    5    3    4    5

前者是一组活动及其所需时间，后者是一组活动的前置关系。我们需要在这个活动列表中进行拓扑排序，求出最短完成时间。

首先，对这些活动进行拓扑排序。然后，对于排序结果的每个活动，计算其最早开始时间和最晚开始时间，算出每个活动的最早完成时间和最晚完成时间。最短完成时间即为最后一个活动的最晚完成时间。在该例中，拓扑排序结果为1-2-3-4-5，最短完成时间为23。