图－广度优先遍历

这里的图的广度优先遍历算法利用了队来实现。

图的深度遍历原则：

1 如果有可能，访问所有领接的未访问的节点，标记它们，并把它们放入队中。

2 当不能执行规则 1 时，如果对不为空，则从队中弹出头元素。重新执行规则 1

3 如果不能执行规则 1 和规则 2 时，则完成了遍历。

代码中的图使用的是Graph 图－邻接矩阵法 来表示，其他的表示法请见：Graph 图－邻接表法

代码中的Queue为辅助结构，用来记载访问过的节点。队列的详细描述可以见：Queue 队 ，LinkedQueue 队

Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。

Graph.main：提供简单测试。代码可以以指定下标的节点开始作广度优先遍历。

代码比较简单，除了Graph.bsf(int i)广度优先遍历算法外没有过多注释。

class Queue {
	private int[] values;
	private int begin = -1;
	private int end = -1;
	Queue(int size) {
		values = new int[size];
	}
	void push(int value) { values[++begin] = value; }
	int pop() { return values[++end]; }
	boolean isEmpty() { return begin == end; }
}

class Vertex {
	private Object value;
	private boolean isVisited;
	Vertex(Object value) {
		this.value = value;
	}

	void visit() { isVisited = true; print(); }
	void clean() {	isVisited = false; }
	boolean isVisited() { return isVisited; }
	void print() { System.out.println(value); }
}

class Graph {
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int pos = -1;

	Graph(int size) {
		vertexs = new Vertex[size];
		adjMat = new int[size][size];
	}

	void add(Object value) {
		assert pos < vertexs.length;
		vertexs[++pos] = new Vertex(value);
	}

	void connect(int from, int to) {
		adjMat[from][to] = 1;
		adjMat[to][from] = 1;
	}

	void disConnect(int from, int to) {
		adjMat[from][to] = 0;
		adjMat[to][from] = 0;
	}

	int findNeighbor(int index) {
		for(int i=0; i<=pos; i++) {
			if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	void bsf(int index) {	//从指定下标的节点开始深度优先遍历
		if(vertexs[index] == null) return;	//如果图中没有指定下标节点，则退出
		Queue q = new Queue(vertexs.length);	//创建队列存放访问过的节点
		vertexs[index].visit(); //访问指定节点
		q.push(index);	//将节点推入队列中
		while(!q.isEmpty()) {	//队列为空则表示遍历结束
			index = q.pop();	//取出队头
			int i; 
			while((i=findNeighbor(index)) != -1) {	//寻找头节点的所有邻接节点
				vertexs[i].visit();	//标记访问过的邻接节点
				q.push(i);	//放入队列中
			} 
		} 
	}

	void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

	public static void main(String[] args) {
		Graph g = new Graph(20);
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		g.connect(0,1);
		g.connect(1,2);
		g.connect(0,3);
		g.connect(3,4);
		g.bsf(0);
	}
}

 

评论

2 楼 wenhui45 2009-11-13  

楼主，是否可以考虑下让队列成为循环队列，现在这个好像没有这个机制，

1 楼 walsh 2008-12-02  

第一次看到楼主的算法这么全，辛苦了，谢谢楼主！！！