大厂必备技能:数据结构图之无向图

在前面的文章中，咱们将树的知识全部讲完。相信大家在不断的学习过程中，自己也能体会到一些很有意思的思想。在咱们前面的文章中，咱们将特别经典的二叉树、二三查找树、红黑树、B树以及B+树的知识详细讲解了一遍，并且手写了一些简单的代码来帮助咱们进行消化理解，相信对正在学习的同学理解一些底层设计会有一定的帮助。

在今天这篇文章中呢，咱们开始新的一种数据结构，也就是继数组、链表、树之后一种全新的数据结构，同时也是咱们数据结构最后的一种独立结构，也就是咱们本篇文章将要讲解的图结构。

图这种数据结构相比树又会复杂很多，咱们可以这样说，链表是最简单的一种数据结构，因为它总是表示的一对一的关系，理解以及实现起来特别简单，本质上就是一个线性表，从头指到尾即可。而咱们的树反映的则是一对多的关系，比如一棵二叉树具有左右两个子结点。咱们的图也是最难得一种数据结构，反映的是多对多的关系。所以说呢，咱们针对这个知识点，学习起来会有一定的难度，但是只要坚持下来，一切问题都会迎刃而解。今天呢，我们讲解一下无向图。

一、什么是图？

1.图的概念：

图是一种数据结构，是继树后一种相对复杂且非线性的数据结构。下面我们来认识一下图这种结构，或者说它应该长成什么样子。

图一共有两部分组成，一部分叫做顶点，另一部分叫做依托顶点而衍生出来的边。我们将顶点与边的集合叫做图。下面呢，咱们来看一下图的内存结构，在正式学习前，我们先对图这种结构有个简单的了解和认识。关于图结构的数据模型，如下所示：

如上图所示，上面是咱们最常见的图结构，也就是图这种数据结构的数据模型。我们前面说在图这种数据结构中，有两个主角，一是顶点，二是边。我相信通过这张模型图大家肯定会更直白更容易理解。

接下来呢，和之前咱们刚开始讲解树结构一样，咱们讲一下图的基本术语。

2.图的基本术语：

顶点：顶点在图中起着至关重要的作用，它主要是构成图的主要骨架，有了顶点以后，咱们将其按照相应的规则连接起来，也就形成了咱们最终的图。在上述的内存模型中，咱们每个端点则就是一个顶点，例如：像咱们a-n这些端点都是咱们当前图结构中的顶点。

边：有了顶点的概念以后，那么什么是边呢？边就是两个顶点连接起来的一条线，我们其实可以很简单理解，所谓最简单的图，我们可以类比之前数学学过的几何一样。最简单的图也就是一条线段，两个端点叫做顶点，其中两个端点之间连接的直线也就叫做咱们的边。所以说，咱们的边一定是依赖顶点衍生出来的，不存在没有顶点却有边的情况。在上图中：例如a和b之间、b和c、a和d、a和e之间的链接等等，咱们称之为图中的边。

相邻顶点：经过同一条边连接起来的顶点怎们称之为相邻顶点。如下图所示：

在该图中，a和b通过同一条边相连，b和c通过同一条边相连。我们可以说a和b为相邻顶点，也可以说b和c叫做相邻顶点，但是a和c没有经过同一条边连接，我们此时就不能说a和c为相邻顶点。

顶点的度：顶点的度这个概念也很好理解，其实就是指某个顶点衍生出来边的个数，咱们也就成为当前顶点的度。比如对下面这幅图：

这幅图还是咱们最开始那幅图。比如咱们对a顶点来说，此时它产生了三条边。分别为a-b、a-d、a-e，我们此时也就是a这个顶点的度为3。同理对f顶点来说，此时它就衍生出一条边，即f-e，此时我们就可以说f顶点的度为1。

子图：我们说一幅图的子集就叫做这幅图的子图。怎么理解呢，如下图所示：

如上图所示，相同颜色的顶点以及对应的边，我们可以看作原图的子图。例如a、b、c、h以及l、m、n分别为原图的一部分，它们也可以单独看作一幅图，此时就将它们称之为原图的子图，当然这幅图子图有很多，我们就简单举个例子。

路径：从某个顶点到另外一个顶点所经过的顶点顺序咱们称之为路径。例如：

例如：从a顶点出发到d顶点，咱们可以逆时针，那么此时它的路径就比较少，那么那就是a-d。如果通过顺时针，那么此时的路径顺序为a-b-c-h-g-d。

7.环：从一个顶点出发最后经过一大堆路径又回到本身，就像是在玩迷宫游戏一样，最后兜兜转转又回到原地。

比如咱们这些标红的顶点构成的路径，咱们就可以说它是一个环。

8.无向图：知道了前面的知识，我们知道两个顶点对应一条边，对于无向图来说，这条边没有特殊含义，没有方向。如下所示：

在a和b顶点中，它们之间的边是没有任何方向可言的。我们既可以说是a到b的边，也可以说是b到a的边。

9.有向图：同理，有了无向图的知识，那么有向图就很好理解了，有向图的意思是两个顶点之间的边是有顺序的。如下所示：

此时对于a和b顶点来说，我们只能说是a到b的边，却不能逆过来说是b到a的边。

10.连通图：每个顶点都能通过直接或间接的方式访问到的情况我们称之为连通图。还是针对这幅图来说：

我们这时候发现a和i、a和m、a和n顶点并不能访问，这时候整幅图就并不是一幅连通图。再比如下面这幅图：

此时当前图中的每一个顶点都能直接或者间接性访问，此时我们说整幅图也就为一幅连通图。

11.连通子图：在一幅图中，可能整幅图并不具备连通图的条件，但是它的某子图一定满足连通图的条件，此时我们称之为整幅图的连通子图。如下图所示：

如上图所示：对整幅图我们分析过，此时并不具备连通图的条件，所以我们说整幅图并不是连通图。但是针对它的一些子图，比如我们不同颜色表示的三幅子图都为连通图。我们就说这三幅连通图为整幅图的连通子图。

二、图的实现方式

下面呢，我们来研究怎么来表示图这种结构呢。其实大家细心一点机会发现咱们图最复杂的一部分其实就是顶点与顶点之间的关系。那么怎么来进行描述呢？整体来说我们最常见的就是通过领接矩阵来表示图结构中顶点与顶点的关系，也就是咱们的边。下面我们具体来研究一下领接矩阵是怎么表示图中顶点与顶点之间的关系的。

2.1使用二维数组邻接矩阵来表示图

在二维数组中，我们可以使用数组的索引来表示顶点。什么意思呢，比如我们针对如下这幅图：

我们可以用二维数组的外层数组索引以及内层数组索引来表示对应的顶点，当前索引位置上的数值来表示两个顶点之间是不是存在边，我们可以设有边对应的值为1，反之则为0。可能理论有点抽象，咱们将最终在二维数组的内存图画出更好理解一些。如下图所示：

如上图所示：我们使用邻接矩阵来表示顶点之间的关系。用二维数组的外层索引以及内层索引来表示咱们图中的顶点，用对应位置上的数值来表示当前位置有没有边(1-表示有边，0-表示无边)。比如我们设当前二维数组引用为adjacency_ matrix，如图所示：adjacency_matrix[0][1]=1，则表示0和1号顶点之间存在一条边，同时又因为当前咱们的图为无向图，所以这个时候为了表示边的无方向性，这个时候咱们的adjacency_matrix[1][0]=1，则表示1到0之间的边。

下面呢，咱们基于邻接矩阵的思想完成一下咱们无向图的实现。

2.2无向图的代码实现

下面呢，咱们使用邻接矩阵来完成无向图的代码实现：

package com.ignorance.graph;

import java.util.ArrayList;

import java.util.List;

public class Graph<E> {

//当前图中的顶点

private List<E> vertexList;

//表示顶点关系的邻接矩阵

private int[][] adjacency_matrix;

//边的数量

private int edgeCount;

//主要用于记录某个顶点是否被访问过

private boolean[] isMarked;

public Graph(int N) {

//初始化邻接矩阵，邻接矩阵整体元素为当前顶点的2次方

this.adjacency_matrix = new int[N][N];

//初始化顶点集合

this.vertexList = new ArrayList<>(N);

}

public void saveVertex(E vertex){

//向顶点集合插入顶点

this.vertexList.add(vertex);

}

public void saveEdge(E vertex1,E vertex2){

if (findIndexByVertex(vertex1) == -1 || findIndexByVertex(vertex2) == -1){

throw new RuntimeException("当前顶点不存在...");

}

this.adjacency_matrix[findIndexByVertex(vertex1)][findIndexByVertex(vertex2)] = 1;

this.adjacency_matrix[findIndexByVertex(vertex2)][findIndexByVertex(vertex1)] = 1;

edgeCount++;

}

private int findIndexByVertex(E targetVertex){

for (int i = 0;i < vertexList.size();i++){

if (targetVertex.equals(vertexList.get(i))){

return i;

}

}

return -1;

}

}

上述代码在咱们讲了邻接矩阵的表示原理以后，应该特别容易理解，代码也没什么难度，咱们就不多解释了。接下来了咱们讲解一下在无向图中一个很重要的知识，那就是遍历。

图的遍历并不像数组和链表那么简单，反而跟树差不多，因为它们本身都是非线性表。不知道大家还有没有印象，在咱们树中，遍历方式分为前序遍历、中序遍历以及后序遍历。在咱们图中遍历方式主要有两种，只要一说，大家有计算机专业的同学肯定就会有一些印象。一种为深度优先算法DFS，另外一种则是广度优先算法BFS。下面呢，咱们具体看一下这两种方式，是怎么进行遍历的，或者两者之间有什么不同。

深度优先DFS算法与广度优先算法BFS:

深度优先算法的实质是先将一个顶点遍历到底，直到对应的顶点再也没有相邻顶点即可。举个例子：比如你现在手里有五件事情要做，每一件事又分成若干个步骤，深度优先算法的实质就是咱们一件事一件事的做完，一件事做完以后咱们再接着做另外一件事。如下图所示：

比如此时从a结点出发，第二层有b和g两个分支，这时候咱们第一次只走第一个分支，然后到第三层，又分为两个分支，这个时候咱们又继续走第一个分支，直到后面再也没有顶点为止，我们接着才从第二个分支继续遍历，就是一个递归的过程。所以呢，对这幅图，咱们采用深度优先算法遍历出来的顺序为：a-b-c-e-f-d-g-h-i。

广度优先算法BFS则是按照每一层进行遍历，相当于是从横向到纵向的过程。比如还是有5个任务，这个时候咱们是所有任务一起同时做。那么使用咱们的广度优先算法此时遍历出来的顺序为：a-b-g-c-d-h-i-e-f。

下面呢，我们继续完成咱们无向图的搜索过程，最终完成的代码如下：

package com.ignorance.graph;

import java.util.*;

import java.util.concurrent.LinkedBlockingDeque;

import java.util.concurrent.LinkedBlockingQueue;

public class Graph<E> {

//当前图中的顶点

private List<E> vertexList;

//表示顶点关系的邻接矩阵

private int[][] adjacency_matrix;

//边的数量

private int edgeCount;

//主要用于记录某个顶点是否被访问过

private boolean[] isMarked;

public Graph(int N) {

//初始化邻接矩阵，邻接矩阵整体元素为当前顶点的2次方

this.adjacency_matrix = new int[N][N];

//初始化顶点集合

this.vertexList = new ArrayList<>(N);

}

public void saveVertex(E vertex){

//向顶点集合插入顶点

this.vertexList.add(vertex);

}

public void saveEdge(E vertex1,E vertex2){

if (findIndexByVertex(vertex1) == -1 || findIndexByVertex(vertex2) == -1){

throw new RuntimeException("当前顶点不存在...");

}

this.adjacency_matrix[findIndexByVertex(vertex1)][findIndexByVertex(vertex2)] = 1;

this.adjacency_matrix[findIndexByVertex(vertex2)][findIndexByVertex(vertex1)] = 1;

edgeCount++;

}

//深度优先算法

public void dfs(){

//初始化标记是否访问数组

this.isMarked = new boolean[vertexList.size()];

//对所有顶点进行遍历

vertexList.forEach(vertex -> {

if (!isMarked[findIndexByVertex(vertex)]){

dfs(vertex);

}

});

}

private void dfs(E vertex){

//打印出当前顶点

System.out.print(vertex + " ");

//打印后表示当前顶点已访问，将其标记为true

isMarked[findIndexByVertex(vertex)] = true;

//访问当前顶点第一个相邻顶点

int nextVisit = getFirstNeighbor(findIndexByVertex(vertex));

//如果当前结点存在相邻结点，一直遍历

while (nextVisit != -1){

//如果当前顶点没被访问

if (!isMarked[nextVisit]){

//递归进行遍历

dfs(vertexList.get(nextVisit));

}

//如果当前顶点已经访问，则访问下一个邻结点

nextVisit = getNextNeighbor(findIndexByVertex(vertex),nextVisit);

}

}

//广度优先算法

private void bfs(int currentIndex) {

int u ;

int w ;

//创建一个临时队列

Queue<Integer> queue = new LinkedBlockingQueue<>();

//输出当前顶点

System.out.print(vertexList.get(currentIndex) + " ");

//标记当前顶点为已访问

isMarked[currentIndex] = true;

//将当前顶点加入队列，为了遍历它的相邻结点

queue.add(currentIndex);

while(!queue.isEmpty()) {

//移除当前顶点，为了避免重复访问

u = (Integer)queue.remove();

//得到它的第一个相邻顶点

w = getFirstNeighbor(u);

//如果存在相邻顶点

while(w != -1) {

//如果没有访问，继续遍历，将其进行标记

if(!isMarked[w]) {

System.out.print(vertexList.get(w) + " ");

isMarked[w] = true;

queue.add(w);

}

w = getNextNeighbor(u, w);

}

}

}

//广度优先算法

public void bfs() {

isMarked = new boolean[vertexList.size()];

vertexList.forEach(v -> {

if (!isMarked[findIndexByVertex(v)]){

bfs(findIndexByVertex(v));

}

});

}

private int findIndexByVertex(E targetVertex){

for (int i = 0;i < vertexList.size();i++){

if (targetVertex.equals(vertexList.get(i))){

return i;

}

}

return -1;

}

private int getFirstNeighbor(int index){

int targetIndex = -1;

for (int i = 0;i < vertexList.size();i++){

if (adjacency_matrix[index][i] > 0){

targetIndex = i;

break;

}

}

return targetIndex;

}

private int getNextNeighbor(int v1,int v2){

int targetIndex = -1;

for (int i = v2 + 1;i < vertexList.size();i++){

if (adjacency_matrix[v1][i] > 0){

targetIndex = i;

break;

}

}

return targetIndex;

}

}

总结

在本篇文章中，我们继链表、树后讲解了一种全新的数据结构，也就是咱们的图结构。针对图的一些常用术语，展开了详细的描述，并讲解了图的常用遍历方式，即深度优先DFS以及广度优先算法BFS。最后呢，咱们通过代码并完成了一个通过邻接矩阵实现的无向图。