简单图的存储和表示

简单图的存储和表示

什么是简单图

在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边,平行边的条数称为重数。在有向图中,关联一对顶点的有向边如果多于1条,并且这些边的始点与终点相同(也就是它们的的方向相同),称这些边为平行边。含平行边的图称为多重图,既不含平行边也不含环的图称为简单图。

稠密图和稀疏图的定义

有很少条边或弧(边的条数|E|远小于|V|²)的图称为稀疏图(sparse graph),
反之边的条数|E|接近|V|²,称为稠密图(dense graph)。

图可以用哪些数据结构进行存储表示

  • 数组(邻接矩阵)存储表示(有向或无向)
  • 邻接表存储表示
  • 前向星存储表示
  • 有向图的十字链表存储表示
  • 无向图的邻接多重表存储表示

稠密图适合用邻接矩阵,稀疏图适合用邻接表表示

示例代码

用邻接矩阵表示稠密图

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
package GraphBasics;

import java.util.Vector;

/**
* @ Description: 用邻接矩阵表示稠密图
* @ Date: Created in 11:35 2018/8/1
* @ Author: Anthony_Duan
*/
public class DenseGraph implements Graph {
//节点数
private int n;

//边数
private int m;
//是否为有向图
private boolean directed;

//图的具体数据
private boolean[][] g;



public DenseGraph(int n, boolean directed) {
assert n >= 0;
this.n = n;
//初始化没有任何边
this.m = 0;
this.directed = directed;

//g初始化为n*n的布尔矩阵,每一个g[i][j]均为false,表示没有任何边
//false为Boolean型的变量的默认值
g = new boolean[n][n];
}

//返回节点个数
@Override
public int V(){
return n;
}

//返回边的个数
@Override
public int E(){
return m;
}


//向图中添加一个边
@Override
public void addEdge(int v, int w) {
assert v >= 0 && v < n;
assert w >= 0 && w < n;

//首先判断边是否存在,如果存在什么都不做
if (hasEdge(v, w)) {
return;
}

g[v][w] = true;
//如果不是有向图
if (!directed) {
g[w][v] = true;
}
m++;
}

// 验证图中是否有从v到w的边
@Override
public boolean hasEdge(int v, int w) {
assert v >= 0 && v < n;
assert w >= 0 && w < n;
return g[v][w];
}
@Override
public void show() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(g[i][j] + "\t");
}
System.out.println();
}
}
/**
* 返回图中一个顶点的所有邻边
* 由于java使用引用机制,返回一个Vector不会带来额外开销
* @param v
* @return
*/
@Override
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<Integer>();

for (int i = 0; i < n; i++) {
if (g[v][i]) {
adjV.add(i);
}
}

return adjV;
}
}

用邻接表表示稀疏图

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
package GraphBasics;

import java.util.Vector;

/**
* @ Description: 用邻接表表示稀疏图
* @ Date: Created in 11:35 2018/8/1
* @ Author: Anthony_Duan
*/
public class SparseGraph implements Graph {
//节点数
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 = m;
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>();
}
}

//返回节点个数
@Override
public int V(){
return n;
}
//返回边的个数
@Override
public int E(){
return m;
}


/**
* 向图中添加一个边
* 这里并没有处理平行边的情况
* 因为邻接表如果要考虑没有平行边,每次添加边都需要遍历一次g[v]
* 效率太低,所以一般是先添加,最后一次性处理,
* 这里就暂时允许有平行边
* @param v
* @param w
*/
@Override
public void addEdge(int v, int w) {
assert v >= 0 && v < n;
assert w >= 0 && w < n;

g[v].add(w);
if (v != w && !directed) {
g[w].add(v);
}
m++;
}



@Override
public void show() {
for( int i = 0 ; i < n ; i ++ ){
System.out.print("vertex " + i + ":\t");
for( int j = 0 ; j < g[i].size() ; j ++ ) {
System.out.print(g[i].elementAt(j) + "\t");
}
System.out.println();
}
}

@Override
public 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;
}


/**
* 返回图中一个顶点的所有邻边
* 由于java使用引用机制所以返回一个Vector不会带来额外开销
* @param v
* @return
*/
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}

-------------End Of This ArticleThank You For Reading-------------