图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图,V是图G中顶点的集合，E是图G中边的集合。
图的特性
- 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中的数据元素我们称之为顶点
(Vertex)。 - 线性表中可以没有数据元素，成为空表。树中可以没有结点，叫做空树。
- 线性表中，相邻的数据元素之间具有线性关系。树结构中，相邻两层的结点具有层次关系。而在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
无向图
有向图
图的权
连通图
图的度
图的存储结构 ：主要有两种方式，一种是邻接矩阵,一种是邻接表。
邻接矩阵:
- 邻接矩阵表示无向图
邻接矩阵表示有向图
邻接矩阵表示有权值的图
邻接表:
邻接表表示无向图
邻接表表示有向图
邻接表表示有权值的图
JAVA利用邻接矩阵实现简单的图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
87public class Graph {
private int vertexSize;//顶点数量 5个顶点
private int[] vertexs;//顶点 v0 v1 v2 v3 v4
private int[][] matrix;//邻接矩阵
private static final int MAX_WEIGHT = 1000; //表示无穷
public Graph(int vertexSize) {
this.vertexSize = vertexSize;
matrix = new int[vertexSize][vertexSize];
vertexs = new int[vertexSize];
for (int i = 0; i < vertexSize; i++) {
vertexs[i] = i;
}
}
/**
* 获取index顶点的的出度
*
* @param index 顶点index
*/
public int getOutDegree(int index) {
int degree = 0;
for (int i = 0; i < matrix[index].length; i++) {
int weight = matrix[index][i];
if (weight != 0 && weight != MAX_WEIGHT) {
degree++;
}
}
return degree;
}
/**
* 获取index顶点的的入度
*
* @param index 顶点index
*/
public int getInDegree(int index) {
int degree = 0;
for (int i = 0; i < matrix[index].length; i++) {
int weight = matrix[i][index];
if (weight != 0 && weight != MAX_WEIGHT) {
degree++;
}
}
return degree;
}
/**
* 获取v1到v2的权值
*
* @return v1到v2的权值权值
*/
public int getWeight(int v1, int v2) {
int weight = matrix[v1][v2];
return weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight);
}
public static void main(String[] args) {
Graph graph = new Graph(5);//v0 -> v4
int[] v0 = new int[]{0, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 6};
int[] v1 = new int[]{9, 0, 3, MAX_WEIGHT, MAX_WEIGHT};
int[] v2 = new int[]{2, MAX_WEIGHT, 0, 5, MAX_WEIGHT};
int[] v3 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0, 1};
int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};
graph.matrix[0] = v0;
graph.matrix[1] = v1;
graph.matrix[2] = v2;
graph.matrix[3] = v3;
graph.matrix[4] = v4;
int v1OutDegree = graph.getOutDegree(1);
System.out.println("v1的出度 = " + v1OutDegree);//v1的出度 = 2
int v0InDegree = graph.getInDegree(1);
System.out.println("v0的入度 = " + v0InDegree);//v0的入度 = 2
int v02v4Weight = graph.getWeight(0, 4);
System.out.println("v0到v4的权值 = " + v02v4Weight);//v0到v4的权值 = 6
}
}