一、前言
记录下图的笔记
二、图
1.什么是图？
图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成，通常 表示为： G(V,E)。其中，G 表示一个图，V 是图 G 中顶点的集合，E 是 图 G 中边的集合
2.图的分类
大致可以分为以下两类：
有向图和无向图
有权图和无权图
具体关于图的定义，可查看这里。
3. 图的算法实现
无向图的实现主要有两种方式实现：
邻接矩阵 （密集图）
邻接表 （稀疏图）
邻接矩阵实现：
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
/**
* 稠密图 - 邻接矩阵
*/
public class DenseGraph {
/**
* 顶点
*/
private int n;
/**
* 边数
*/
private int m;
/**
* 图的具体数据
*/
private boolean[][] g;
/**
* 是否为有向图
*/
private boolean isDirected;
/**
* 初始化
* @param n
* @param isDirected
*/
public DenseGraph(int n, boolean isDirected) {
this.n = n;
this.m = 0;
this.isDirected = isDirected;
this.g = new boolean[n][n];
}
/**
* 返回顶点数
* @return
*/
public int V() {return this.n;}
/**
* 返回边数
* @return
*/
public int E() {return this.m;}
/**
* 向图中添加一个边
* @param v
* @param w
*/
public void addEdge(int v, int w) {
// 如果存在这条边了，直接return
if (hasEdge(v, w)) {
return;
}
// 把第v 行 第 w 列 设置为 true，也就是代表这两个顶点已经存在边的连接
g[v][w] = true;
if (!isDirected) {
// 也要相应的把第w 行 第 v 列 设置为 true，也就是代表这两个顶点已经存在边的连接
g[w][v] = true;
}
m ++;
}
/**
* 判断是否已经存在这条边了
* @param v
* @param w
* @return
*/
public boolean hasEdge(int v, int w) {
return g[v][w];
}
}
邻接表：
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
import java.util.Vector;
// 稀疏图 - 邻接表
public class SparseGraph {
private int n; // 节点数
private int m; // 边数
private boolean directed; // 是否为有向图
private Vector<Integer>[] g; // 图的具体数据
// 构造函数
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // 初始化没有任何边
this.directed = directed;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if (hasEdge(v, w))
return;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}
4. 尾语
数据结构和算法永远是程序的灵魂、核心。所以，应该要掌握这些核心，才能让自己不被淘汰！加油！
