图的广度优先搜索BFS

Love The Way You Lie 2022-08-06 11:11 141阅读 0赞

public class BFSDemo {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		
    		char[] vertices = {'A', 'B', 'C', 'D', 'E'};
    		int[][] edges = {
    				{0, 1, 0, 1, 0},
    				{1, 0, 1, 0, 0},
    				{0, 1, 0, 0, 0},
    				{1, 0, 0, 0, 1},
    				{0, 0, 0, 1, 0}
    			};
    		/*第二组测试数据->输出结果->A B C D E F G H I 
    		char[] vertices = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
    		int[][] edges = {
    				{0, 1, 1, 1, 1, 0, 0, 0, 0},
    				{1, 0, 0, 0, 0, 1, 0, 0, 0},
    				{1, 0, 0, 0, 0, 0, 0, 0, 0},
    				{1, 0, 0, 0, 0, 0, 1, 0, 0},
    				{1, 0, 0, 0, 0, 0, 0, 0, 0},
    				{0, 1, 0, 0, 0, 0, 0, 1, 0},
    				{0, 0, 0, 1, 0, 0, 0, 0, 1},
    				{0, 0, 0, 0, 0, 1, 0, 0, 0},
    				{0, 0, 0, 0, 0, 0, 1, 0, 0}
    			};*/
    		boolean[] isVisited = new boolean[vertices.length];
    		
    		LinkedList<Integer> queues = new LinkedList<Integer>();
    		queues.offer(0);
    		isVisited[0] = true;
    		System.out.print(vertices[0] + " ");
    		while(!queues.isEmpty()) {
    			int par = queues.poll();
    			for(int i = 0; i < edges[par].length; i++) {
    				if(edges[par][i]==1 && !isVisited[i]) {
    					queues.offer(i);
    					isVisited[i] = true;
    					System.out.print(vertices[i] + " ");
    				}
    			}
    		}
    		System.out.println();
    	}
    
    }

输出结果：

A B D C E

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关 BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则

青旅半醒/ 2022年10月30日 04:26/ 0 赞/ 129 阅读

相关 leetcode广度优先搜索（bfs）

1. 01 矩阵给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的

柔光的暖阳◎/ 2022年09月04日 12:41/ 0 赞/ 136 阅读

相关标程: 广度优先搜索 BFS

贴个标程, 以方便查阅. \include <iostream> \include <algorithm> \include <vector> \include <queue

àì夳堔傛蜴生んèń/ 2022年08月09日 15:48/ 0 赞/ 126 阅读

相关图的广度优先搜索BFS

public class BFSDemo { public static void main(String[] args) { // T

Love The Way You Lie/ 2022年08月06日 11:11/ 0 赞/ 142 阅读

相关广度优先搜索BFS（迷宫问题）

问题及代码：给出迷宫的图纸和初始终点位置，用DFS求最小步数。 include <iostream> include <cstring>

逃离我推掉我的手/ 2022年07月28日 04:11/ 0 赞/ 165 阅读

相关 BFS广度优先搜索

BFS(Breadth-First Search)，广度优先搜索，又称宽度优先搜索。目的从某个状态出发，彻底地遍历所有可以到达的状态。设s为初始状态，先搜索与

快来打我*/ 2022年07月18日 01:16/ 0 赞/ 186 阅读

相关广度/宽度优先搜索(BFS)

本文转自[http://rapheal.iteye.com/blog/1526861][http_rapheal.iteye.com_blog_1526861] 适合初学

超、凢脫俗/ 2022年06月17日 01:29/ 0 赞/ 182 阅读

相关图的广度优先搜索

广度优先搜索算法是最简便的图的搜索算法之一，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到

柔情只为你懂/ 2022年06月09日 09:58/ 0 赞/ 159 阅读

相关广度优先搜索（BFS）

BFS是一种图搜索算法，当然这种思想也可以被借鉴到各种其他的算法中。对于图中的所有节点，我们选一个起始点s，然后去发现（遍历）所有从s 点出发能直接到达的点，为了记

蔚落/ 2022年05月15日 00:46/ 0 赞/ 260 阅读

相关图的广度优先搜索

图的广度优先搜索广度优先搜索算法是最简便的图的搜索算法之一，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻

逃离我推掉我的手/ 2022年05月14日 13:19/ 0 赞/ 166 阅读