首页 > 代码库 > 【数据结构与算法】图的深度与广度遍历
【数据结构与算法】图的深度与广度遍历
图的深度遍历与广度遍历与二叉树的遍历类似,但是因为是图,需要有个数组存一下点是否被遍历过。
- 代码实现
/** * 源码名称:GraphIterateMatrix.java * 日期:2014-08-25 * 程序功能:图的深度与广度遍历 * 版权:CopyRight@A2BGeek * 作者:A2BGeek */ import java.util.LinkedList; import java.util.Queue; public class GraphIterateMatrix { private String[] Vnode = { "A", "B", "C", "D", "E", "F", "G", "H", "I" }; private int[][] Edge = { { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 0, 1 }, { 0, 0, 1, 0, 1, 0, 1, 1, 1 }, { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, { 1, 0, 0, 0, 1, 0, 1, 0, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, { 0, 1, 1, 1, 0, 0, 0, 0, 0 } }; private int nodeNum = Vnode.length; private boolean[] flag; private Queue<Integer> queue;// for bfs public void Dfs() { flag = new boolean[nodeNum]; for (int i = 0; i < nodeNum; i++) { if (flag[i] == false) { DfsRecursive(i); } } } private void DfsRecursive(int j) { flag[j] = true; System.out.print(Vnode[j] + " "); for (int k = 0; k < nodeNum; k++) { if (Edge[j][k] == 1 && flag[k] == false) { DfsRecursive(k); } } } public void Bfs() { flag = new boolean[nodeNum]; for (int i = 0; i < nodeNum; i++) { if (flag[i] == false) { BfsIterate(i); } } } private void BfsIterate(int i) { flag[i] = true; System.out.print(Vnode[i] + " "); queue = new LinkedList<Integer>(); queue.offer(i); while (!queue.isEmpty()) { int j = queue.poll(); for (int k = 0; k < nodeNum; k++) { if (Edge[j][k] == 1 && flag[k] == false) { flag[k] = true; System.out.print(Vnode[k] + " "); queue.offer(k); } } } } public static void main(String[] args) { GraphIterateMatrix graphIterateMatrix = new GraphIterateMatrix(); graphIterateMatrix.Dfs(); System.out.println(); graphIterateMatrix.Bfs(); } }
【数据结构与算法】图的深度与广度遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。