博客

一.图的深度优先遍历

1.基本思想


从初始访问节点出发，首先访问第一个节点，然后再以这个被访问的节点的邻接节点作为初始节点，访问它的第一个邻接节点，依次进行，显然这是一个递归的过程


2.算法步骤


1）访问初始节点v，并标记节点v以访问

2）查找节点v的第一个邻接节点w

3）若w存在，执行4，若w不存在，回到第一步，从v的下一个节点继续

4）若w未被访问，对w进行深度优先遍历递归

5）若w被访问，以下一个邻接节点作为初始节点进行递归


3.代码实现

//得到第一个结点的下标
	public int getfirstNeighbor(int index){
		for(int j=0;j<vertexList.size();j++){
			if(edges[index][j]>0){
				return j;
			}
		}
		return -1;
	}
	
	//根据前一个邻接节点的下标来获取下一个邻接节点
	public int getNextNeighbor(int v1,int v2){
		for(int j=v2+1;j<vertexList.size();j++){
			if(edges[v1][j]>0){
				return j;
			}
		}
		return -1;
	}
	
	//深度优先遍历
	/* isVisited[] 记录节点是否访问的数组
	 * i 第一次是0
	 */
	public void dfs(boolean[] isVisited,int i){
		//首先访问该节点，输出
		System.out.print(getValueByIndex(i)+"->");
		isVisited[i]=true;
		int w=getfirstNeighbor(i);
		while(w!=-1){
			//说明有邻接节点
			if(!isVisited[w]){
				dfs(isVisited,w);
			}
			
			//如果该节点被访问
			w=getNextNeighbor(i,w);
		}
	}
	
	//重载dfs方法
	public void dfs(){
		isVisited=new boolean[vertexList.size()];
		//遍历所有的节点进行dfs回溯
		for(int i=0;i<vertexList.size();i++){
			if(!isVisited[i]){
				dfs(isVisited,i);
			}
		}
	}
	

二.图的广度优先遍历

1.基本思想


与深度优先遍历不同的是，广度优先在选出初始节点后，依次访问与初始节点邻接的节点，直到没有节点与之邻接，同时，广度优先遍历需要使用一个队列来保持访问过节点的顺序。


2.算法步骤


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的继ww邻接节点的下一个邻接节点w，转到步骤6

3.代码

//广度优先遍历
	public void bfs(boolean isVisited[],int i){
		int u; //表示队列的头节点对应下标
		int w; //邻接节点
		//队列，记录访问节点的顺序
		LinkedList queue=new LinkedList();
		//输出访问节点信息
		System.out.println(getValueByIndex(i)+"->");
		//标记为已访问
		isVisited[i]=true;
		//将一访问的节点加入队列
		queue.addLast(i);
		while(!queue.isEmpty()){
			//取出队列的头节点下标
			u=(Integer)queue.removeFirst();
			//得到第一个邻接节点的下标
			w=getfirstNeighbor(u);
			while(w!=-1){
				//是否访问过
				if(!isVisited[w]){
					System.out.println(getValueByIndex(w)+"->");
					//标记为已访问
					isVisited[w]=true;
					//入队
					queue.addLast(w);
				}
				//以u为前驱点，找w后面的下一个节点
				w=getNextNeighbor(u,w);
			}
		}
	}
	
	//遍历所有的节点，都进行广度优先搜索
	public void bfs(){
		isVisited=new boolean[vertexList.size()];
		for(int i=0;i<vertexList.size();i++){
			if(!isVisited[i]){
				bfs(isVisited,i);
			}
		}
	}

3.全部代码

package text_six_tu;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class one {
	private ArrayList<String> vertexList;//存储节点集合
	private int[][] edges;//存储邻接矩阵
	private int numOfEdges;//表示边的数目
	//判断节点是否已经访问
	private boolean[] isVisited;

	public static void main(String[] args) {
		int n=6;
		String vertexs[]={"A","B","C","D"};
		one graph=new one(6);
		for(String vertex : vertexs){
			graph.insertVertex(vertex);
		}
		
		graph.insertEdge(0, 1, 2);
		graph.insertEdge(0, 2, 5);
		graph.insertEdge(2, 3, 5);
		graph.insertEdge(1, 3, 8);
		
		graph.showGreph();
		graph.bfs();

	}
	//构造器
	public one(int n){
		vertexList = new ArrayList<String>(n);
		edges=new int[n][n];
		numOfEdges=0;
		
	}
	
	//得到第一个结点的下标
	public int getfirstNeighbor(int index){
		for(int j=0;j<vertexList.size();j++){
			if(edges[index][j]>0){
				return j;
			}
		}
		return -1;
	}
	
	//根据前一个邻接节点的下标来获取下一个邻接节点
	public int getNextNeighbor(int v1,int v2){
		for(int j=v2+1;j<vertexList.size();j++){
			if(edges[v1][j]>0){
				return j;
			}
		}
		return -1;
	}
	
	//深度优先遍历
	/* isVisited[] 记录节点是否访问的数组
	 * i 第一次是0
	 */
	public void dfs(boolean[] isVisited,int i){
		//首先访问该节点，输出
		System.out.print(getValueByIndex(i)+"->");
		isVisited[i]=true;
		int w=getfirstNeighbor(i);
		while(w!=-1){
			//说明有邻接节点
			if(!isVisited[w]){
				dfs(isVisited,w);
			}
			
			//如果该节点被访问
			w=getNextNeighbor(i,w);
		}
	}
	
	//重载dfs方法
	public void dfs(){
		isVisited=new boolean[vertexList.size()];
		//遍历所有的节点进行dfs回溯
		for(int i=0;i<vertexList.size();i++){
			if(!isVisited[i]){
				dfs(isVisited,i);
			}
		}
	}
	
	//广度优先遍历
	public void bfs(boolean isVisited[],int i){
		int u; //表示队列的头节点对应下标
		int w; //邻接节点
		//队列，记录访问节点的顺序
		LinkedList queue=new LinkedList();
		//输出访问节点信息
		System.out.println(getValueByIndex(i)+"->");
		//标记为已访问
		isVisited[i]=true;
		//将一访问的节点加入队列
		queue.addLast(i);
		while(!queue.isEmpty()){
			//取出队列的头节点下标
			u=(Integer)queue.removeFirst();
			//得到第一个邻接节点的下标
			w=getfirstNeighbor(u);
			while(w!=-1){
				//是否访问过
				if(!isVisited[w]){
					System.out.println(getValueByIndex(w)+"->");
					//标记为已访问
					isVisited[w]=true;
					//入队
					queue.addLast(w);
				}
				//以u为前驱点，找w后面的下一个节点
				w=getNextNeighbor(u,w);
			}
		}
	}
	
	//遍历所有的节点，都进行广度优先搜索
	public void bfs(){
		isVisited=new boolean[vertexList.size()];
		for(int i=0;i<vertexList.size();i++){
			if(!isVisited[i]){
				bfs(isVisited,i);
			}
		}
	}
	//返回节点个数
	public int getnumOfVertsx(){
		return vertexList.size();
	}
	//显示图对应的矩阵
	public void showGreph(){
		for(int[] link : edges){
			System.out.println(Arrays.toString(link));
		}
	}
	//得到边的数目
	public int getOfEdges(){
		return numOfEdges;
	}
	//返回节点i
	public String getValueByIndex(int i){
		return vertexList.get(i);
	}
	//返回v1和v2的权值
	public int getWeight(int v1,int v2){
		return edges[v1][v2];
	}
	//插入结点
	public void insertVertex(String vertex){
		vertexList.add(vertex);
	}
	//添加边
	public void insertEdge(int v1,int v2,int weight){
		edges[v1][v2]=weight;
		edges[v2][v1]=weight;
		numOfEdges++;
	}

}