邻接矩阵的遍历

//无向图的邻接矩阵存储
public class UndirectedMatrixGraph {
    private ArrayList vertexList;//存储顶点的集合
    private int[][] edgeMatrix;//存储边的邻接矩阵
    private int numOfVertex;//顶点的个数
    private int numOfEdge;//边的个数
    private int size;//顶点的最大规模
    private boolean[] isVisited;//记录顶点是否被访问

    public UndirectedMatrixGraph() {
    }

    public UndirectedMatrixGraph(int size) {
        this.size = size;
        vertexList = new ArrayList(size);
        edgeMatrix = new int[size][size];
        numOfVertex = 0;
        numOfEdge = 0;
        isVisited = new boolean[numOfVertex];
    }

    public void DFS() {
        boolean[] visited = new boolean[numOfVertex];
        int i;
        for (i = 0; i < numOfVertex; i++) {
            if (!visited[i]) {
                DFS(visited, i);
            }
        }
    }

    public void DFS(boolean[] visited, int i) {
        int j;
        visited[i] = true;
        System.out.print(vertexList.get(i));
        for (j = 0; j < numOfVertex; j++) {// 无向图for (j = i+1; j < numOfVertex; j++)
            if (edgeMatrix[i][j] != 0 && !visited[j]) {
                DFS(visited, j);
            }
        }
    }

    public void BFS() {
        boolean[] visited = new boolean[numOfVertex];
        Queue<V> queue = new LinkedList<V>();
        for (int i = 0; i < numOfVertex; i++) {
            if (!visited[i]) {
                System.out.println(vertexList.get(i));
                visited[i] = true;
                queue.add(vertexList.get(i));
            }
            while (!queue.isEmpty()) {
                queue.remove();
                for (int j = 0; j < numOfVertex; j++) {
                    if (edgeMatrix[i][j] != 0 && !visited[j]) {
                        System.out.println(vertexList.get(j));
                        visited[j] = true;
                        queue.add(vertexList.get(j));
                    }
                }
            }
        }
    }
}


public class GraphDemo {
    public static void main(String[] args) {
        Graph graph = new UndirectedMatrixGraph<Character>(6);//邻接矩阵测试

        //添加顶点
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');

        //添加边
        graph.addEdge('A', 'B');
        graph.addEdge('A', 'D');
        graph.addEdge('B', 'C');
        graph.addEdge('B', 'E');
        graph.addEdge('C', 'D');
        graph.addEdge('C', 'F');
        graph.addEdge('D', 'F');
        graph.addEdge('E', 'F');

        graph.DFS();//深度优先遍历
        graph.BFS();//广度优先遍历
    }
}

邻接表的遍历

//无向图的邻接表存储
public class UndirectedLinkGraph<V> {

    class Vertex<V> {//内部类，存储顶点的信息
        V date;//顶点值
        LinkedList<Integer> adj;//顶点的每一个邻接顶点构成的邻接表，Integer为顶点在顶点数组中的下标

        //顶点的构造方法
        Vertex(V date) {
            this.date = date;
            adj = new LinkedList<Integer>();
        }
    }

    Vertex<V>[] vertexList;//由顶点组成的数组
    int numOfVertex;//顶点的数量
    int numOfEdge;//边的数量
    int size;//顶点的最大规模

    UndirectedLinkGraph() {

    }

    UndirectedLinkGraph(int size) {
        vertexList = new Vertex[size];
        numOfVertex = 0;
        numOfEdge = 0;
    }


    public void DFS() {
        boolean[] visited = new boolean[numOfVertex];
        for (int i = 0; i < numOfVertex; i++) {
            if (!visited[i]) {
                DFS(visited, i);
            }
        }
    }

    public void DFS(boolean[] visited, int i) {
        System.out.print(vertexList[i].date);
        visited[i] = true;
        for (int j = 0; j < vertexList[i].adj.size(); j++) {
            //i的邻接表中第j个元素，在顶点数组中的索引
            int x = vertexList[i].adj.get(j);
            if (!visited[x]) {
                DFS(visited, x);
            }
        }
    }

 
    public void BFS() {
        boolean[] visited = new boolean[numOfVertex];
        Queue<Vertex> queue = new LinkedList<Vertex>();
        for (int i = 0; i < numOfVertex; i++) {
            if (!visited[i]) {
                System.out.println(vertexList[i].date);
                visited[i] = true;
                queue.add(vertexList[i]);
            }
            while (!queue.isEmpty()) {
                queue.remove();
            }
            for (int j = 0; j < vertexList[i].adj.size(); j++) {
                int indext = vertexList[i].adj.get(j);
                if (!visited[indext]) {
                    System.out.println(vertexList[indext].date);
                    visited[indext]=true;
                    queue.add(vertexList[indext]);
                }
            }
        }
    }
}


public class GraphDemo {
    public static void main(String[] args) {

        Graph graph = new UndirectedLinkGraph<Character>(6);//邻接表测试

        //添加顶点
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');

        //添加边
        graph.addEdge('A', 'B');
        graph.addEdge('A', 'D');
        graph.addEdge('B', 'C');
        graph.addEdge('B', 'E');
        graph.addEdge('C', 'D');
        graph.addEdge('C', 'F');
        graph.addEdge('D', 'F');
        graph.addEdge('E', 'F');

        graph.DFS();//深度优先遍历
        graph.BFS();//广度优先遍历
    }
}