基本介绍
为什么要有图
线性表局限于一个直接前驱和一个直接后继，树也只能有一个直接前驱也就是父节点，当我们要表示多对多的关系时就需要用到图。
图的常用概念
- 顶点(vertex)
- 边(edge)
- 路径A->B->C
- 无向图 顶点之间的连接没有方向，A->B也可以B->A
- 有向图 顶点之间的连接有方向，比如A->B不能是B->A
- 带权图 边带权值，带权图也叫网
图的表示方式
两种表示方式：二维数组表示(邻接矩阵)，链表表示(邻接表)。
- 邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，矩阵是的 row 和 col 表示的是 1….n 个点。
- 邻接表
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.，邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
代码实现
构建下图所示这个图，要求能够添加边，最后打印出邻接矩阵
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
package com.eh.ftd.dsa.ds;
import java.util.*;
import java.util.Queue;
/**
* 图
*
* @author David Li
* @create 2020/06/30 19:54
*/
public class Graph {
/**
* 图的邻接矩阵表现形式
*/
private int[][] matrix;
/**
* 顶点的表现形式
*/
private List<String> vertexNames;
/**
* 顶点是否被访问过，用于遍历
*/
private boolean[] visited;
/**
* 构造器
*
* @param vertexNames 顶点名称数组
*/
public Graph(String[] vertexNames) {
this.matrix = new int[vertexNames.length][vertexNames.length];
this.vertexNames = Arrays.asList(vertexNames);
visited = new boolean[vertexNames.length];
}
private int getIndexByVertexName(String vertexName) {
for (int i = 0; i < vertexNames.size(); i++) {
if (vertexName.equals(vertexNames.get(i))) {
return i;
}
}
throw new RuntimeException();
}
public void buildEdge(String v1, String v2) {
int idx1 = getIndexByVertexName(v1);
int idx2 = getIndexByVertexName(v2);
matrix[idx1][idx2] = 1;
matrix[idx2][idx1] = 1;
}
public void printMatrix() {
for (int[] arr : matrix) {
System.out.println(Arrays.toString(arr));
}
}
/**
* 深度优先遍历
*
* @param idx
*/
public void dfs(int idx) {
// 输出自己
System.out.println(vertexNames.get(idx));
// 标记已访问
visited[idx] = true;
// 访问第一个邻居节点
for (int i = 0; i < vertexNames.size(); i++) {
if (!visited[i] && matrix[idx][i] == 1)
dfs(i);
}
}
/**
* 广度优先遍历
*
* @param
*/
public void bfs() {
Queue<Integer> queue = new LinkedList<>();
// 入队自己
queue.add(0);
while (!queue.isEmpty()) {
int idx = queue.poll();
// 输出
System.out.println(vertexNames.get(idx));
// 标记已访问
visited[idx] = true;
// 将邻居入队
for (int i = 0; i < vertexNames.size(); i++) {
if (!visited[i] && matrix[idx][i] == 1) {
// 入队
queue.add(i);
}
}
}
}
public static void main(String[] args) {
String[] vertexNames = {"A", "B", "C", "D", "E", "F", "G"};
Graph graph = new Graph(vertexNames);
graph.buildEdge("A", "B");
graph.buildEdge("B", "C");
graph.buildEdge("B", "D");
graph.buildEdge("D", "C");
graph.buildEdge("A", "E");
graph.buildEdge("C", "F");
graph.buildEdge("E", "G");
// graph.printMatrix();
// graph.dfs(0);
graph.bfs();
}
}
|
图的遍历
算法在dfs和bfs的文章里有详细介绍，在此不过多赘述，直接上代码。
dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/**
* 深度优先遍历
*
* @param idx
*/
public void dfs(int idx) {
// 输出自己
System.out.println(vertexNames.get(idx));
// 标记已访问
visited[idx] = true;
// 访问第一个邻居节点
for (int i = 0; i < vertexNames.size(); i++) {
if (!visited[i] && matrix[idx][i] == 1)
dfs(i);
}
}
|
bfs
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
|
/**
* 广度优先遍历
*
* @param
*/
public void bfs() {
Queue<Integer> queue = new LinkedList<>();
// 入队自己
queue.add(0);
while (!queue.isEmpty()) {
int idx = queue.poll();
// 输出
System.out.println(vertexNames.get(idx));
// 标记已访问
visited[idx] = true;
// 将邻居入队
for (int i = 0; i < vertexNames.size(); i++) {
if (!visited[i] && matrix[idx][i] == 1) {
// 入队
queue.add(i);
}
}
}
}
|
