图的遍历(邻接矩阵)

		

[java]  
package com.wzs;  
  
import java.util.LinkedList;  
import java.util.Queue;  
  
// 图的遍历  
public class Graph {  
    // 邻接矩阵存储图  
    // --A B C D E F G H I  
    // A 0 1 0 0 0 1 1 0 0  
    // B 1 0 1 0 0 0 1 0 1  
    // C 0 1 0 1 0 0 0 0 1  
    // D 0 0 1 0 1 0 1 1 1  
    // E 0 0 0 1 0 1 0 1 0  
    // F 1 0 0 0 1 0 1 0 0  
    // G 0 1 0 1 0 1 0 1 0  
    // H 0 0 0 1 1 0 1 0 0  
    // I 0 1 1 1 0 0 0 0 0  
  
    // 顶点数  
    private int number = 9;  
    // 记录顶点是否被访问  
    private boolean[] flag;  
    // 顶点  
    private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" };  
    // 边  
    private int[][] edges = {   
            { 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 }   
            };  
  
    // 图的深度遍历操作(递归)  
    void DFSTraverse() {  
        flag = new boolean[number];  
        for (int i = 0; i < number; i++) {  
            if (flag[i] == false) {// 当前顶点没有被访问  
                DFS(i);  
            }  
        }  
    }  
  
    // 图的深度优先递归算法  
    void DFS(int i) {  
        flag[i] = true;// 第i个顶点被访问  
        System.out.print(vertexs[i] + " ");  
        for (int j = 0; j < number; j++) {  
            if (flag[j] == false && edges[i][j] == 1) {  
                DFS(j);  
            }  
        }  
    }  
  
    // 图的广度遍历操作  
    void BFSTraverse() {  
        flag = new boolean[number];  
        Queue<Integer> queue = new LinkedList<Integer>();  
        for (int i = 0; i < number; i++) {  
            if (flag[i] == false) {  
                flag[i] = true;  
                System.out.print(vertexs[i] + " ");  
                queue.add(i);  
                while (!queue.isEmpty()) {  
                    int j = queue.poll();  
                    for (int k = 0; k < number; k++) {  
                        if (edges[j][k] == 1 && flag[k] == false) {  
                            flag[k] = true;  
                            System.out.print(vertexs[k] + " ");  
                            queue.add(k);  
                        }  
                    }  
                }  
            }  
        }  
    }  
  
    // 测试  
    public static void main(String[] args) {  
        Graph graph = new Graph();  
        System.out.println("图的深度遍历操作(递归):");  
        graph.DFSTraverse();  
        System.out.println("\n-------------");  
        System.out.println("图的广度遍历操作:");  
        graph.BFSTraverse();  
    }  
}  
输出结果：
[java]  
图的深度遍历操作(递归):  
A B C D E F G H I   
-------------  
图的广度遍历操作:  
A B F G C I E D H   
 
						
		
	

补充：软件开发 , Java ,

上一个：静态变量错误 java.lang.Error: Unresolved compilation problem:
下一个：[Maven Essentials] 坐标和依赖