广度优先遍历原理和实现

2020年10月7日 12点热度 0条评论 来源: 菜鸟小党

广度优先遍历原理及其实现

对于广度优先遍历代码的实现原理主要是基于数据结构------队列,来实现的,通过队列的出队列进行结点之间的转换。

举例说明

下面给出一个无向图的连接例子
A------------- B
A------------- C
B------------- C
B------------- E
B------------- D

分析

这里采用的为5个结点进行的图结构构建,进行广度优先遍历得到的结果为
A-B-C-D-E
这里对实现过程进行简单叙述:

  1. 首先是选中一个结点这里选择A节点进行加入队列,以A所在行为主进行B,C,D,E中是否存在与A相连接的节点,有便输出,
  2. 即A-B-C,再往后便没有连接,终止。

这里相比于深度优先遍历来讲,一直以A节点为中心,而不是A-B后以B为中心

  1. A没有了连接的节点,执行出队列操作,往后的节点以此类推。

实现代码:

1、首先是需要编写得到首节点和下一个节点的矩阵数值的函数

//得到第一个邻接坐标
	public static  int getFirstNeighboor(int index){ 
		for(int j = 0;j<verterList.size();j++){ 
			if(edges[index][j]>0){ 
				return j;
			}
		}
		return -1;
	}
	//根据前一个节点的下标来获取一个邻接节点
	public static int getNextNeighbor(int v1,int v2){ 
		for(int j = v2+1;j<verterList.size();j++){ 
			if(edges[v1][j] > 0){ 
				return j;
			}
		}
		return -1;
	}

2、其次是对图进行初始化

//构造器
	public Graph(int n){ 
		//初始化矩阵
		verterList = new ArrayList<String>(n);
		edges = new int [n][n];
		numdeges = 0;
		
		
	}

3、核心代码:

//开始广度
	//遍历所有节点
	public void bfs(){ 
		for(int i =0;i<getVerter();i++){ 
			if(!isVisited[i]){ 
				bfs(isVisited,i);
			}
		}
	}

	//对一个结点进行广度优先遍历
	private void bfs(boolean[] isVisited,int i){ 
		int u;//表示一个头节点
		int w;//表示邻接结点
		//队列,进行记录节点的访问顺序
		LinkedList queenLinkedList = new LinkedList();
		
		//访问节点输出信息
		System.out.print(getNumofIndex(i)+"=>");
		//标记为已经访问
		isVisited[i] = true;
		//加入队列
		queenLinkedList.addLast(i);
		while(! queenLinkedList.isEmpty()){ 
			//取出队列的头节点下标
			u = (Integer)queenLinkedList.removeFirst();
			//得到第一个邻接点的下标
			w = getFirstNeighboor(u);
			while(w != -1){ 
				if(! isVisited[w]){ 
					System.out.print(getNumofIndex(w)+"=>");
					isVisited[w] = true;
					//入队
					queenLinkedList.addLast(w);
				}
				//以u为前驱点,找w后面的第一个节点
				w = getNextNeighbor(u, w);//广度优先
			}
		}
		
	}

main函数

public static void main(String[] args) { 
		// TODO Auto-generated method stub

		int n = 5;//节点个数
		String vertexString[] ={ "A","B","C","D","E"};
		Graph Graph = new Graph(n);
		for(String value : vertexString){ 
			Graph.insertVer(value);
		}
		//添加边
		
		//a->b,a->c,b->c,b->d,b->e
		Graph.insertEdges(0, 1, 1);
		Graph.insertEdges(0, 2, 1);
		Graph.insertEdges(1, 2, 1);
		Graph.insertEdges(1, 3, 1);
		Graph.insertEdges(1, 4, 1);
		//显示
		Graph.print();
		System.out.println("shendu");
		//Graph.DFS();
		//Graph.DFS_real();
		Graph.bfs();
	}
	

进行广度优先遍历得到的结果为
A-B-C-D-E

    原文作者:菜鸟小党
    原文地址: https://blog.csdn.net/brotherand/article/details/117927135
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。