image.png

本文所使用的所有邻接表以及邻接矩阵定义均在之前博客，这里不再赘述

一、深度优先遍历DFS（Depth-first search）

1.1.1 DFS递归邻接表实现原理

图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v,并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点w，并访问它:再选取与w邻接的未被访问的任一顶点并访问，以此重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个并重复上述访问过程，直至图中所有顶点都被访问过为止。

   /**
     * @param graph 邻接表
     * @param i     开始节点下标
     */
    public static void dfsRecursion(AGraph graph, int i) {
        ArcNode p;
        visited[i] = 1;
        dfsToString(graph, i);
        p = graph.adjList[i].firstArc;
        while (p != null) {
            //如果没有访问过，则递归
            if (visited[p.adjvex] == 0) {
                dfsRecursion(graph, p.adjvex);
            }
            p = p.nextArc;
        }
    }

    public static void dfsToString(AGraph graph, int i){
        System.out.print(graph.adjList[i].name + " ");
    }

---

1.1.2 DFS递归邻接矩阵实现原理

使用邻接矩阵实现DFS递归思路上和邻接表基本是一样的.不同的就是每次检索所有节点与当前节点是否有连接

/**
     * @param graph
     * @param i
     */
    public static void dfsRecursionMatrix(MGraph graph, int i) {
        visited[i] = 1;
        System.out.print(graph.vex[i].no + " ");
        for (int j = 0; j < graph.n; j++) {
            //因为是无权无向图，所以权值默认为1
            if(graph.edges[i][j] == 1 && visited[j] == 0){
                dfsRecursionMatrix(graph,j);
            }
        }
    }

---

1.2.1 DFS非递归邻接表实现

关于非递归的DFS实现，查阅了20多篇博客，发现网上大部分的邻接表实现非递归都是有问题的，终于在一篇博客中得到正解。
https://www.cnblogs.com/exciting/p/10102661.html
这里介绍下简单思路：

1. 取第一个节点信息入栈
2. 若栈不为空，取栈顶元素ArcNode p
3. 遍历边节点p,如果存在visited[p.adjvex] == 0,即没用访问过，那么该元素入栈，将visited[p.adjvex] 置为1，同时p等于栈顶节点（也就是刚入栈元素）的firstArc
4. 如果p已经访问过了，那么p = p.nextArc
5. 如果遍历到p = null时，跳出内循环，将栈顶元素出栈（关键）

最后一步是关键，网上看到的版本大多是元素不出栈，内层循环入栈之后 break,或者是定义外循环次数为n次，我都试过，是不正确的。
拿本文例子按上述步骤解释：假设从1节点入栈，p=4节点，4节点没有被访问过，4节点入栈，之后无论跳出循环还是其他操作，p = 4节点的firstArc,即为1，1已经访问过，所以p = p.nextArc = null。结束循环，p取栈顶元素4的firstArc,依然是1。陷入死循环。可能解释不是很清楚，百度搜一下非递归代码看下应该就知道了。
内循环结束如果出栈的话，栈顶4出栈，栈顶变为1,1访问下一节点4， visited[4]=1，跳过访问下一节点，正解(节点4已经输出值了，如果需要保存出栈的顺序节点，那么需要额外定义一个集合来存储)
下面给出代码：

 /**
     * @param graph 邻接表
     * @param i     起点下标
     */
    public static void dfsNoRecursion(AGraph graph, int i) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int[] visited = new int[graph.verNum];
        visited[i] = 1;
        stack.push(i);

        System.out.print(graph.adjList[i].name + " ");
        ArcNode p;
        while (!stack.isEmpty()) {
            p = graph.adjList[stack.getFirst()].firstArc;
            while (p != null) {
                if (visited[p.adjvex] == 0) {
                    visited[p.adjvex] = 1;
                    System.out.print(graph.adjList[p.adjvex].name + " ");
                    stack.push(p.adjvex);
                    p = graph.adjList[p.adjvex].firstArc;
                } else {
                    p = p.nextArc;
                }
            }
            //p=null表明栈顶元素相邻节点都已经遍历过了
            if (p == null) {
                stack.pop();
            }
        }
    }

1.2.2 DFS非递归邻接矩阵实现

非递归使用邻接矩阵和非递归使用邻接表区别仅仅在于遍历的方式。
邻接表是取栈顶的firstArc，然后next向下遍历直到找到没有遍历过的节点，然后让p等于新的栈顶的firstArc。
邻接矩阵是取栈顶节点，然后在邻接矩阵中遍历栈顶节点相邻的元素，如果存在，visited[j] = 1,入栈，跳出循环.更新k为最新的栈顶节点

    /**
     * @param graph 邻接矩阵
     * @param i     起点下标
     */
    public static void dfsNoRecursionMatrix(MGraph graph, int i) {
        int[] visited = new int[graph.n];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(i);
        System.out.print(stack.getFirst() + " ");
        visited[i] = 1;
        while (!stack.isEmpty()) {
            int k = stack.getFirst();
            int j = 0;
            for(j = 0; j < graph.n; j++) {
                if(graph.edges[k][j] == 1 && visited[j] == 0) {
                    stack.push(j);
                    visited[j] = 1;
                    System.out.print(stack.getFirst() + " ");
                    break;
                }
            }
            //如果j = n,与j相邻的节点都访问结束了
            if (j == graph.n) {
                stack.pop();
            }
        }
    }

---

二、广度优先遍历(Breadth-First-Search)

广度优先遍历这里通过邻接表非递归的方式实现，如果我们熟悉二叉树的层次遍历，那么广度优先遍历思路基本一致。
我们利用队列，首节点入队，相邻节点依次入队，当全部相邻节点入队之后，出队遍历下一层。
文章可能输出方式不是特别规范，因为下标和节点信息都是一致的，即下标i, graph.adjList[k].name , 以及ArcNode的adjvex属性表示的都是一样的。

   /**
     * 
     * @param graph 邻接表
     * @param i 起始下标
     */
    public static void bfsNoRecursion(AGraph graph, int i) {
        int[] visited = new int[graph.verNum];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        //顶点入队
        queue.add(i);
        visited[i] = 1;
        while (!queue.isEmpty()) {
            //顶点出队
            int k = queue.poll();
            System.out.print(graph.adjList[k].name + " ");
            ArcNode p = graph.adjList[k].firstArc;
            while (p != null) {
                //没有被访问过的节点入队
                if (visited[p.adjvex] == 0) {
                    queue.add(p.adjvex);
                    visited[p.adjvex] = 1;
                }
                p = p.nextArc;
            }
        }
    }

---

三、非连通图的DFS,BFS

上述的操作都是针对于连通图来讲的。对于非连通图，只需要将遍历函数放到一个循环中，循环检测图中的每一个顶点，如果当前节点没有被访问，则调用上述函数从这个顶点遍历

    public void noConnectDfs(AGraph graph){
        for(int i = 0; i < graph.verNum) {
            if (visited[i] == 0) {
                dfsNoRecursion(graph,i);
            }
        }
    }

    public void noConnectBFS(AGraph graph){
        for(int i = 0; i < graph.verNum) {
            if (visited[i] == 0) {
                bfsNoRecursion(graph,i);
            }
        }
    }

---

四、测试代码

以上就是递归非递归的实现方法，可能类的成员变量名称和教材略有不同，但表示意思都是一样的。关于邻接表和邻接矩阵的创建，请阅读上一篇文章。
下面给出测试代码：

 public static void main(String[] args) {
        //初始化邻接矩阵,6个节点
        int n = 6;
        EdgeElement[] elements = new EdgeElement[6];
        elements[0] = new EdgeElement(0, 1);
        elements[1] = new EdgeElement(0, 2);
        elements[2] = new EdgeElement(0, 3);
        elements[3] = new EdgeElement(1, 2);
        elements[4] = new EdgeElement(1, 4);
        elements[5] = new EdgeElement(4, 5);

        String[] names = {"0", "1", "2", "3", "4", "5"};

        MGraph mGraph = new MGraph(elements, names, n, GTypeConstant.NoDirectionNoWeight);
        mGraph.graphToString();

        //邻接表形式

        AGraph aGraph = new AGraph(6, 6, names, elements, GTypeConstant.NoDirectionNoWeight);
        aGraph.graphToString();


        //初始化visited数组
        DfsBfs.visited = new int[10];
        System.out.println("执行DFS递归(邻接表)，初始节点为1");
        dfsRecursion(aGraph, 1);
        visited = new int[10];
        System.out.println();
        System.out.println("执行DFS递归(邻接矩阵)，初始节点为1");
        dfsRecursionMatrix(mGraph, 1);
        System.out.println();
        System.out.println("执行DFS非递归(邻接表)，初始节点为1");
        dfsNoRecursion(aGraph, 1);
        System.out.println();
        System.out.println("执行DFS非递归(邻接矩阵)，初始节点为1");
        dfsNoRecursionMatrix(mGraph, 1);
        System.out.println();
        System.out.println("执行BFS非递归(邻接矩阵)，初始节点为1");
        bfsNoRecursion(aGraph,1);
    }

输出结果为：

0  1  1  1  0  0  
1  0  1  0  1  0  
1  1  0  0  0  0  
1  0  0  0  0  0  
0  1  0  0  0  1  
0  0  0  0  1  0  
输出邻接表存储情况：
0->3->2->1
1->4->2->0
2->1->0
3->0
4->5->1
5->4
执行DFS递归(邻接表)，初始节点为1
1 4 5 2 0 3 
执行DFS递归(邻接矩阵)，初始节点为1
1 0 2 3 4 5 
执行DFS非递归(邻接表)，初始节点为1
1 4 5 2 0 3 
执行DFS非递归(邻接矩阵)，初始节点为1
1 0 2 3 4 5 
执行BFS非递归(邻接矩阵)，初始节点为1
1 4 2 0 5 3