记录生活中的点点滴滴

0%

图(Graph)是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。

图的常用概念

  1. 顶点(vertex)
  2. 边(edge)
  3. 路径
  4. 无向图
  5. 有向图
  6. 带权图

图的表示方式

图的表示方式有两种:二维数组表示(邻接矩阵);链表表示(邻接表)。

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于 n 个顶点的图而言,矩阵是的 row 和 col 表示的是 1….n 个点。

下面我们通过邻接矩阵来完成图这一数据结构的编写。

首先,它有哪些属性?

  1. 存储顶点集合,可以用ArrayList表示
  2. 邻接矩阵,用二维数组表示
  3. 边的数目,int表示

OK,上代码:

1
2
3
4
5
class Graph{
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges;//邻接矩阵
private int numofEdges;//边的数目
}

初始化图,通过传入一个节点数目n,我们要初始化这三个属性。

1
2
3
4
5
6
//初始化图
public Graph(int n){
vertexList = new ArrayList<String>(n);
edges = new int[n][n];
numofEdges = 0;
}

添加节点,传入字符串,把它添加到list中

1
2
3
4
//添加顶点
public void addVertex(String s){
vertexList.add(s);
}

建立边,我们还可以传入这条边对应的权值

1
2
3
4
5
6
7
8
9
//建立边,不传weight默认为1
public void createEdge(int i1,int i2){
createEdge(i1,i2,1);
}
public void createEdge(int i1,int i2,int weight){
edges[i1][i2] = weight;
edges[i2][i1] = weight;
numofEdges++;
}

遍历图,通过输出邻接矩阵来遍历图

1
2
3
4
5
6
7
8
9
10
//遍历图,输出邻接矩阵
public void listGraph(){
int len = vertexList.size();
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
System.out.print(edges[i][j]+" ");
}
System.out.println();
}
}

还有一些其他方法,就直接把代码粘出来了,不多bb了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//一些其他常用的方法
//返回节点个数
public int vertexCount(){
return vertexList.size();
}
//返回边的个数
public int edgesCount(){
return numofEdges;
}
//返回节点对应下标,例如0->A,1->B
public String getValueByIndex(int i){
return vertexList.get(i);
}
//返回i1 i2的权值
public int getWeight(int i1,int i2){
return edges[i1][i2];
}

OK,这就是一个很简单的图的基本数据结构,下面我们测试一下看看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
Graph graph = new Graph(5);
String[] ss = {"A","B","C","D","E"};
for (String s : ss) {
graph.addVertex(s);
}
graph.createEdge(0,1);
graph.createEdge(0,2);
graph.createEdge(1,2);
graph.createEdge(1,3);
graph.createEdge(1,4);
graph.listGraph();
System.out.println("图节点的个数: "+graph.vertexCount());
System.out.println("图边的个数: "+graph.edgesCount());
}

输出结果:

邻接表

  1. 邻接矩阵需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在,会造成空间的一定损失.
  2. 邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成

图的遍历

所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种 访问策略: (1) 深度优先遍历 (2) 广度优先遍历

深度优先遍历DFS

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次

举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:

A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束)

下面写代码实现,我们首先要在原来的图Graph类中增加一个boolean数组,判断遍历过程中节点是否被访问过。

1
2
//遍历时判断是否访问过
private boolean[] isVisited;

下面是DFS的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//DFS遍历
public void dfs(){
int count = vertexCount();//顶点数目
isVisited = new boolean[count];
for (int i = 0; i < count; i++) {
if(!isVisited[i])
dfs(i);
}
}
//对dfs进行重载用来dfs下标为i的节点
private void dfs(int i) {
//设置下标i的已访问并输出
isVisited[i] = true;
System.out.print(vertexList.get(i) + "-->");
int count = vertexCount();//顶点数目
for (int j = 0; j < count; j++) {
if(edges[i][j]>0 && !isVisited[j]){
dfs(j);
}
}
}

我们还在原来的main方法中进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
Graph graph = new Graph(8);
String[] ss = {"A","B","C","D","E","F","G","H"};
for (String s : ss) {
graph.addVertex(s);
}
graph.createEdge(0,1);//A B
graph.createEdge(0,2);//A C
graph.createEdge(0,3);//A D
graph.createEdge(1,4);//B E
graph.createEdge(2,5);//C F
graph.createEdge(5,7);//F H
graph.createEdge(7,6);//H G
graph.createEdge(6,3);//G D
graph.listGraph();

System.out.println("DFS遍历:");
graph.dfs();
}

输出结果:

广度优先遍历BFS

图的广度优先搜索(Broad First Search) :

类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点。

我们还以上面DFS那个图来举例,但是这次把它倒过来来看:

如果我们从A点发起广度优先搜索,则我们可能得到如下的一个访问过程:

A(从A开始,找相邻的,可以找到BCD)->B->C->D(B接着)->E(C接着)->F(D接着)->G(F接着)->H

(都为true,最终结束)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//BFS遍历
public void bfs(){
int count = vertexCount();//顶点数目
isVisited = new boolean[count];//初始化是否访问过的数组
//从0开始进行各自的BFS
for (int i = 0; i < count; i++) {
if(!isVisited[i])
bfs(i);
}
}
//重载
public void bfs(int i){
//借助队列实现
LinkedList<Integer> queue = new LinkedList<>();
//将i入队并标记
queue.offer(i);
isVisited[i] = true;
while (!queue.isEmpty()){
//将队首元素出队并输出
int poll = queue.poll();
System.out.print(getValueByIndex(poll) + "-->");
//遍历,如果ij之间有边并且j未被访问,则将j入队并标记
for (int j = 0,len = vertexCount(); j < len; j++) {
if(edges[i][j]>0 && !isVisited[j]){//入队
queue.offer(j);
isVisited[j] = true;
}
}
}
}

下面进行测试,在上面我们测试BFS时的main方法后面再添加下面代码:

1
2
3
4
5
6
System.out.println();

System.out.println("BFS遍历:");
graph.bfs();

System.out.println();

输出结果如下: