1.图的表示
图是由顶点和边组成，图最常用的两种方法就是邻接表和邻接矩阵。这两种办法分别用表和矩阵的方式描述图中各顶点之间的联系。
下面分别展示了两种表示上面这个图的方法：
2.图的遍历
广度优先遍历和深度优先遍历是遍历图的两种最常用的方法，下面将详细进行介绍。
2.1 广度优先遍历(BFS)
即Breadth First Search，其主要思想是从起始点开始，将其邻近的所有顶点都加到一个队列（FIFO）中去，然后标记下这些顶点离起始顶点的距离为1.最后将起始顶点标记为已访问，今后就不会再访问。然后再从队列中取出最先进队的顶点A，也取出其周边邻近节点，加入队列末尾，将这些顶点的距离相对A再加1，最后离开这个顶点A。依次下去，直到队列为空为止。从上面描述的过程我们知道每个顶点被访问的次数最多一次（已访问的节点不会再访问），而对于连通图来说，每个顶点都会被访问。加上每个顶点的邻接链表都会被遍历，因此BFS的时间复杂度是Θ（V+E），其中V是顶点个数，E是边数，也就是所有邻接表中的元素个数。为了更好的说明这个过程，下图列出了对一个图的BFS的过程。
代码实现：
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class BFSDemo {
public static void main(String[] args) {
//构造各顶点
LinkedList<Character> list_s = new LinkedList<Character>();
list_s.add('w');
list_s.add('r');
LinkedList<Character> list_w = new LinkedList<Character>();
list_w.add('s');
list_w.add('i');
list_w.add('x');
LinkedList<Character> list_r = new LinkedList<Character>();
list_r.add('s');
list_r.add('v');
LinkedList<Character> list_x = new LinkedList<Character>();
list_x.add('w');
list_x.add('i');
list_x.add('u');
list_x.add('y');
LinkedList<Character> list_v = new LinkedList<Character>();
list_v.add('r');
LinkedList<Character> list_i = new LinkedList<Character>();
list_i.add('u');
list_i.add('x');
list_i.add('w');
LinkedList<Character> list_u = new LinkedList<Character>();
list_u.add('i');
list_u.add('x');
list_u.add('y');
LinkedList<Character> list_y = new LinkedList<Character>();
list_y.add('u');
list_y.add('x');
//构造图
HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
graph.put('s', list_s);
graph.put('w', list_w);
graph.put('r', list_r);
graph.put('x', list_x);
graph.put('v', list_v);
graph.put('i', list_i);
graph.put('y', list_y);
graph.put('u', list_u);
//记录每个顶点离起始点的距离，也即最短距离
HashMap<Character, Integer> dist = new HashMap<Character, Integer>();
//遍历的起始点
char start = 's';
//调用广度优先方法
bfs(graph, dist, start);
}
private static void bfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Integer> dist,
char start) {
Queue<Character> q = new LinkedList<>();
q.add(start);// 将s作为起始顶点加入队列
dist.put(start, 0);
int i = 0;
while (!q.isEmpty()) {
char top = q.poll();// 取出队首元素
i++;
System.out.println("The " + i + "th element:" + top + " Distance from s is:" + dist.get(top));
int d = dist.get(top) + 1;// 得出其周边还未被访问的节点的距离
for (Character c : graph.get(top)) {
if (!dist.containsKey(c))// 如果dist中还没有该元素说明还没有被访问
{
dist.put(c, d);
q.add(c);
}
}
}
}
}
运行结果：
The 1th element:s Distance from s is:0
The 2th element:w Distance from s is:1
The 3th element:r Distance from s is:1
The 4th element:i Distance from s is:2
The 5th element:x Distance from s is:2
The 6th element:v Distance from s is:2
The 7th element:u Distance from s is:3
The 8th element:y Distance from s is:3
2.2 深度优先遍历(DFS)
即Depth First Search,深度优先搜索是从起始顶点开始，递归访问其所有邻近节点，比如A节点是其第一个邻近节点，而B节点又是A的一个邻近节点，则DFS访问A节点后再访问B节点，如果B节点有未访问的邻近节点的话将继续访问其邻近节点，否则继续访问A的未访问邻近节点，当所有从A节点出去的路径都访问完之后，继续递归访问除A以外未被访问的邻近节点。具体看下图：
代码如下：
import java.util.HashMap;
import java.util.LinkedList;
public class DFSDemo {
public static void main(String[] args) {
//构造各顶点
LinkedList<Character> list_u = new LinkedList<Character>();
list_u.add('v');
list_u.add('x');
LinkedList<Character> list_v = new LinkedList<Character>();
list_v.add('y');
LinkedList<Character> list_y = new LinkedList<Character>();
list_y.add('x');
LinkedList<Character> list_x = new LinkedList<Character>();
list_x.add('v');
LinkedList<Character> list_w = new LinkedList<Character>();
list_w.add('y');
list_w.add('z');
LinkedList<Character> list_z = new LinkedList<Character>();
//构造图
HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
graph.put('u', list_u);
graph.put('v', list_v);
graph.put('y', list_y);
graph.put('x', list_x);
graph.put('w', list_w);
graph.put('z', list_z);
HashMap<Character, Boolean> visited = new HashMap<Character, Boolean>();
//调用深度优先遍历方法
dfs(graph, visited);
}
private static void dfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited) {
visit(graph, visited, 'u');// 为了和图中的顺序一样，我认为控制了DFS先访问u节点
visit(graph, visited, 'w');
}
//通过一个全局变量count记录了进入每个节点和离开每个节点的时间
static int count;
private static void visit(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited,
char start) {
if (!visited.containsKey(start)) {
count++;
System.out.println("The time into element " + start + ":" + count);// 记录进入该节点的时间
visited.put(start, true);
for (char c : graph.get(start)) {
if (!visited.containsKey(c)) {
visit(graph, visited, c);// 递归访问其邻近节点
}
}
count++;
System.out.println("The time out element " + start + ":" + count);// 记录离开该节点的时间
}
}
}
运行结果：
The time into element u:1
The time into element v:2
The time into element y:3
The time into element x:4
The time out element x:5
The time out element y:6
The time out element v:7
The time out element u:8
The time into element w:9
The time into element z:10
The time out element z:11
The time out element w:12
