|
介绍图的遍历方式之前，先来看下图的表示方式，图的表示方式常见的有三种，分别是邻接矩阵，邻接表和边集数组。邻接矩阵是表示图最直观的一种方式，可以看到各顶点之间的关系，而邻接表可以看到一个顶点指向其他顶点的数量，而边集数组就是记录每条边的起点，终点和权值的数组。 邻接矩阵
邻接矩阵就是使用一个 n*n （n是图的顶点个数）的矩阵 A 。对于无向图来说，如果顶点 i 和顶点 j 之间相连，则把 A[i][j]和 A[j][i] 标记为相同的值，如果是非加权图标记为 1 即可，如果是加权图，标记为这条边的权值。对于有向图来说，如果是顶点 i 指向顶点 j ，只需要记录 A[i][j]的值，如下图所示。 
对于简单无向图来说他的邻接矩阵是关于左上角到右下角这条线对称的，因为在无向图中 A[i][j]和 A[j][i] 的值是一样的。对于有向图来说 A[i][?] 不为 0 的个数就是点 i 的出度，A[?][j] 不为 0 的个数是点 j 的入度。 邻接表
对于稠密图（边相对比较多）来说使用邻接矩阵更合适一些，但如果是稀疏图（边相对比较少）使用邻接矩阵就会造成矩阵中很多元素是 0 ，从而导致存储空间的浪费，这个时候可以考虑使用邻接表。邻接表是一种链式存储结构，对于图中的每一个顶点 v 都建一个单向链表，将顶点 v 相关的信息存储在表头，链表的其余节点用来存放和顶点 v 相关的信息。如果是加权图需要在链表的节点中添加权值，否则可以不加。 
邻接表的特点： 邻接表方便找任一顶点的所有邻接点。 节约稀疏图的存储空间。 方便计算无向图的度，方便计算有向图的出度。
对于有向图的入度使用邻接表的方式就不太好算了，这时候我们还可以使用十字链表来表示图，图的十字链表和邻接表类似，都是使用链表，不过十字链表的头节点会有两个指针，分别指向两个链表，一个是指向出度的链表，一个是指向入度的链表，十字链表更方便查找一个顶点的出度和入度。 边集数组
边集数组是使用一维数组来存储边，一维数组中每个元素有 3 个成员组成，分别是边的起点，终点，权值，当然也可以写成二维数组 edges[m][3] ，其中 m 是边的数量，如下图所示 edges[i][0]表示第 i 条边的起点edges[i][1]表示第 i 条边的终点edges[i][2]表示第 i 条边的权值
图的遍历方法主要有深度优先搜索（DFS）和广度(宽度)优先搜索（BFS）。 深度优先搜索（DFS）
DFS 的思想类似于树的前序遍历。其遍历过程可以描述为：从图中某个顶点 v 出发沿着一个方向一直访问下去，当访问到这个方向上最后一个顶点（这个顶点之后没有下一个顶点了，或者和这个顶点相连的都被访问完了）的时候，往回退一步，查看和上一个顶点相连的有没有可访问的，如果有就继续重复上面的方式沿着另一个方向继续访问，如果没有可访问的就在回到上一个顶点 …… ，重复同样的步骤，如下图所示。当一个顶点被访问之后就不能在被访问了，所以还需要使用一个数组 visited 来记录哪些顶点被访问过。 
可以看下代码大致轮廓，这里的图使用的是邻接表，假设从顶点 u 开始访问。
public void dfsGraph(int u) {
System.out.println("这里可以打印 u 这个顶点的信息");
visited[u] = true;// 标记为被访问过，防止重复访问。
for (遍历从 u 出发能到达的所有顶点 v){
if (visited[v])// 如果当前顶点被访问过了，直接跳过。
continue;
dfsGraph(v);// 递归。
}
}
这里只是从图的一个顶点开始访问，如果要遍历整个图，需要从图的所有顶点开始，否则在有向图中有些顶点是访问不到的。我们来看下图的访问过程，如下图所示，这里选择的是非加权有向图。 
测试代码如下： public static void main(String[] args) {
int size = 5;// 顶点个数。
boolean visited[] = new boolean[size];// 标记顶点是否被访问过。
int[][] g = {{0, 1, 1, 0, 0},// 图的邻接矩阵。
{0, 0, 0, 1, 1},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}};
for (int i = 0; i < visited.length; i++) {
if (!visited[i])// 只有当前顶点没被访问过才会访问。
dfsGraph(g, visited, i);
}
}
private static void dfsGraph(int[][] g, boolean visited[], int v) {
System.out.print(v + ",");// 打印当前顶点。
visited[v] = true; // 标记已访问。
for (int i = 0; i < g.length; i++) {
if (visited[i])// 如果访问过则跳过。
continue;
if (g[v][i] == 1) // 如果相连就访问。
dfsGraph(g, visited, i);
}
}
打印结果：0,1,3,4,2, 。 广度优先搜索（BFS）
DFS 是从一个点沿着一个方向一直走下去，而 BFS 是从一个点开始，先访问和他相连的，然后在访问和他相连顶点的邻接点 …… ，一圈一圈的往外访问。 
访问图的时候需要标记哪些点被访问过，防止出现重复访问的情况，我们来看下图的 BFS 访问过程，如下图所示。 
结合上面的图我们来看下他的大致模板。
// 从图的 v 位置开始访问。
private static void bfsGraph(int[][] g, boolean visited[], int v) {
Queue<Integer> queue = new LinkedList<>();// 队列。
queue.offer(v); // 把开始访问的点放入到队列中。
while (!queue.isEmpty()) {// 队列不为空就一直循环。
int u = queue.poll();// 出队。
System.out.print(u + ",");// 打印当前顶点。
for (int i = 0; i < g.length; i++) {
if (visited[i])// 不能重复访问。
continue;
if (g[u][i] == 1) {
// 标记已访问，这里实际上还没打印，先添加到队列中。
visited[i] = true;
queue.offer(i);// 当前顶点加入到队列中。
}
}
}
}
|
