图的遍历(Java语言)

//邻接矩阵的深度优先搜索
public void dfs(int v) {
        System.out.print(getVertex(v) + " ");  //先输出此顶点
        marked[v] = true; //把遍历过的顶点标记为true
        for (int w = adj(v); w < vertexList.size(); w++) { //w下标对应的顶点是v下标对应顶点的邻接点
            if(edges[v][w] != 0 && !marked[w]) { //如果该顶点和它的邻接点之间可以连接并且该顶点的邻接点没有被遍历
                dfs(w); //对该顶点的邻接点进行深度优先搜索
            }
        }
    }

//邻接矩阵的广度优先搜索
    public void bfs(int i) {
        LinkedList<Integer> list = new LinkedList<Integer>(); //创建一个链表
        marked[i] = true; //从给定的顶点出发，先把该顶点标记为访问过
        list.addLast(i); //把该顶点对应的下标加入list中

        while (!list.isEmpty()) { //该链表不为空
            int v = list.removeFirst(); //定义一个变量v来存储从链表中取出的第一个下标元素
            System.out.print(getVertex(v) + " ");  //输出该元素对应的顶点
            for (int w = adj(v); w < vertexList.size(); w++) { //遍历以下标v为顶点的每一个邻接点的下标
                if(edges[v][w] != 0 && !marked[w]) { //如果该顶点和它的邻接点之间可以连接并且该顶点的邻接点没有被遍历
                    marked[w] = true; //把该顶点的邻接点标记为访问过
                    list.addLast(w); //把该顶点的邻接点加入链表的链尾
                }
            }
        }
    }

package com.graph;
import java.util.*;
public class Graph {
    ArrayList<String> vertexList; //存储顶点的集合
    int[][] edges; //存储图对应的邻接矩阵
    int numEdges; //表示边的条数
    boolean[] marked; //标记是否被遍历过
    public Graph(int n) {
        //初始化存储顶点的集合、初始化矩阵
        vertexList = new ArrayList<String>(n);
        edges = new int[n][n];
        marked = new boolean[n];
    }
    //找当前节点的邻接结点对应的下标w
    public int adj(int v) {
        for (int w = 0; w < vertexList.size(); w++) {
            if(edges[v][w] != 0) {
                return w;
            }
        }
        return -1;
    }
    /**
     * 深度优先搜索
     * @param v 传入要开始遍历的顶点的下标（从下标为v的顶点开始遍历）
     */
    public void dfs(int v) {
        System.out.print(getVertex(v) + " ");  //先输出此顶点
        marked[v] = true; //把遍历过的顶点标记为true
        for (int w = adj(v); w < vertexList.size(); w++) { //w下标对应的顶点是v下标对应顶点的邻接点
            if(edges[v][w] != 0 && !marked[w]) { //如果该顶点和它的邻接点之间可以连接并且该顶点的邻接点没有被遍历
                dfs(w); //对该顶点的邻接点进行深度优先搜索
            }
        }
    }
    //广度优先搜索
    public void bfs(int i) {
        LinkedList<Integer> list = new LinkedList<Integer>(); //创建一个链表
        marked[i] = true; //从给定的顶点出发，先把该顶点标记为访问过
        list.addLast(i); //把该顶点对应的下标加入list中

        while (!list.isEmpty()) { //该链表不为空
            int v = list.removeFirst(); //定义一个变量v来存储从链表中取出的第一个下标元素
            System.out.print(getVertex(v) + " ");  //输出该元素对应的顶点
            for (int w = adj(v); w < vertexList.size(); w++) { //遍历以下标v为顶点的每一个邻接点的下标
                if(edges[v][w] != 0 && !marked[w]) { //如果该顶点和它的邻接点之间可以连接并且该顶点的邻接点没有被遍历
                    marked[w] = true; //把该顶点的邻接点标记为访问过
                    list.addLast(w); //把该顶点的邻接点加入链表的链尾
                }
            }
        }
    }
    //对dfs进行方法重载，遍历所有顶点(防止漏掉没有任何指向的顶点)
    public void dfs() {
        for (int i = 0; i < vertexList.size(); i++) {
            if(!marked[i]) {
                dfs(i);
            }
        }
    }
    对bfs进行方法重载，遍历所有顶点(防止漏掉没有任何指向的顶点)
    public void bfs() {
        marked = new boolean[vertexList.size()]; //再调用了dfs之后若调用bfs，须重新new个marked数组，否则经过dfs之后marked数组的值都为true
        for (int i = 0; i < vertexList.size(); i++) {
            if(!marked[i]) {
                bfs(i);
            }
        }
    }
    //返回给定下标的顶点值
    public String getVertex(int index) {
        return vertexList.get(index);
    }
    //返回顶点的个数
    public int numVertex() {
        return vertexList.size();
    }
    //返回边的条数
    public int numEdges() {
        return numEdges;
    }
    //显示图对应的矩阵
    public void showGraph() {
        for(int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }
    //返回v1和v2的权值
    public int weight(int v1, int v2) {
        return edges[v1][v2];
    }
    //插入结点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }
    //添加边

    /**
     *
     * @param v1 表示第一个顶点对应的下标
     * @param v2 表示第二个顶点对应的下标
     * @param w 表示它们两个顶点之间的关系。(w值为1表示两个顶点能够直接连接，为0表示不能直接连接)
     */
    public void insertEdge(int v1, int v2, int w) {
        edges[v1][v2] = w;
        edges[v2][v1] = w;
        numEdges++;
    }
}

package com.graph;

public class GraphDemo {
    public static void main(String[] args) {
        String[] vertexes = {"A","B","C","D","E","F","G","H","I"};
        Graph graph = new Graph(vertexes.length);
        //添加顶点
        for(String vertex : vertexes) {
            graph.insertVertex(vertex);
        }
        //添加边
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,5,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,6,1);
        graph.insertEdge(1,8,1);
        graph.insertEdge(2,3,1);
        graph.insertEdge(2,8,1);
        graph.insertEdge(3,8,1);
        graph.insertEdge(3,4,1);
        graph.insertEdge(3,6,1);
        graph.insertEdge(3,7,1);
        graph.insertEdge(4,5,1);
        graph.insertEdge(4,7,1);
        graph.insertEdge(5,6,1);
        graph.insertEdge(6,7,1);
        graph.showGraph();
        System.out.println("DFS:");
        graph.dfs();
        System.out.println();
        System.out.println("BFS:");
        graph.bfs();
    }
}