数据结构与算法之图论

图

1、基本概念

极大连通、极小连通、极大连通子图、极小连通子图、连通分量

• 极大连通

  在无向图中&＃xff0c;指的是任意两点都有直接或者间接的路径

• 极小连通

  在无向图中&＃xff0c;生成树就是一个极小连通&＃xff1b;如果加一条边就会形成一个环&＃xff0c;如果减一条边就会出现孤立的节点&＃xff1b;n个节点应该有n-1条边

• 极大连通子图和极小连通子图

  满足上述极大连通和极小连通的子图

• 连通分量

  指的是极大连通子图的数目

• 思考&＃xff1a;假如一个图有n个节点

  如果边数小于n-1的话&＃xff0c;此图必定是非连通图

  非连通图最多应该有 (n−1)(n−2)2\frac{(n-1)(n-2)}{2}2(n−1)(n−2)​ 条边 &＃xff0c;解释&＃xff1a;由n-1构成完全图&＃xff0c;如果此时再加入一条边&＃xff0c;那么就会形成连通图了

强连通图、强连通分量

• 强连通图

  有向图中&＃xff0c;任意两个顶点都有直接或者间接的路径到达&＃xff08;注意&＃xff0c;路径是有方向的&＃xff09;&＃xff0c;此图称为强连通图

• 强连通分量

  有向图的强连通子图的数量就是强连通分量&＃xff0c;书上是说‘有向图的极大连通子图就是强连通分量’

  如下图所示&＃xff0c;三个强连通分量 {1,2,3,4}, {5}, {6}

  

• 思考&＃xff1a;假如有n个节点的有向图

  强连通情况下&＃xff0c;至少需要n条边&＃xff1b;解释&＃xff1a;构成一个环就行了&＃xff0c;这样&＃xff0c;任意两点直接都可循环到达。

生成树与最小生成树

• 生成树

  无向图$G\&＃61;(V,E)$和无向图图G1&＃61;(V1,E1)G^1 &＃61; (V^1, E^1)G1&＃61;(V1,E1)&＃xff0c;若G1包含GG^1包含GG1包含G的所有顶点&＃xff0c;且边是$G$的子集&＃xff0c;那么G1就是G的生成树G^1就是G的生成树G1就是G的生成树

  生成树不唯一

  维基百科如下图定义

  

• 最小生成树

  每条边都有权值&＃xff0c;最小生成树就是最后生成的树&＃xff0c;权值和最小

2、最小生成树算法

Prim算法

Kruskal算法

3、最短路径算法

Dijkstra算法

Floyd算法

4、拓扑排序与关键路径&＃xff08;AOV与AOE&＃xff09;

5、Graphviz简单介绍

​ Graphviz是用来可视化图和树的工具&＃xff0c;常用.dot文件或者api进行操作&＃xff0c;官网链接。

用法一、dot文件使用

目前还不会使用这个软件&＃xff0c;先挖坑。