图的邻接矩阵存储法学习笔记

Learning Journal
Algorithm, Graph

图的邻接矩阵存储法

性质

先来回顾下邻接矩阵存储法，邻接矩阵使用一个二维数组来表示节点和节点之间的关系。我们假设A是这个二维数组，那么A中的一个元素A[ig]不仅体现出了节点Vi和结点Vg的关系，而且A[ig]的值可以表示这条边权值的大小。

下面两个例子展示了有向图和无向图使用邻接矩阵存储的结构：

无向图邻接矩阵

有向图邻接矩阵

从上图我们可以看到，无向图的邻接矩阵是对称矩阵，也一定是对称矩阵，以上两张图都是不带权的图，因此矩阵中所有边的权值均为1。邻接矩阵的代码实现仅仅使用了二维矩阵，这里不展开写。

图的邻接表存储法

性质

图的邻接表存储法使用一维数组存储结点信息（当然也可以使用链表，但使用数组对可以更方便的查找结点信息），图中每个顶点Vi的所有邻接点组成一个线性表存储在对应的结点下，由于邻接点的数目不确定，所以使用单链表进行存储。这个表在无向图中称为顶点Vi的边表，有向图则称为顶点Vi作为弧尾的出边表。

对于上文中的无向图，用邻接表进行存储的内部结构如下：

无向图邻接表

每一个节点后面所接的结点都是它的邻接点。

实现

邻接表的实现相较邻接矩阵来说没那么简单粗暴，完整的功能分为3个类进行实现：

  • 图类
  • 顶点类
  • 操作类

首先来看图类和顶点类，这两个类实现了构造图和顶点所需要的函数，图由一个顶点数组存储，每个顶点包含一个ArrayList存储该顶点的边（在有向图中为出度表），具体实现见代码，这里不再赘述。

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
import java.util.ArrayList;
public class Graph {
	public Vertex listVertex[];
	public boolean direct;// true为有向图，false为无向图
	public static int v_index = 0;// 计算当前点在数组内的下标
	/* Graph构造 */
	public Graph(int num, boolean flag) {
		direct = flag;
		listVertex = new Vertex[num];
	}
	/* 添加节点 */
	public void addVertex(Vertex v) {
		listVertex[v_index++] = v;
	}
	/* 添加边 */
	public void addEdge(int from, int to) {
		listVertex[from].add_adjacent(listVertex[to]);
		if (!direct) {
			listVertex[to].add_adjacent(listVertex[from]);
		}
	}
}
/* 顶点类 */
class Vertex {
	public boolean isVisited;// 节点是否被访问
	public ArrayList<Vertex> adjacent = null;// 邻接点列表
	public int name;
	public Vertex() {	
		isVisited = false;
	}
	public Vertex(int l) {
		name = l;
		isVisited = false;
	}
	public void add_adjacent(Vertex data) {// 添加邻接点
		if (adjacent == null)
			adjacent = new ArrayList<Vertex>();
		adjacent.add(data);
	}
	public ArrayList<Vertex> getAdj() {
		return adjacent;
	}
	@Override
	public String toString() {
		return "Vertex [name=" + name + "]";
	}
}

操作类实现了图的两种遍历方法在上篇笔记中讨论过，这里深度优先使用栈作为遍历的结构，本质上与迭代是一样的。广度优先使用了ArrayDeque作为数据结构来实现队列，这种结构是一种双向队列，因此也可用于实现栈等其他数据结构。具体实现逻辑见代码。

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
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Traversal_test {
	public Vertex dfs[];
	public Vertex bfs[];
	/* 深度优先遍历 */
	public void dfs(Graph graph) {
		dfs = new Vertex[graph.listVertex.length];
		Stack<Vertex> dfs_stack = new Stack<Vertex>();
		dfs_stack.push(graph.listVertex[0]);
		graph.listVertex[0].isVisited = true;// 第一个节点访问
		int index = 0;
		dfs[0] = graph.listVertex[0];
		while (!dfs_stack.isEmpty()) {// 栈非空则持续遍历
          	//getAdjVertex方法只返回没遍历过的顶点，没有则返回null
			Vertex v = getAdjVertex(dfs_stack.peek());
			if (v == null) {
				dfs_stack.pop();
			} else {
				dfs[++index] = v;
				v.isVisited = true;
				dfs_stack.push(v);
			}
		}
	}
	/* 广度优先遍历 */
	public void bfs(Graph graph) {
		int num = graph.listVertex.length;
		bfs = new Vertex[num];
		ArrayDeque<Vertex> queue = new ArrayDeque<Vertex>();
		bfs[0] = graph.listVertex[0];
		queue.add(graph.listVertex[0]);
		graph.listVertex[0].isVisited = true;
		Vertex vv;
		int index = 0;
		while (!queue.isEmpty()) {
			Vertex v = queue.remove();
			while ((vv = getAdjVertex(v)) != null) {
				queue.add(vv);
				bfs[++index] = vv;
				vv.isVisited = true;
			}
		}
	}
	public static Vertex getAdjVertex(Vertex v) {
		ArrayList<Vertex> alv = v.getAdj();
		if (alv != null) {
			for (int k = 0; k < alv.size(); k++) {
				if (alv.get(k).isVisited == false) {
					return alv.get(k);
				}
			}
		}
		return null;
	}
	public static void main(String[] args) {
		System.out.println("Input the number of vertex:");
		Scanner scan = new Scanner(System.in);
		int node_num = scan.nextInt();
		System.out.println("Is this directed graph?");
		boolean flag = scan.nextBoolean();
		Graph graph = new Graph(node_num, flag);
		/* 构建图的节点 */
		for (int k = 0; k < node_num; k++) {
			graph.listVertex[k] = new Vertex(k);
		}
		/* 构建图的边 */
		System.out.println("Input the each node of each edge:-1 to exit");
		int i = 0, j = 0;
		while ((i = scan.nextInt()) != -1) {
			j = scan.nextInt();
			graph.addEdge(i, j);
		}
		Traversal_test dt = new Traversal_test();
		/* 深度优先遍历 */
		dt.dfs(graph);
		if (dt.dfs.length < graph.listVertex.length) {
			System.out.println("The graph is not a connected path!");
		} else {
			System.out.println("The depth-first traversal of this graph is:");
			for (int k = 0; k < dt.dfs.length; k++) {
				System.out.println(dt.dfs[k].toString());
			}
		}
		/* 广度优先遍历 */
		/* 重新构图 */
		/* 将节点重置为未访问 */
		for (int k = 0; k < node_num; k++) {
			graph.listVertex[k].isVisited = false;
		}
		dt.bfs(graph);
		if (dt.bfs.length < graph.listVertex.length) {
			System.out.println("The graph is not a connected path!");
		} else {
			System.out.println("The breadth-first traversal of this graph is:");
			for (int k = 0; k < dt.bfs.length; k++) {
				System.out.println(dt.bfs[k].toString());
			}
		}
		scan.close();
	}
}

小结

这篇笔记主要总结了图的邻接表实现法，邻接表在教科书和其它数据结构的书上介绍的不多，网上的实现大多也是基于多个类的“全功能”图。我总结这篇笔记的目的是以尽可能简单的代码实现邻接表图的基本功能，这在以后回忆知识点的时候会非常有帮助。到这篇文章，图的常见存储和遍历方法基本做了个笔记，接下来是运用这些方法做一些运用。（判断最短路径，拓扑排序等）

参考阅读：

java使用邻接表对图进行深度和广度遍历

Future belongs to the few of us still wiling to get our hands dirty.

Share Comments