本文共 2580 字，大约阅读时间需要 8 分钟。

所谓图的遍历，即是对结点的访问。-一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历

图的深度优先遍历介绍

深度优先遍历基本思想：图的深度优先搜素(Depth FirstSearch)：DFS

1. 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点。 然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解: 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
3. 显然，深度优先搜索是一个递归的过程

深度优先遍历算法步骤

1. 访问初始结点v。并标记结点v为已访问。
2. 查找结点v的第-一个邻按结点w.
3. 若w存在，则继续执行4，如果w不存在，则回到第1步， 将从v的下一个结点继续。
4. 若w未被访问，对w进行深度优先遍历递归(即把w当做另一个v，然后进行步骤123)。
5. 查找结点v的w邻按结点的下一个邻接结点，转到步骤3。

代码实现：在原先的代码基础上进行添加：

public boolean[] isVisited; // 记录被访问了的节点	public Graph(int n) {
   		edges = new int[n][n];		vertexList = new ArrayList
   
    (n);		num = 0;		isVisited = new boolean[n];	}
   

添加方法：

// 得到第一个邻接节点的下标	public int getFirstNode(int index) {
   		for (int j = 0; j < vertexList.size(); j++) {
   			if (edges[index][j] > 0) {
    // 存在下一个节点				return j;			}		}		return -1;	}	// 根据前一个邻接节点的下标获取下一个邻接节点	public int getNextNode(int v1, int v2) {
   		for (int j = v2 + 1; j < vertexList.size(); j++) {
   			if (edges[v1][j] > 0) {
   				return j;			}		}		return -1;	}	// 深度优先遍历	private void DFS(boolean[] isVisited, int i) {
   		// 先进行访问i		System.out.print(getValue(i) + " -> ");		// 把这个节点设置为已访问		isVisited[i] = true;		// 查找第一个邻接节点		int w = getFirstNode(i);		while (w != -1) {
   			if (!isVisited[w]) {
   // 节点还未被访问				DFS(isVisited, w);			}			// 已经被访问,查找下一个邻接 节点			w = getNextNode(i, w);		}	}	// 对DFS进行重载	public void DFS() {
   		// 遍历所有节点进行DFS		for (int i = 0; i < nodeNum(); i++) {
   			if (!isVisited[i]) {
   				DFS(isVisited, i);			}		}	}

图的广度优先搜索(Broad First Search)。

广度优先遍历算法步骤

1. 访问初始结点v并标记结点v为已访问。
2. 结点v入队列
3. 当队列非空时， 继续执行，否则算法结束。
4. 出队列， 取得队头结点u。.
5. 查找结点u的第一 个邻接结点w.
6. 若结点u的邻接结点w不存在，则转到步骤3;否则循环执行以下三个步骤：
   6.1 若结点w尚未被访问，则访问结点w并标记为己访问。
   6.2 结点w入队列
   6.3 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

使用代码实现广度优先遍历，添加对应的方法。

// 广度优先遍历	public void BFS(boolean[] isVisited, int i) {
   		int u; // 队列的头节点		int w; // 邻接节点		LinkedList queue = new LinkedList(); // 使用队列记录访问顺序		System.out.print(getValue(i) + " -> ");		isVisited[i] = true;		queue.addLast(i);		while (!queue.isEmpty()) {
   			// 取出队列头节点下标			u = (Integer) queue.removeFirst();			w = getFirstNode(u);			while (w != -1) {
   				// 是否被访问过				if (!isVisited[w]) {
   					System.out.print(getValue(w) + " -> ");					isVisited[w] = true;					// 入队列					queue.addLast(w);				}				w= getNextNode(u, w); //继续找下一个节点			}		}	}	public void BFS() {
   		// 遍历所有节点进行DFS		for (int i = 0; i < nodeNum(); i++) {
   			if (!isVisited[i]) {
   				BFS(isVisited, i);			}		}	}

转载地址：http://ogmzi.baihongyu.com/