图的深度优先遍历 邻接表（头结点边结点）

8.3.1深度优先搜索遍历

 

　　图的深度优先搜索遍历类似于二叉树的深度优先搜索遍历。其基本思想如下：假定以图中某个顶点Vi为出发点，首先访问出发点，然后选择一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。显然，这是一个递归的搜索过程。

 

　　现以图8.15为例说明深度优先搜索过程。假定V1是出发点，首先访问V1。因V1有两个邻接点V2、V3均末被访问过，可以选择V2作为新的出发点，访问V2之后，再找V2的末访问过的邻接点。同V2邻接的有V1、V4和V5，其中V1已被访问过，而V4、V5尚未被访问过，可以选择V4作为新的出发点。重复上述搜索过程，继续依次访问V8、V5 。访问V5之后，由于与V5相邻的顶点均已被访问过，搜索退回到V8，访问V8的另一个邻接点V6。接下来依次访问V3和V7，最后得到的的顶点的访问序列为：V1 → V2 → V4 → V8 → V5 → V6 → V3 → V7。

 

package abc.graph;

import java.util.ArrayList;
import java.util.List;

public class AlGraph {
	
	List<HeadNode> headNodes = new ArrayList<HeadNode>();
	
	void addVertex(HeadNode node) {
		headNodes.add(node);
	}
	
	void addArc(HeadNode head, HeadNode tail) {
		if(head.firstArcNode == null)
			head.firstArcNode = new ArcNode(tail);
		else {
			ArcNode arcNode = head.firstArcNode;
			while (arcNode.nextArcNode != null) {
				arcNode = arcNode.nextArcNode;
			}
			arcNode.nextArcNode = new ArcNode(tail);
		}
	}
	
	public void DFSTraverse() {
		InitVisited();
		DFS(headNodes.get(0));
	}
	private void DFS(HeadNode node) {
		node.isVisited = true;
		System.out.print(node.name);
		System.out.print(" -> ");
		
		ArcNode arcNode = node.firstArcNode;
		while(arcNode != null) {
			if(arcNode.headNode.isVisited != true)
				DFS(arcNode.headNode);
			arcNode = arcNode.nextArcNode;
		}
	}
	
	private void InitVisited() {
		for(HeadNode node : headNodes) {
			node.isVisited = false;
		}
	}
	
	static AlGraph createAlGraph() {
		AlGraph alGraph = new AlGraph();
		
		HeadNode V1 = new HeadNode("V1");
		HeadNode V2 = new HeadNode("V2");
		HeadNode V3 = new HeadNode("V3");
		HeadNode V4 = new HeadNode("V4");
		HeadNode V5 = new HeadNode("V5");
		HeadNode V6 = new HeadNode("V6");
		HeadNode V7 = new HeadNode("V7");
		HeadNode V8 = new HeadNode("V8");
		
		
		alGraph.addVertex(V1);
		alGraph.addVertex(V2);
		alGraph.addVertex(V3);
		alGraph.addVertex(V4);
		alGraph.addVertex(V5);
		alGraph.addVertex(V6);
		alGraph.addVertex(V7);
		alGraph.addVertex(V8);
		
		alGraph.addArc(V1, V2);			alGraph.addArc(V1, V3);
		alGraph.addArc(V2, V1);			alGraph.addArc(V2, V4);	alGraph.addArc(V2, V5);
		alGraph.addArc(V3, V1);			alGraph.addArc(V3, V6);	alGraph.addArc(V3, V7);
		alGraph.addArc(V4, V2);			alGraph.addArc(V4, V8);
		alGraph.addArc(V5, V2);			alGraph.addArc(V5, V8);
		alGraph.addArc(V6, V3);			alGraph.addArc(V6, V8);
		alGraph.addArc(V7, V3);			alGraph.addArc(V7, V8);
		alGraph.addArc(V8, V4);			alGraph.addArc(V8, V5);	alGraph.addArc(V8, V6);	alGraph.addArc(V8, V7);
		
		return alGraph;
	}
	
	void print() {
		for(HeadNode head : headNodes) {
			System.out.print(head.name);
			if(head.firstArcNode != null) {
				ArcNode arcNode = head.firstArcNode;
				System.out.print(" -> ");
				System.out.print(arcNode.headNode.name);
				while (arcNode.nextArcNode != null) {
					arcNode = arcNode.nextArcNode;
					System.out.print(" -> ");
					System.out.print(arcNode.headNode.name);
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		AlGraph.createAlGraph().print();
		System.out.println("\nAlGraph DFSTraverse !!");
		AlGraph.createAlGraph().DFSTraverse();
	}
}

class ArcNode {
	HeadNode headNode;
	ArcNode nextArcNode;
	public ArcNode(HeadNode tail) {
		this.headNode = tail;
	}
}

class HeadNode {
	String name;
	ArcNode firstArcNode;
	boolean isVisited;
	
	HeadNode(String name) {
		this.name = name;
	}
}

 

 

 

输出 写道

V1 -> V2 -> V3
V2 -> V1 -> V4 -> V5
V3 -> V1 -> V6 -> V7
V4 -> V2 -> V8
V5 -> V2 -> V8
V6 -> V3 -> V8
V7 -> V3 -> V8
V8 -> V4 -> V5 -> V6 -> V7

AlGraph DFSTraverse !!
V1 -> V2 -> V4 -> V8 -> V5 -> V6 -> V3 -> V7 ->