图论整理 顶
图的基本概念
根据之前博客数据结构整理 中，我们可以知道
是一种线性数据结构
是一种树结构
而这样一种结构就是一种图的结构
图的每一个点称为顶点(Vertex),通常我们会给顶点标上序号，而这些序号就可以理解为索引
当然这是一种抽象后的概念，在实际中，图可以表示为很多，比如社交网络
顶点与顶点相连的称为边(Edge)
而由以上的图中，由于各个顶点相邻的边是没有方向的，所以这种图又被称为无向图(Undirected Graph)，在无向图中，只要两个顶点相连，那么无论从哪个顶点出发都可以到达相邻的顶点。而类似于下图的图是有方向的
我们称之为有向图(Directed Graph)，在有向图中，只能够从起始顶点出发到达方向末端的相邻顶点，相反则不可以。所以我们在考虑现实关系建模的时候，要使用无向图还是有向图，比如地铁站点之间，无论从哪个站点出发都可以到达相邻的同一个线路的站点，所以要使用无向图。在社交网络中，如果是微信中，可以使用无向图，因为微信中人与人的关系是好友的关系。但有一些社交工具可能是一种关注的关系，而不是好友的关系。比如像下图中，Anne关注了Bob,而Bob并没有关注Anne,这样我们就必须使用有向图来进行建模。
如果一个图中，顶点与顶点的边只代表一种关系，而没有任何实际的度量，我们可以称这种图为无权图。而在有一些图中，它们的边代表具有一定的度量信息的意义。我们称这样的图为有权图。而这个权指的就是这些度量信息。
所以图的分类可以分为四种:
- 无向无权图
- 有向无权图
- 无向有权图
- 有向有权图
对于图的算法有一些只适合于某一类图，比如最小生成树算法只适用于有权图，拓扑排序算法只适用于有向图，最短路径算法虽然适用于所有类型的图，但是对于无向图和有向图的方式是不一样的。
在无向无权图中的概念
如果两个顶点之间有边，我们称为两点相邻
和一个顶点相邻的所有的边，我们成为点的邻边
从一个顶点到另一个顶点所经过的所有边，我们称为路径(Path)，比如下图中从0到6经过了0-1-6，当然从0到6不一定只有这一条路径。
从一个顶点出发，经过其他顶点最终回到起始顶点，我们称之为环(Loop),比如下图中的0-1-2-3-0就是一个环，当然0-1-6-5-4-3-0也是一个环。
对于单个顶点来说也可以有一条自己到自己的边，我们称为自环边,如下图中的0-0。每两个相邻到顶点也可能不只一条边，我们可以称为平行边，如下图中的3-4。大多数情况下自环边和平行边没有意义，一般我们在处理自环边和平行边的时候都是先将其去除，变成没有自环边和平行边的图。当然也有自环边和平行边存在意义的场景，但是这种情况比较少。在图论中，我们称没有自环边和平行边的图为简单图。
当然在一个图中，并不是所有的顶点都必须是相连的
我们称在一张图中可以相互连接抵达的顶点的集合为联通分量，所以上面这张图中就有2个联通分量。因此一个图的所有节点不一定全部相连。一个图可能是有多个联通分量。
这种有环的图，我们可以称为有环图。
像这种无法找到从一个顶点出发，经过其他顶点又回到起始顶点的，我们称为无环图。但它又满足树的定义的，所以树是一种无环图。我们在图论中谈到树的定义跟在数据结构中说的树不完全是一个概念，图论中的树的根节点可以是任意节点，而数据结构中说的树往往是固定的一个根节点。虽然树是一种无环图，但一个无环图不一定是树。
由上图可知，它是一个有2个联通分量的图，但可以肯定的是1个联通的无环图是树。
由该图我们可以看到，右边的图跟左边的图的顶点是一样的，区别只在于边，右边的图的边是左边的图的边的子集。我们将左边的图的一些边删除，就可以得到右边的图。同时右边的图还是一个树的形状。那么这个过程就可以称为联通图的生成树。由于树必须是联通的，所以只有联通图才有可能生成树。并且该生成树包含原联通图所有的顶点的树。这个树也是保障原联通图可以联通，并且边数最小的那个图，所以该树的边数为：V - 1，这里的V为顶点数。
但是反过来说，我们将一个联通图删边，包含所有的顶点，边数为V - 1,却不一定是联通图的生成树。如下面这个图，它就已经不再联通了，并且产生了环。
那么一个图不一定有生成树，这个图必须是一个联通的图。但是一个图一定有生成深林。一个联通图一定有生成树。对于不止一个联通分量的图，我们可以将各个联通分量生成树，进而获得生成森林。
在无向图中，一个顶点的度(degree)，就是这个顶点相邻的边数，这里也是在说简单图，不考虑自环边和平行边。但在一个有向图中，一个顶点的度的概念不同。所以我们可以看到下图中0这个顶点有两个邻边0-1、0-3，所以0这个顶点的度就是2.
- 无权无向图的邻接矩阵
接口
public interface Adj {
int getV();
int getE();
/**
* 是否存在某条边
* @param v
* @param w
* @return
*/
boolean hasEdge(int v,int w);
/**
* 获取和顶点相邻的边
* @param v
* @return
*/
Collection<Integer> adj(int v);
/**
* 求一个顶点的度(顶点有多少个邻边)
* @param v
* @return
*/
int degree(int v);
/**
* 检测一个顶点的索引是否有效
* @param v
*/
void validateVertex(int v);
}实现类
/**
* 只支持处理简单图
*/
public class AdjMatrix implements Adj {
//顶点数
private int V;
//边数
private int E;
//邻接矩阵
private int[][] adj;
public AdjMatrix(String filename) {
File file = new File(filename);
try (Scanner scanner = new Scanner(file)) {
V = scanner.nextInt();
if (V < 0) {
throw new IllegalArgumentException("V必须为非负数");
}
adj = new int[V][V];
E = scanner.nextInt();
if (E < 0) {
throw new IllegalArgumentException("E必须为非负数");
}
for (int i = 0;i < E;i++) {
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if (a == b) {
throw new IllegalArgumentException("检测到自环边");
}
if (adj[a][b] == 1) {
throw new IllegalArgumentException("检测到平行边");
}
adj[a][b] = 1;
adj[b][a] = 1;
}
}catch (IOException e) {
e.printStackTrace();
}
}
@Override
public int getV() {
return V;
}
@Override
public int getE() {
return E;
}
@Override
public boolean hasEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
return adj[v][w] == 1;
}
@Override
public Collection<Integer> adj(int v) {
validateVertex(v);
List<Integer> res = new ArrayList<>();
for (int i = 0;i < V;i++) {
if (adj[v][i] == 1) {
res.add(i);
}
}
return res;
}
@Override
public int degree(int v) {
return adj(v).size();
}
@Override
public void validateVertex(int v) {
if (v < 0 || v >= V) {
throw new IllegalArgumentException("顶点" + v + "无效");
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("V = %d,E = %d\n",V,E));
for (int i = 0;i < V;i++) {
for (int j = 0;j < V;j++) {
builder.append(String.format("%d ",adj[i][j]));
}
builder.append("\n");
}
return builder.toString();
}
public static void main(String[] args) {
Adj adjMatrix = new AdjMatrix("/Users/admin/Downloads/g.txt");
System.out.println(adjMatrix);
}
}g.txt中的内容(第一行表示有7个顶点，9条边；第二行到最后表示哪个顶点与哪个顶点相连)
7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6运行结果
V = 7,E = 9
0 1 0 1 0 0 0
1 0 1 0 0 0 1
0 1 0 1 0 1 0
1 0 1 0 1 0 0
0 0 0 1 0 1 0
0 0 1 0 1 0 1
0 1 0 0 0 1 0
时间复杂度和空间复杂度
空间复杂度 O(V^2)
时间复杂度
建图 O(E)
查看两个节点是否相邻 O(1)
求一个点的相邻节点 O(V)
- 无权无向图的邻接表
从邻接矩阵的空间复杂度O(V^2)来看，如果一个图有3000个顶点，如果这个图是一个树的话，那么我们只存储顶点加边需要存储3000 + (3000 - 1)个信息，就是5999个信息，但如果使用邻接矩阵的话，则需要存储3000^2个信息，即9000000个信息，我们可以看到这个差距是巨大的。
求一个点的相邻节点的时间复杂度是O(V)的，但其实这个相邻节点的数量就等于该节点的度，而在邻接矩阵中，我们需要扫描全部3000个顶点才能确认一个顶点的相邻节点，这其实也造成了大量的浪费。如果能找出一个O(degree(v))的算法，那么将比O(V)要小的多。
稀疏图和稠密图
这里稀疏和稠密是指边的多少。如果一个图是一个树的话，那么它肯定是一个稀疏图，因为树是所有图里面边最少的图。但是一个有环图并不一定是一个稠密图。假如一个有环无向图有3000个顶点，每个顶点的度为3，那么这个图有3000 * 3 / 2 = 4500条边。那这个图最多可以有3000 * 2999 / 2 = 4498500条边，它表示每一个顶点都跟剩下的2999个顶点相连，所以每一个顶点的度为2999。那么4500条边和4498500相比相差了将近1000倍，是一个很大的量级了。
比如说对于上面这个图，我们看起来可能很稠密，但其实它只是一个稀疏图。因为在该图中度数最大的顶点的度也不过是6、7的样子。虽然这个图的顶点个数大概有几十个，但图中的边数比起它所能容纳的最多的边数，其实是少很多的。
而上图就是一个典型的稠密图，虽然图中只有21个顶点，要远远少于之前的稀疏图，但是它每一个顶点都跟剩余的20个顶点相连，形成的边数非常多。对于这种每一个顶点跟剩余所有的顶点相连的图，我们称为完全图。在图论中，我们处理的大多数问题其实都是稀疏图。因为在现实中，我们对具体的问题进行建模的时候，完全图或者稠密图是非常少的。但是稀疏图和稠密图之间并没有一个黑白分明的界限，没有固定的标准。但我们可以用一个顶点的度/顶点在完全图中的度来进行比较，它可能是比1/2，1/10，1/100还要少，一般都是稀疏图。
用邻接矩阵来表示一个图的缺点：如果一个图是比较稀疏的话，那么它的空间复杂度会比较高。求一个顶点的相邻顶点所耗费的时间也比较多。而实际生活所处理的图都是稀疏的。所以鉴于邻接矩阵的空间复杂度过大，且相邻节点的时间复杂度较大。我们就使用邻接表来表示这个图
实现类
public class AdjList implements Adj {
//顶点数
private int V;
//边数
private int E;
//邻接表
private List<Integer>[] adj;
@SuppressWarnings("unchecked")
public AdjList(String filename) {
File file = new File(filename);
try (Scanner scanner = new Scanner(file)) {
V = scanner.nextInt();
if (V < 0) {
throw new IllegalArgumentException("V必须为非负数");
}
adj = new LinkedList[V];
for (int i = 0;i < V;i++) {
adj[i] = new LinkedList<>();
}
E = scanner.nextInt();
if (E < 0) {
throw new IllegalArgumentException("E必须为非负数");
}
for (int i = 0;i < E;i++) {
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if (a == b) {
throw new IllegalArgumentException("检测到自环边");
}
if (adj[a].contains(b)) {
throw new IllegalArgumentException("检测到平行边");
}
adj[a].add(b);
adj[b].add(a);
}
}catch (IOException e) {
e.printStackTrace();
}
}
@Override
public int getV() {
return V;
}
@Override
public int getE() {
return E;
}
@Override
public boolean hasEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
@Override
public Collection<Integer> adj(int v) {
validateVertex(v);
return adj[v];
}
@Override
public int degree(int v) {
return adj(v).size();
}
@Override
public void validateVertex(int v) {
if (v < 0 || v >= V) {
throw new IllegalArgumentException("顶点" + v + "无效");
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("V = %d,E = %d\n",V,E));
for (int v = 0;v < V;v++) {
builder.append(String.format("%d :",v));
adj[v].stream().map(w -> String.format("%d ",w))
.forEach(builder::append);
builder.append("\n");
}
return builder.toString();
}
public static void main(String[] args) {
Adj adjList = new AdjList("/Users/admin/Downloads/g.txt");
System.out.println(adjList);
}
}运行结果
V = 7,E = 9
0 :1 3
1 :0 2 6
2 :1 3 5
3 :0 2 4
4 :3 5
5 :2 4 6
6 :1 5
空间复杂度 O(V + E)
时间复杂度
建图 O(E * V) 之所以要乘以V是因为检测平行边的时候，需要遍历顶点邻接的所有顶点，如果在一个完全图下，就要遍历所有的顶点， 而链表是一个线性结构，所以时间复杂度最坏的情况下会有V这么大。这也是一个查重的过程。
查看两点是否相邻 O(degree(v))，最差情况下的完全图中就是O(V)
求一个点的相邻节点 O(degree(v)), 最差情况下的完全图中就是O(V)
通过上面的复杂度，我们可以看到邻接表相比于邻接矩阵，它有两点不足。
- 建图的时间复杂度O(E * V)相比邻接矩阵的O(E)要大很多，如果图的顶点数很多，那么这么差别也是巨大的。
- 查看两点是否相邻O(degree(v))在邻接矩阵中是O(1)级别的
将以上的问题提取出来，就是要快速查重和快速查看两点是否相邻
要解决以上的问题，我们就不能使用链表(LinkedList),我们可以使用哈希表(HashSet,时间复杂度O(1)),或者使用红黑树(TreeSet，时间复杂度O(log V)).
由于红黑树保证了顶点索引的顺序性，我们使用红黑树来进行转变。而哈希表无法达到该要求，但由于哈希表的时间复杂度更低，如果对顶点没有顺序要求，则使用哈希表更优，在通常的解题过程中推荐使用哈希表。相比哈希表，红黑树更节省空间。
实现类
public class AdjSet implements Adj {
//顶点数
private int V;
//边数
private int E;
//邻接表
private Set<Integer>[] adj;
@SuppressWarnings("unchecked")
public AdjSet(String filename) {
File file = new File(filename);
try (Scanner scanner = new Scanner(file)) {
V = scanner.nextInt();
if (V < 0) {
throw new IllegalArgumentException("V必须为非负数");
}
adj = new TreeSet[V];
for (int i = 0;i < V;i++) {
adj[i] = new TreeSet<>();
}
E = scanner.nextInt();
if (E < 0) {
throw new IllegalArgumentException("E必须为非负数");
}
for (int i = 0;i < E;i++) {
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if (a == b) {
throw new IllegalArgumentException("检测到自环边");
}
if (adj[a].contains(b)) {
throw new IllegalArgumentException("检测到平行边");
}
adj[a].add(b);
adj[b].add(a);
}
}catch (IOException e) {
e.printStackTrace();
}
}
@Override
public int getV() {
return V;
}
@Override
public int getE() {
return E;
}
@Override
public boolean hasEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
@Override
public Collection<Integer> adj(int v) {
validateVertex(v);
return adj[v];
}
@Override
public int degree(int v) {
return adj(v).size();
}
@Override
public void validateVertex(int v) {
if (v < 0 || v >= V) {
throw new IllegalArgumentException("顶点" + v + "无效");
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("V = %d,E = %d\n",V,E));
for (int v = 0;v < V;v++) {
builder.append(String.format("%d :",v));
adj[v].stream().map(w -> String.format("%d ",w))
.forEach(builder::append);
builder.append("\n");
}
return builder.toString();
}
public static void main(String[] args) {
Adj adjset = new AdjSet("/Users/admin/Downloads/g.txt");
System.out.println(adjset);
}
}运行结果
V = 7,E = 9
0 :1 3
1 :0 2 6
2 :1 3 5
3 :0 2 4
4 :3 5
5 :2 4 6
6 :1 5
空间复杂度 O(V + E)
时间复杂度
建图 O(E * log V) 相比于链表，红黑树的查重的时间复杂度就要低的多
查看两点是否相邻 O(log V)
求一个点的相邻节点 O(degree(v)), 最差情况下的完全图中就是O(V)
当然我们也可以使用哈希表来实现
实现类
public class AdjHash implements Adj {
//顶点数
private int V;
//边数
private int E;
//邻接表
private Set<Integer>[] adj;
@SuppressWarnings("unchecked")
public AdjHash(String filename) {
File file = new File(filename);
try (Scanner scanner = new Scanner(file)) {
V = scanner.nextInt();
if (V < 0) {
throw new IllegalArgumentException("V必须为非负数");
}
adj = new HashSet[V];
for (int i = 0;i < V;i++) {
adj[i] = new HashSet<>();
}
E = scanner.nextInt();
if (E < 0) {
throw new IllegalArgumentException("E必须为非负数");
}
for (int i = 0;i < E;i++) {
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
if (a == b) {
throw new IllegalArgumentException("检测到自环边");
}
if (adj[a].contains(b)) {
throw new IllegalArgumentException("检测到平行边");
}
adj[a].add(b);
adj[b].add(a);
}
}catch (IOException e) {
e.printStackTrace();
}
}
@Override
public int getV() {
return V;
}
@Override
public int getE() {
return E;
}
@Override
public boolean hasEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
@Override
public Collection<Integer> adj(int v) {
validateVertex(v);
return adj[v];
}
@Override
public int degree(int v) {
return adj(v).size();
}
@Override
public void validateVertex(int v) {
if (v < 0 || v >= V) {
throw new IllegalArgumentException("顶点" + v + "无效");
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("V = %d,E = %d\n",V,E));
for (int v = 0;v < V;v++) {
builder.append(String.format("%d :",v));
adj[v].stream().map(w -> String.format("%d ",w))
.forEach(builder::append);
builder.append("\n");
}
return builder.toString();
}
public static void main(String[] args) {
Adj adjhash = new AdjHash("/Users/admin/Downloads/g.txt");
System.out.println(adjhash);
}
}运行结果
V = 7,E = 9
0 :1 3
1 :0 2 6
2 :1 3 5
3 :0 2 4
4 :3 5
5 :2 4 6
6 :1 5
空间复杂度 O(V + E)
时间复杂度
建图 O(E)
查看两点是否相邻 O(1)
求一个点的相邻节点 O(degree(v)), 最差情况下的完全图中就是O(V)，但使用哈希表则无法按照邻接顶点的顺序来输出
为了保证邻接顶点的顺序性，后续以使用红黑树为主。
- 无权无向图的深度优先遍历
在之前的数据结构整理 中，我们知道二分搜索树的深度优先遍历为前序遍历，中序遍历和后序遍历。
我们来看一下前序遍历
private void preOrder(Node node) {
if (node == null) {
return;
}
list.add(node.getElement()); //遍历
preOrder(node.getLeft()); //访问所有子树，遍历和node相邻的其他node
preOrder(node.getRight());
}在二分搜索树中，它的节点为一个Node的对象，而在图中的节点为一个顶点的索引值。根据二分搜索树的遍历方式，图的深度优先遍历也是添加节点，再访问跟顶点相邻的其他顶点，这个是没有变的。只不过和图的顶点相邻的可能不只两个顶点，可能有多个，所以我们要通过adj()方法获取一个顶点所有相邻的顶点。但跟二分搜索树不同的是，我们要判断哪些顶点被访问过，要有一个记录，我们放在一个数组visited中，如果w这个顶点没有被访问过的话，相应的我们去递归调用w这个顶点就好了。之所以在二分搜索树中不需要考虑节点有没有被访问过，是因为树中没有环，所以节点的左右子树是一定没有被访问过的，但是在图中因为有环的存在，所以一定要判断这个节点是否被访问过。对于图的深度优先遍历的递归的终止条件就是对于我们当前的这个v或者一个相邻的顶点都没有，或者它的所有的相邻的节点都已经被遍历过了，就不需要继续递归下去了，递归函数就会直接终止。换句话说，要么G.adj(v)为空，要么.filter(w -> !visitedw)为空，则.forEach(this::dfs)都不会继续执行，递归结束。
private void dfs(int v) {
visited[v] = true;
list.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs); //相当于.forEach(w -> dfs(w))
}在具体调用上，我们可以从任意一个顶点出发，比如我们就从0这个顶点出发。
dfs(0);我们用一个全流程图来说明整个过程
假设有这么一个图，它的邻接表如右边所示，此时我们建立一个visited数组
visted 0 1 2 3 4 5 6
依然从0开始遍历dfs(0)，此时0被遍历过了，我们找到0的相邻节点1、2.
visted 0 1 2 3 4 5 6
遍历结果: 0
由于1和2都没有被遍历，此时dfs(0) -> dfs(1),我们再找到1的相邻节点0、3、4
visted 0 1 2 3 4 5 6
遍历结果: 0 1
由于0被遍历过了，此时我们过滤出来的为3、4，则我们开始遍历3，dfs(0) -> dfs(1) -> dfs(3)
visted 0 1 2 3 4 5 6
遍历结果: 0 1 3
我们再找到3的相邻节点1、2、5，由于1被遍历过，此时我们过滤出来的为2、5，则我们开始遍历2，dfs(0) -> dfs(1) -> dfs(3) -> dfs(2)
visted 0 1 2 3 4 5 6
遍历结果: 0 1 3 2
我们再找到2的相邻节点0、3、6，由于0、3都被遍历过，此时我们过滤出来的为6，则我们开始遍历6，dfs(0) -> dfs(1) -> dfs(3) -> dfs(2) -> dfs(6)
visted 0 1 2 3 4 5 6
遍历结果: 0 1 3 2 6
我们再找到6的相邻节点2、5，由于2被遍历过，此时我们过滤出来的为5，则我们开始遍历5，dfs(0) -> dfs(1) -> dfs(3) -> dfs(2) -> dfs(6) -> dfs(5)
visted 0 1 2 3 4 5 6
遍历结果: 0 1 3 2 6 5
我们再找到5的相邻节点3、6，由于3、6都被遍历过，此时我们过滤出来的结果为空，此次递归结束，返回上层递归dfs(6);但由于6的相邻节点2、5都被遍历过了，返回上层递归dfs(2);2的相邻节点0、3、6都被遍历过了，返回上层递归dfs(3);3的相邻节点1、2、5都被遍历过了，返回上层递归dfs(1)；1的相邻节点为0、3、4，其中4没有被遍历过，所以过滤出来的节点为4，则我们开始遍历4，dfs(0) -> dfs(1) -> dfs(4)
visted 0 1 2 3 4 5 6
遍历结果: 0 1 3 2 6 5 4
我们再找到4的相邻节点为1，由于1被遍历过了，返回上层递归dfs(1),1的相邻节点为0、3、4都被遍历过了，返回上层递归dfs(0),0的相邻节点1、2都被遍历过了，而0又是递归调用的顶层，所以全部递归结束，全部结果就是0 1 3 2 6 5 4.
我们先新建一个h.txt,内容为
7 8
0 1
0 2
1 3
1 4
2 3
2 6
3 5
5 6接口
public interface DFS {
List<Integer> getPre();
List<Integer> getPost();
}深度优先遍历类
/**
* 深度优先遍历
*/
public class GraphDFS implements DFS {
private Adj G;
//访问过的顶点
private boolean[] visited;
private List<Integer> pre = new ArrayList<>();
public GraphDFS(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
dfs(0);
}
private void dfs(int v) {
visited[v] = true;
pre.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return null;
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFS(g);
System.out.println(graphDFS.getOrder());
}
}运行结果
0, 1, 3, 2, 6, 5, 4
深度优先遍历的改进
如上图所示，当我们的图有多个联通分量的时候，上面的算法就无法遍历所有的顶点，所以我们需要对整个深度优先遍历类进行一个改进
/**
* 深度优先遍历
*/
public class GraphDFS implements DFS {
private Adj G;
//访问过的顶点
private boolean[] visited;
private List<Integer> pre = new ArrayList<>();
public GraphDFS(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
dfs(v);
}
}
}
private void dfs(int v) {
visited[v] = true;
pre.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return null;
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFS(g);
System.out.println(graphDFS.getOrder());
}
}修改一下h.txt的内容，使其变成两个联通分量的图
7 6
0 1
0 2
1 3
1 4
2 3
2 6运行结果
0, 1, 3, 2, 6, 4, 5
- 无权无向图的深度优先先序遍历和深度优先后序遍历
在之前的二分搜索树的深度遍历中分成了前序遍历，中序遍历，后序遍历
1、前序遍历
private void preOrder(Node node) {
if (node == null) {
return;
}
list.add(node.getElement());
preOrder(node.getLeft());
preOrder(node.getRight());
}2、中序遍历
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.getLeft());
list.add(node.getElement());
inOrder(node.getRight());
}3、后序遍历
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.getLeft());
postOrder(node.getRight());
list.add(node.getElement());
}那么对于二分搜索树的这个概念同样适合于图
private void dfs(int v) {
visited[v] = true;
list.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
}在这种在遍历节点前添加元素的，我们称为深度优先先序遍历
private void dfs(int v) {
visited[v] = true;
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
list.add(v);
}在这种在遍历节点后添加元素的，我们称为深度优先后序遍历
现在我们将这两中遍历出来的元素都进行一下存储
/**
* 深度优先遍历
*/
public class GraphDFS implements DFS{
private Adj G;
//访问过的顶点
private boolean[] visited;
//深度优先前序遍历结果
private List<Integer> pre = new ArrayList<>();
//深度优先后续遍历结果
private List<Integer> post = new ArrayList<>();
public GraphDFS(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
dfs(v);
}
}
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return post;
}
private void dfs(int v) {
visited[v] = true;
pre.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
post.add(v);
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFS(g);
System.out.println(graphDFS.getPre());
System.out.println(graphDFS.getPost());
}
}运行结果
0, 1, 3, 2, 6, 4, 5
6, 2, 3, 4, 1, 0, 5
不过由于图的顶点的相邻节点可能不只2个，所以它并没有二叉树的中序遍历。不但图没有，多叉树也没有，仅仅只有二叉树才会有中序遍历。而图的深度优先后序遍历往往在某些条件下会起到很大的作用。
时间复杂度 O(V + E)
- 无权无向图的非递归深度优先遍历
我们来看一下二分搜索树的非递归前序遍历
public void preOrderNR() {
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
Node cur = stack.pop();
list.add(cur.getElement());
if (cur.getRight() != null) {
stack.push(cur.getRight());
}
if (cur.getLeft() != null) {
stack.push(cur.getLeft());
}
}
}那么图的非递归深度优先遍历跟二分搜索树一样，只不过，我们需要对于每一个节点，用visited数组判断一下，这个节点是否已经被遍历过了
/**
* 深度优先遍历
*/
public class GraphDFSNoRecursion implements DFS {
private Adj G;
//访问过的顶点
private boolean[] visited;
//深度优先前序遍历结果
private List<Integer> pre = new ArrayList<>();
public GraphDFSNoRecursion(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
dfs(v);
}
}
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return null;
}
private void dfs(int v) {
Stack<Integer> stack = new Stack<>();
stack.push(v);
visited[v] = true;
while (!stack.empty()) {
int cur = stack.pop();
pre.add(cur);
G.adj(cur).stream().filter(w -> !visited[w])
.forEach(w -> {
stack.push(w);
visited[w] = true;
});
}
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFSNoRecursion(g);
System.out.println(graphDFS.getPre());
}
}运行结果
0, 2, 6, 3, 1, 4, 5
在二分搜索树中，非递归的前序遍历跟递归的前序遍历的结果是一样的，因为它是严格根据左右子树的规律来进行入栈和出栈(先右后左)，不过在图中，栈的后进先出特性并不能让其与递归的结果顺序保持一致。
至于此，如果不保证结果与递归结果相同的顺序性，当然可以用栈也可以用队列
/**
* 深度优先遍历
*/
public class GraphDFSQueue implements DFS {
private Adj G;
//访问过的顶点
private boolean[] visited;
//深度优先前序遍历结果
private List<Integer> pre = new ArrayList<>();
public GraphDFSQueue(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
dfs(v);
}
}
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return null;
}
private void dfs(int v) {
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
visited[v] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
pre.add(cur);
G.adj(cur).stream().filter(w -> !visited[w])
.forEach(w -> {
queue.add(w);
visited[w] = true;
});
}
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFSQueue(g);
System.out.println(graphDFS.getPre());
}
}运行结果
0, 1, 2, 3, 4, 6, 5
- 联通分量的个数
接口
public interface CC {
int getCCCount();
}实现类
/**
* 深度优先遍历
*/
public class GraphDFS implements DFS,CC {
private Adj G;
//访问过的顶点
private boolean[] visited;
//深度优先前序遍历结果
private List<Integer> pre = new ArrayList<>();
//深度优先后续遍历结果
private List<Integer> post = new ArrayList<>();
//联通分量个数
private int cccount = 0;
public GraphDFS(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
dfs(v);
cccount++;
}
}
}
@Override
public List<Integer> getPre() {
return pre;
}
@Override
public List<Integer> getPost() {
return post;
}
@Override
public int getCCCount() {
return cccount;
}
private void dfs(int v) {
visited[v] = true;
pre.add(v);
G.adj(v).stream().filter(w -> !visited[w])
.forEach(this::dfs);
post.add(v);
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
DFS graphDFS = new GraphDFS(g);
System.out.println(graphDFS.getPre());
System.out.println(graphDFS.getPost());
System.out.println(((CC)graphDFS).getCCCount());
}
}运行结果
0, 1, 3, 2, 6, 4, 5
6, 2, 3, 4, 1, 0, 5
2
- 检测两个顶点是否在一个联通分量中以及获取各个联通分量各自的顶点
接口
public interface CCN extends CC {
/**
* 检测两个顶点是否联通
* @param v
* @param w
* @return
*/
boolean isConnected(int v,int w);
/**
* 获取各个联通分量各自的顶点
* @return
*/
List<Integer>[] components();
}实现类
/**
* 检测两个顶点是否在同一个联通分量中
*/
public class GraphDFSCC implements CCN {
private Adj G;
//访问过的顶点
private Integer[] visited;
//联通分量个数
private int cccount = 0;
public GraphDFSCC(Adj G) {
this.G = G;
visited = new Integer[G.getV()];
for (int i = 0;i < visited.length;i++) {
visited[i] = -1;
}
for (int v = 0;v < G.getV();v++) {
if (visited[v] == -1) {
dfs(v,cccount);
cccount++;
}
}
}
@Override
public int getCCCount() {
Stream.of(visited).map(v -> v + " ")
.forEach(System.out::print);
System.out.println();
return cccount;
}
@Override
public boolean isConnected(int v, int w) {
G.validateVertex(v);
G.validateVertex(w);
return visited[v] == visited[w];
}
@Override
@SuppressWarnings("unchecked")
public List<Integer>[] components() {
List<Integer>[] res = new ArrayList[cccount];
for (int i = 0;i < cccount;i++) {
res[i] = new ArrayList<>();
}
for (int v = 0;v < G.getV();v++) {
res[visited[v]].add(v);
}
return res;
}
private void dfs(int v, int ccid) {
visited[v] = ccid;
G.adj(v).stream().filter(w -> visited[w] == -1)
.forEach(w -> dfs(w,ccid));
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
CCN graphDFS = new GraphDFSCC(g);
System.out.println(graphDFS.getCCCount());
System.out.println(graphDFS.isConnected(1,6));
List<Integer>[] comp = graphDFS.components();
for (int ccid = 0;ccid < comp.length;ccid++) {
System.out.print(ccid + " : ");
comp[ccid].stream().map(w -> w + " ")
.forEach(System.out::print);
System.out.println();
}
}
}运行结果
0 0 0 0 0 1 0
2
true
0 : 0 1 2 3 4 6
1 : 5
- 单一源路径
我们这条路径为可能的一条连接路径，但未必是最短路径。为了便于观察，我们还是下面这个2个联通分量到图。
接口
public interface Path {
/**
* 从源到顶点t是否联通
* @param t
* @return
*/
boolean isConnectedTo(int t);
/**
* 从源到顶点t所经过的路径
* @param t
* @return
*/
Collection<Integer> path(int t);
}实现类
/**
* 单源路径
*/
public class SingleSourcePath implements Path {
private Adj G;
//源
private int source;
//访问过的顶点
private boolean[] visited;
//路径前节点
private int[] pre;
public SingleSourcePath(Adj G,int source) {
G.validateVertex(source);
this.G = G;
this.source = source;
visited = new boolean[G.getV()];
pre = new int[G.getV()];
for (int i = 0;i < pre.length;i++) {
pre[i] = -1;
}
//我们定义源节点的父节点为它自己
dfs(source,source);
}
@Override
public boolean isConnectedTo(int t) {
G.validateVertex(t);
return visited[t];
}
@Override
public Collection<Integer> path(int t) {
List<Integer> res = new ArrayList<>();
if (!isConnectedTo(t)) {
throw new IllegalArgumentException("源顶点" + source +
"到目标顶点" + t + "未联通");
}
int cur = t;
while (cur != source) {
res.add(cur);
cur = pre[cur];
}
res.add(source);
Collections.reverse(res);
return res;
}
/**
* 深度遍历
* @param v 需要遍历的顶点
* @param parent v的上一个顶点(从哪来的)
*/
private void dfs(int v,int parent) {
visited[v] = true;
pre[v] = parent;
G.adj(v).stream().filter(w -> !visited[w])
.forEach(w -> dfs(w,v));
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
Path graphDFS = new SingleSourcePath(g,0);
System.out.println("0 -> 6 : " + graphDFS.path(6));
System.out.println("0 -> 5 : " + graphDFS.path(5));
}
}运行结果
0 -> 6 : 0, 1, 3, 2, 6
Exception in thread "main" java.lang.IllegalArgumentException: 源顶点0到目标顶点5未联通
at com.cgc.cloud.middlestage.user.graph.SingleSourcePath.path(SingleSourcePath.java:43) at com.cgc.cloud.middlestage.user.graph.SingleSourcePath.main(SingleSourcePath.java:72)单一源路径的优化
由于我们在单源路径算法中的深度优先遍历里其实是遍历了连接的所有顶点，而我们的目标其实只是为了找出一条从源到目标相连的路径，其实并不一定要遍历所有连接的顶点，只要找到目标顶点即返回，所以我们做如下的修改。
接口
public interface TPath {
/**
* 从源到顶点t是否联通
* @return
*/
boolean isConnected();
/**
* 从源到顶点t所经过的路径
* @return
*/
Collection<Integer> path();
}实现类
/**
* 单源路径
*/
public class OncePath implements TPath {
private Adj G;
//源
private int source;
//目标
private int target;
//访问过的顶点
private boolean[] visited;
//路径前节点
private int[] pre;
public OncePath(Adj G, int source,int target) {
G.validateVertex(source);
G.validateVertex(target);
this.G = G;
this.source = source;
this.target = target;
visited = new boolean[G.getV()];
pre = new int[G.getV()];
for (int i = 0;i < pre.length;i++) {
pre[i] = -1;
}
//我们定义源节点的父节点为它自己
dfs(source,source);
for (boolean e : visited) {
System.out.print(e + " ");
}
System.out.println();
}
@Override
public boolean isConnected() {
return visited[target];
}
@Override
public Collection<Integer> path() {
List<Integer> res = new ArrayList<>();
if (!isConnected()) {
throw new IllegalArgumentException("源顶点" + source +
"到目标顶点" + target + "未联通");
}
int cur = target;
while (cur != source) {
res.add(cur);
cur = pre[cur];
}
res.add(source);
Collections.reverse(res);
return res;
}
/**
* 深度遍历
* @param v 需要遍历的顶点
* @param parent v的上一个顶点(从哪来的)
*/
private boolean dfs(int v,int parent) {
visited[v] = true;
pre[v] = parent;
if (v == target) {
return true;
}
for (int w : G.adj(v)) {
if (!visited[w]) {
if (dfs(w,v)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
TPath path1 = new OncePath(g,0,3);
System.out.println("0 -> 3 : " + path1.path());
TPath path2 = new OncePath(g,0,5);
System.out.println("0 -> 5 : " + path2.path());
}
}运行结果
true true false true false false false
0 -> 3 : 0, 1, 3
true true true true true false true
Exception in thread "main" java.lang.IllegalArgumentException: 源顶点0到目标顶点5未联通
at com.cgc.cloud.middlestage.user.graph.OncePath.path(OncePath.java:50) at com.cgc.cloud.middlestage.user.graph.OncePath.main(OncePath.java:89)由结果可知，当我们遍历到了目标顶点后，其他的顶点将不会去遍历，所以结果第一行只有第一、第二、第四个是true,其他都是false；而如果从源顶点到目标顶点是不联通的，则会遍历完整个联通变量中的节点，所以结果第三行里只有代表5的节点是false，其他都是true.
- 无向图的环检测
当我们要判断一个图中是否有环的时候，不论这个图是否有多个联通分量。我们在检测环的时候，最主要要看遍历的顶点的相邻节点是否是已经访问过的，且这个访问过的节点不是正在被遍历的这个顶点的父节点。
比如说我们从0开始遍历到1，我们看1的相邻节点有0、3、4.虽然0是被遍历过的，但是0是1的父节点，显然它不满足一个环。于是我们遍历到3.
3的相邻节点为1、2。1虽然被访问过，但而1是3的父节点，于是我们遍历到了2.
2的相邻节点有0和6，0是被遍历过的，且0不是2的父节点，所以我们此时可以断定，该图中有环。
环检测类
/**
* 无向图的环检测
*/
public class CycleDetection {
private Adj G;
//访问过的顶点
private boolean[] visited;
//是否有环
@Getter
private boolean hasCycle = false;
public CycleDetection(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
if (dfs(v,v)) {
hasCycle = true;
break;
}
}
}
}
/**
* 从顶点v开始，判断图中是否有环
* @param v
* @param parent
* @return
*/
private boolean dfs(int v,int parent) {
visited[v] = true;
for (int w : G.adj(v)) {
if (!visited[w]) {
if (dfs(w,v)) {
return true;
}
}else if (w != parent) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
CycleDetection graphDFS = new CycleDetection(g);
System.out.println(graphDFS.isHasCycle());
}
}运行结果
true
- 二分图检测
二分图的概念
- 顶点V可以分成不相交的两部分。
- 所有的边的两个端点隶属不同的部分。
虽然根据上图中，我们可以很清晰的看出这是一个二分图，但是其实它就是下面这张图
这张图就不是那么一眼看出是一个二分图了。
二分图检测类
/**
* 二分图检测
*/
public class BipartitionDetection {
private Adj G;
//访问过的顶点
private boolean[] visited;
//各顶点的染色
private int[] colors;
//是否是一个二分图
private boolean isBipartite = true;
public BipartitionDetection(Adj G) {
this.G = G;
visited = new boolean[G.getV()];
colors = new int[G.getV()];
for (int i = 0;i < colors.length;i++) {
colors[i] = -1;
}
for (int v = 0;v < G.getV();v++) {
if (!visited[v]) {
if (!dfs(v,0)) {
isBipartite = false;
break;
}
}
}
}
/**
* 检测是否是二分图
* @param v
* @param color
* @return
*/
private boolean dfs(int v,int color) {
visited[v] = true;
colors[v] = color;
for (int w : G.adj(v)) {
if (!visited[w]) {
if (!dfs(w,1 - color)) {
return false;
}
}else if (colors[w] == colors[v]) {
return false;
}
}
return true;
}
public boolean isBipartite() {
return isBipartite;
}
public static void main(String[] args) {
Adj g = new AdjSet("/Users/admin/Downloads/h.txt");
BipartitionDetection graphDFS = new BipartitionDetection(g);
System.out.println(graphDFS.isBipartite());
}
}运行结果
true