本文共 1518 字，大约阅读时间需要 5 分钟。

一、基本概念理解

图：G=（V,E）= 边集V（G） + 点集E（G）

有向图：边集中的元素均为有方向的.

无向图：边集中的元素无方向.

完全图：每两点之间都可直接互通.

有向完全图：有弧 n(n-1) 条.（有方向的称为弧） 无向完全图：有边 n(n-1)/2 条.（无方向的称为边）

权：与弧或边相关的数.

网：带权的图.

子图：图的一部分.

顶点的度：

对无向图：与点关联的边的数目. 对有向图：入度 + 出度 = 与弧关联的边的数目.

路径：顶点的序列.

路径长度： 对图：沿路径边或弧的数目. 对网：沿路径边或弧的权值加和. 简单路径：顶点不重复. 回路：第一个顶点和最后一个顶点为同一个顶点. 简单回路：回路 + 中间顶点不重复.

连通：两个顶点可达.

连通图：图中任意两个顶点可达. （连通+无向图=连通图）（有向图 + 连通图 = 强连通图 ） （可以认为连通图对有向图无概念，强连通图对无向图无概念） 连通分量： 强连通图的连通分量为其本身. 非连通的无向图的每一个极大连通子图. 最大连通子图：把图的所有结点用最少的边将其连接起来的子图，不唯一. 强连通分量：有向图中的极大强连通子图.

生成树：极小连通子图（全部顶点 + 连着全部顶点的n-1条边）.

生成森林：每一个连通分量都写成它的生成树.

二、图的存储结构

1.邻接矩阵

一维数组存储顶点信息 + 矩阵（二维数组）存储顶点之间信息 对图： A[ i ][ j ] = 0 —> i 点和 j 点不可达 A[ i ][ j ] = 1 —> i 点和 j 点可达 对网： A[ i ][ j ] = w —> i 点和 j 点之间的权值 A[ i ][ j ] = ∞ —> i 点和 j 点不可达

对无向图：因为对称，可压缩存储，我们只取矩阵的上三角或下三角即可.

从而，我们所需存储空间为1+2+3+…+n = n(n+1)/2. 对有向图：不可压缩存储，所需存储空间为n^2.

2.邻接表

对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。

逆邻接表

三、图的遍历

1.深度优先遍历DFS

2.广度优先遍历BFS

四、生成树（求最小生成树）

1、生成树的顶点个数与图的顶点个数相同 2、生成树是图的极小连通子图 3、一个有n个顶点的连通图的生成树有n-1条边 4、生成树中任意两个顶点间的路径是唯一的 5、在生成树中再加一条边必然形成回路 6、含n个顶点n-1条边的图不一定是生成树

最小生成树：生成树的所有权值之和最小

构造最小生成树的方法：

1.普里姆算法

2.Kruskal算法

五、有向无环图（DAG图）（拓扑排序 + 关键路径）

AOV网–>用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。

拓扑排序–>把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。

拓扑排序的方法

（1）在有向图中选一个没有前驱的顶点且输出之； （2）从图中删除该顶点和所有以它为尾的弧 。 （3）重复上述两步，直至全部顶点均已输出；

AOE网(Activity On Edge)–>也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。

关键路径：由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为源点到终点的最长路径，该路径即为关键路径。

六、求最短路径

Dijkstra算法

转载地址：https://bupt-xbz.blog.csdn.net/article/details/77008464 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！