java算法：图遍历(深度优先和广度优先)

java算法：图遍历

递归图形遍历或深度优先搜索，系统地访问图中所有的结点的方法，如，树的遍历，也是很多递归算法的基础。

访问v，递归地访问每个附属于v的（未访问过的）结点，如果图是连通的，则最终能到达所有的结点。

例1：深度优先搜索

Java代码

1. privatevoiddfs(intk){
2. visit(k);
3. visited[k]=true;
4. for(Nodet=adj[k];t!=null;t=t.next){
5. if(!visited[t.v]){
6. dfs(t.v);
7. }
8. }
9. }

private void dfs(int k){
	visit(k);
	visited[k] = true;
	for(Node t = adj[k]; t != null; t = t.next){
		if(!visited[t.v]){
			dfs(t.v);
		}
	}
}

使用邻接表表示法在具有V个顶点和E条边的图中进行深度优先搜索所需要的时间与V+E成比例。

例2：广度优先搜索

Java代码

1. voidbfs(intk){
2. IntQueueq=newIntQueue(v*v);
3. q.put(k);
4. while(!q.empty()){
5. if(!visited[k=q.get()]){
6. Nodet;
7. visit(k);
8. visited[k]=true;
9. for(t=adj[k];t!=null;t=t.next){
10. if(!visited[t.v]){
11. q.put(t.v);
12. }
13. }
14. }
15. }
16. }

void  bfs(int k){
	IntQueue q = new IntQueue(v*v);
	q.put(k);
	while(!q.empty()){
		if(!visited[k = q.get()]){
			Node t;
			visit(k);
			visited[k] = true;
			for(t = adj[k]; t != null; t = t.next){
				if(!visited[t.v]){
					q.put(t.v);
				}
			}
		}
	}
}