【数据结构与算法】图的深度与广度遍历

浅浅的花香味﹌ 2022-08-11 10:28 163阅读 0赞

图的深度遍历与广度遍历与二叉树的遍历类似，但是因为是图，需要有个数组存一下点是否被遍历过。

*  代码实现

/**
     * 源码名称：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();
    	}
    }