Java如何实现的图的遍历 |
您所在的位置：网站首页 › java三步判断 › Java如何实现的图的遍历 |
Java如何实现的图的遍历
|
1.图的遍历 从图中某一顶点出发访问图中其余顶点，且每个顶点仅被访问一次 图的遍历有两种深度优先遍历DFS、广度优先遍历BFS 2.深度优先遍历深度优先遍历以深度为优先进行遍历，简单来说就是每次走到底。类似于二叉树的前序遍历 思路： 1.以某一个顶点为起点进行深度优先遍历，并标记该顶点已访问 2.以该顶点为起点选取任意一条路径一直遍历到底，并标记访问过的顶点 3.第2步遍历到底后回退到上一个顶点，重复第2步 4.遍历所有顶点结束 根据遍历思路可知，这是一个递归的过程，其实DFS与回溯基本相同。 遍历：
以此图为例进行深度优先遍历 static void dfs(int[][] graph,int idx,boolean[]visit) { int len = graph.length; //访问过 if(visit[idx]) return; //访问该顶点 System.out.println("V"+idx); //标志顶点 visit[idx] = true; for(int i = 1;i < len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { //递归进行dfs遍历 dfs(graph, i, visit); } } }登录后复制遍历结果： V1 V2 V3 V4 V5 V6 V7 V8 V9 创建图的代码： public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i |
【本文地址】
今日新闻 |
推荐新闻 |