L
L
LearnJava
Search…

1. 简介

图结构也是一种非线性数据结构。生活中有很多图结构的例子,比如通信网络、交通网络、人际关系网络等都可以归结为图结构。图结构的每个节点可以互相关联,比树结构更加复杂
下图就是一个简单的图结构:

2. 相关概念

  • 1.有向图
  • 2. 无向图
  • 3. 顶点的度:连接顶点的边的数量称为该顶点的度。在有向图中又分为入度和出度。
  • 4. 邻接顶点:指一条边的两个顶点。在有向图中分为入边邻接顶点和出边邻接顶点。
  • 5. 无向完全图:每两个顶点之间就有一条边。
  • 6. 有向完全图:每两个顶点之间存在方向相反的两条边。对于一个N个节点的有向完全图,边数为N(N-1),是无向完全图的两倍。
  • 7. 子图:类似子集合,子图的顶点和边都是原图的。
  • 8. 路径:两个顶点之间的连线,可以有多条,每条长度可能不一样。路径又可以分为三种形式:
    • 简单路径:一条路径上的顶点不重复出现;
    • 环:路径的第一个顶点和最后一个顶点相同叫做环,有时也成回路;
    • 简单回路:路径的第一个顶点和最后一个顶点相同,其余顶点不重复的叫做简单回路。
  • 9. 连通、连通图和连通分量:
    • 如果两个顶点之间有路径,那么这两个顶点是连通的;
    • 无向图中任意两个顶点都是连通的,称为连通图;
    • 无向图中极大连通子图称为连通分量。
    连通图的连通分量有且仅有一个,就是它本身。
  • 10. 强连通图和强连通分量:
    • 如果两个顶点之间有路径,那么这两个顶点是连通的,注意,因为有向,有时可能是Vi -> Vj是连通的,Vj -> Vi不是连通的;
    • 如果有向图中任意两个顶点都是连通的,那么就是强连通图;
    • 有向图的最大强连通子图称为该图的强连通分量。
    强连通图的强连通分量有且仅有一个,就是它本身。
  • 11. 权:在边上表示的数值,这个数值就是该边的权。无向图中加入权值称为无向带权图,有向图中加入权值称为有向带权图。权在生活中可以表示交通图中道路的长度,人际关系中代表亲密度等。
  • 12. 网(network):即边上带有权值的图的另一个名称,网与实际应用更为贴切。

3. 图的存储

在实际应用中,通常使用数组来单独保存顶点信息,然后采用二维数组保存顶点之间的关系。这种保存顶点之间关系的数组称为邻接矩阵。
1
char[] Vertex = new char[MaxNum]; //保存顶点信息
2
int[][] EdgeWeight = new int[MaxNum][MaxNum]; //保存边
Copied!
这张无向图的边就可以这样表示
1
Vertex[0] = 1;
2
Vertex[1] = 2;
3
Vertex[2] = 3;
4
Vertex[3] = 4;
5
Vertex[5] = 5;
Copied!
边通过EdgeWeight二维数组表示,有边的话存1,没有的话存0。比如1和2之间的表可以表示为:
1
//数组下角标从0开始的
2
EdgeWeight[0][1] = 1;
3
EdgeWeight[1][0] = 1;
Copied!
这个图的邻接矩阵:
0
1
1
0
1
1
0
0
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
1
0
因为是无向图,所以左下和右上是对称的,有向图就不是了。

4. 代码实例

接下来用一个代码实例来看下树的结构初始化,清空以及输出遍历操作:
1
package com.wangjun.datastructure;
2
3
public class GraphTest {
4
private final int MaxNum = 5; // 最大顶点数
5
6
public static void main(String[] args) {
7
GraphTest gt = new GraphTest();
8
GraphMatrix gm = gt.new GraphMatrix();
9
gt.createGraph(gm);
10
gt.outGraph(gm);
11
gt.deepTraGraph(gm);
12
}
13
14
15
// 定义邻接矩阵结构
16
class GraphMatrix {
17
char[] Vertex = new char[MaxNum]; // 保存顶点信息,数字或者字母
18
int GType; // 类型,0:无向图,1:有向图
19
int vertexNum; // 顶点的数量
20
int EdgeNum; // 边的数量
21
int[][] EdgeWeight = new int[MaxNum][MaxNum]; // 保存边的权
22
int[] isTrav = new int[MaxNum]; // 遍历标志
23
}
24
25
// 创建邻接矩阵图
26
// 这里创建手动创建一个5节点的图,对应上面的图
27
public void createGraph(GraphMatrix gm) {
28
gm.Vertex[0] = '1';
29
gm.Vertex[1] = '2';
30
gm.Vertex[2] = '3';
31
gm.Vertex[3] = '4';
32
gm.Vertex[4] = '5';
33
34
gm.GType = 0;
35
gm.vertexNum = 5;
36
gm.EdgeNum = 6;
37
gm.EdgeWeight[0][1] = 1;
38
gm.EdgeWeight[1][0] = 1;
39
gm.EdgeWeight[0][2] = 1;
40
gm.EdgeWeight[2][0] = 1;
41
gm.EdgeWeight[0][4] = 1;
42
gm.EdgeWeight[4][0] = 1;
43
gm.EdgeWeight[2][4] = 1;
44
gm.EdgeWeight[4][2] = 1;
45
gm.EdgeWeight[1][3] = 1;
46
gm.EdgeWeight[3][1] = 1;
47
gm.EdgeWeight[3][4] = 1;
48
gm.EdgeWeight[4][3] = 1;
49
}
50
51
// 清空图
52
public void clearGraph(GraphMatrix gm) {
53
for (int i = 0; i < MaxNum; i++) {
54
for (int j = 0; i < MaxNum; j++) {
55
gm.EdgeWeight[i][j] = 0;
56
}
57
}
58
}
59
60
// 显示图,即显示邻接矩阵
61
public void outGraph(GraphMatrix gm) {
62
// 输出顶点信息
63
System.out.println("顶点:");
64
for (int i = 0; i < MaxNum; i++) {
65
System.out.print(gm.Vertex[i] + " ");
66
}
67
System.out.println();
68
// 输出边的信息
69
System.out.println("边:");
70
for (int i = 0; i < MaxNum; i++) {
71
for (int j = 0; j < MaxNum; j++) {
72
System.out.print(gm.EdgeWeight[i][j] + " ");
73
}
74
System.out.println();
75
}
76
}
77
78
/*
79
* 遍历图,即逐个访问图的顶点,使用isTrav数组标志该节点是否被遍历过
80
* 常用的遍历图方法:广度优先遍历法和深度优先遍历法 此函数以深度优先遍历法为例
81
* 深度遍历法类似于树的先序遍历,具体执行过程如下:
82
* 1)从isTrav数组中选择一个未被访问的顶点Vi,将其标记为1,表示已访问过
83
* 2)从Vi的一个未被访问过的邻接点出发进行深度优先遍历
84
* 3)重复步骤2),直至图中所有和Vi有路径相通的顶点都被访问过
85
* 4)重复步骤1)至3)的操作,直至图中所有的顶点都被访问过
86
* 深度优先遍历法是一个递归过程
87
*/
88
public void deepTraGraph(GraphMatrix gm) {
89
// 清除顶点访问标志
90
for (int i = 0; i < gm.vertexNum; i++) {
91
gm.isTrav[i] = 0;
92
}
93
System.out.println("深度优先遍历节点:");
94
for (int i = 0; i < gm.vertexNum; i++) {
95
// 若该节点未遍历
96
if (gm.isTrav[i] == 0) {
97
deepTraOne(gm, i);// 调用函数遍历
98
}
99
}
100
}
101
102
//深度遍历的执行函数
103
public void deepTraOne(GraphMatrix gm, int n) {
104
// 从第n个节点开始,深度遍历图
105
gm.isTrav[n] = 1;
106
// 输出节点数据
107
System.out.println("node:" + gm.Vertex[n] + " ");
108
109
// 添加处理节点的操作
110
for (int i = 0; i < gm.vertexNum; i++) {
111
if (gm.EdgeWeight[n][i] != 0 && gm.isTrav[i] == 0) {
112
deepTraOne(gm, i);// 递归进行遍历
113
}
114
}
115
}
116
117
}
Copied!
Last modified 1yr ago