Java編程實(shí)現(xiàn)深度優(yōu)先遍歷與連通分量代碼示例

更新時(shí)間：2017年11月24日 14:20:31 作者：HeatDeath

這篇文章主要介紹了Java編程實(shí)現(xiàn)深度優(yōu)先遍歷與連通分量代碼示例，

深度優(yōu)先遍歷

深度優(yōu)先遍歷類似于一個(gè)人走迷宮：

如圖所示，從起點(diǎn)開始選擇一條邊走到下一個(gè)頂點(diǎn)，沒(méi)到一個(gè)頂點(diǎn)便標(biāo)記此頂點(diǎn)已到達(dá)。

當(dāng)來(lái)到一個(gè)標(biāo)記過(guò)的頂點(diǎn)時(shí)回退到上一個(gè)頂點(diǎn)，再選擇一條沒(méi)有到達(dá)過(guò)的頂點(diǎn)。

當(dāng)回退到的路口已沒(méi)有可走的通道時(shí)繼續(xù)回退。

而連通分量，看概念：無(wú)向圖G的極大連通子圖稱為G的連通分量( Connected Component)。任何連通圖的連通分量只有一個(gè)，即是其自身，非連通的無(wú)向圖有多個(gè)連通分量。

下面看看具體實(shí)例：

package com.dataStructure.graph;
// 求無(wú)權(quán)圖的聯(lián)通分量
public class Components {
	private Graph graph;
	// 存放輸入的數(shù)組
	private Boolean[] visited;
	// 存放節(jié)點(diǎn)被訪問(wèn)狀態(tài)
	private int componentCount;
	// 連通分量的數(shù)量
	private int[] mark;
	// 存儲(chǔ)節(jié)點(diǎn)所屬聯(lián)通分量的標(biāo)記
	// 構(gòu)造函數(shù)，初始化私有屬性
	public Components(Graph graph) {
		this.graph = graph;
		componentCount = 0;
		// 連通分量初始數(shù)量為 0
		visited = new Boolean[graph.V()];
		mark = new int[graph.V()];
		for (int i = 0; i < graph.V(); i++) {
			visited[i] = false;
			// 節(jié)點(diǎn)初始訪問(wèn)狀態(tài)為 false
			mark[i] = -1;
			// 節(jié)點(diǎn)初始連通分量標(biāo)記為 -1
		}
		for (int i = 0; i < graph.V(); i++) {
			// 對(duì)于未被訪問(wèn)的節(jié)點(diǎn)進(jìn)行 dfs深度優(yōu)先遍歷
			if (!visited[i]) {
				dfs(i);
				componentCount++;
				// 對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行dfs 到底后，一個(gè)連通分量結(jié)束，數(shù)量+1
			}
		}
	}
	private void dfs(int i) {
		visited[i] = true;
		// 節(jié)點(diǎn) i 已被訪問(wèn)
		mark[i] = componentCount;
		// 節(jié)點(diǎn) i 屬于當(dāng)前連通分量的數(shù)量（標(biāo)記）
		for (int node : graph.adjacentNode(i)) {
			// 遍歷圖中節(jié)點(diǎn) i 的鄰接節(jié)點(diǎn)
			if (!visited[node]) // 對(duì)未被訪問(wèn)的鄰接節(jié)點(diǎn)進(jìn)行 dfs
			dfs(node);
		}
	}
	public Boolean isConnected(int v, int w) {
		return mark[v] == mark[w];
		// 根據(jù)兩節(jié)點(diǎn)所屬連通分量的標(biāo)記判斷兩節(jié)點(diǎn)是否相連
	}
	public int getComponentCount() {
		return componentCount;
		// 返回 graph 中連通分量的數(shù)量
	}
}
//public class Components {
//
//  private Graph G;          // 圖的引用
//  private boolean[] visited; // 記錄dfs的過(guò)程中節(jié)點(diǎn)是否被訪問(wèn)
//  private int ccount;     // 記錄聯(lián)通分量個(gè)數(shù)
//  private int[] id;      // 每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的聯(lián)通分量標(biāo)記
//
//  // 圖的深度優(yōu)先遍歷
//  private void dfs(int v) {
//
//    visited[v] = true; // 節(jié)點(diǎn) v 的訪問(wèn)狀態(tài)置為 true
//    id[v] = ccount; // 節(jié)點(diǎn) v 對(duì)應(yīng)的聯(lián)通標(biāo)記設(shè)置為 ccount
//
//    // 遍歷節(jié)點(diǎn) v 的鄰接點(diǎn) i
//    for (int i : G.adjacentNode(v)) {
//      // 如果鄰接點(diǎn) i 尚未被訪問(wèn)
//      if (!visited[i])
//        // 對(duì)鄰接點(diǎn) i 進(jìn)行深度優(yōu)先遍歷
//        dfs(i);
//    }
//  }
//
//  // 構(gòu)造函數(shù), 求出無(wú)權(quán)圖的聯(lián)通分量
//  public Components(Graph graph) {
//
//    // 算法初始化
//    G = graph;
//
//    // visited 數(shù)組存儲(chǔ) 圖G 中 節(jié)點(diǎn)的被訪問(wèn)狀態(tài)
//    visited = new boolean[G.V()];
//
//    // id 數(shù)組存儲(chǔ) 圖G 中 節(jié)點(diǎn)所屬連通分量的標(biāo)記
//    id = new int[G.V()];
//
//    // 連通分量數(shù)量初始化為 0
//    ccount = 0;
//
//    // 將 visited 數(shù)組全部置為 false； id 數(shù)組全部置為 -1
//    for (int i = 0; i < G.V(); i++) {
//      visited[i] = false;
//      id[i] = -1;
//    }
//
//    // 求圖的聯(lián)通分量
//    for (int i = 0; i < G.V(); i++)
//      // 訪問(wèn)一個(gè)未曾被訪問(wèn)的節(jié)點(diǎn)
//      if (!visited[i]) {
//        // 對(duì)其進(jìn)行深度優(yōu)先遍歷
//        dfs(i);
//        ccount++;
//      }
//  }
//
//  // 返回圖的聯(lián)通分量個(gè)數(shù)
//  int count() {
//    return ccount;
//  }
//
//  // 查詢點(diǎn)v和點(diǎn)w是否聯(lián)通（節(jié)點(diǎn)v 和 w 的聯(lián)通分量的標(biāo)記是否相同
//  boolean isConnected(int v, int w) {
//    assert v >= 0 && v < G.V();
//    assert w >= 0 && w < G.V();
//    return id[v] == id[w];
//  }
//}