图的深度优先搜索DFS

不念不忘少年蓝@ 2022-08-06 11:11 203阅读 0赞

import java.util.Stack;
    
    public class DFSDemo {
    
    	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 F H C D G I E 
    		 * 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];
    		Stack<Integer> stack = new Stack<Integer>();
    		stack.push(0);
    		isVisited[0] = true;
    		System.out.print(vertices[0] + " ");
    		while(!stack.isEmpty()) {
    			int v = getAdjUnvisitedVertex(stack.peek(), edges, isVisited);
    			if(v == -1) {
    				stack.pop();
    			} else {
    				stack.push(v);
    				isVisited[v] = true;
    				System.out.print(vertices[v] + " ");
    			}
    		}
    		System.out.println();
    	}
    
    	public static int getAdjUnvisitedVertex(int cur, int[][] edges, boolean[] isVisited) {
    		// TODO Auto-generated method stub
    		for(int i = 0; i < edges[cur].length; i++) {
    			if(edges[cur][i]==1 && !isVisited[i]) {
    				return i;
    			}
    		}
    		return -1;
    	}
    
    }

输出结果：

A B C D E

发表评论取消回复

表情：

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

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

相关阅读

相关深度优先搜索（DFS）

文章目录一、简介二、DFS的代码实现三、代码测试一、简介深度优先搜索是一种常见的图搜索算法，它可以用于寻找图中从起点到终点的路径或遍历

小灰灰/ 2024年03月22日 14:50/ 0 赞/ 118 阅读

相关深度优先搜索(DFS)

目录 1.基本思想 2.代码实现（C++） 3.性能分析 1.基本思想深度优先搜索(Depth-First-Search,DFS)的基本思想如

曾经终败给现在/ 2023年10月06日 16:51/ 0 赞/ 22 阅读

相关 leecode 深度优先搜索 DFS

104 [二叉树的最大深度][Link 1] Definition for a binary tree node. class TreeNode(ob

曾经终败给现在/ 2023年06月09日 10:13/ 0 赞/ 26 阅读

相关图的DFS(深度优先搜索)C语言详解

实现如图的DFS（邻接矩阵） ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

﹏ヽ暗。殇╰゛Y/ 2023年05月28日 05:11/ 0 赞/ 45 阅读

相关 DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节

缺乏、安全感/ 2022年10月30日 04:26/ 0 赞/ 214 阅读

相关 leetcode深度优先搜索（dfs）

1. 图像渲染有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像

深碍√TFBOYSˉ_/ 2022年09月04日 09:53/ 0 赞/ 205 阅读

相关图的深度优先搜索DFS

import java.util.Stack; public class DFSDemo { public static void

不念不忘少年蓝@/ 2022年08月06日 11:11/ 0 赞/ 204 阅读

相关 DFS-深度优先搜索—2

在这一篇博客：[http://blog.csdn.net/hacker\_zhidian/article/details/54773762][http_blog.csdn.ne

落日映苍穹つ/ 2022年07月11日 13:19/ 0 赞/ 229 阅读

相关 DFS深度优先搜索模板

package test; public class DFS { final static int MAXN = 100;

亦凉/ 2022年06月03日 09:54/ 0 赞/ 212 阅读

相关深度优先搜索（DFS）

DFS是相对于BFS的另一个中图搜索算法，其与BFS最大的不同在于它是深度优先，它会优先顺着一条路径走到底，一旦某个节点邻接的节点都被发现了，就会回溯到前面一个节点，直

以你之姓@/ 2022年05月15日 01:13/ 0 赞/ 274 阅读