数据结构之图算法

深度优先遍历(DFS) （递归实现）

没有碰到重复顶点的情况下，就一直往下走，直到回到头节点，然后再回溯到没有遍历过的节点。
起初，从A开始为：A,B,G,H,A
因为A遍历过，所以一直回溯到B然后走F
再回溯到B走E,D,J,A然后C
再回溯到A再I
最终，深度优先遍历的顺序为：a b g h f e d j c i

广度优先遍历(BFS) （列队实现）

起初，把点A放入队列中，A被遍历。
接着把队首元素A出队，把A的下一层的顶点B,I,J,C,H移进队列。
队首元素B出队，B的下一层顶点E,F,G相继入队。
队首元素I出队，I的下一层顶点A,因为A已经遍历所以I直接出队。
依此类推。

最终，广度优先遍历的顺序即入队列（或出队列）的顺序：a b h c j i g f e d

java代码

package com.cy.数据结构算法.graph;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * BFS 遍历 DFS遍历
 *
 * @author cy
 * @date 2019/10/31
 */
public class GraphDfs {
    public Integer numVertex;
    public Integer numEdge;
    public VertexNode[] vertexNodes;
    public boolean[] vst;
    public Integer[] pre;
    public boolean ringFound;
    public static Integer firstNode;
    /*public Integer[] numLayerNode;
    public Integer[] nodeLyaer;*/

    public GraphDfs(VertexNode[] vertexNodes) {
        this.numEdge = 0;
        this.numVertex = vertexNodes.length;
        this.vertexNodes = vertexNodes;
        vst = new boolean[numVertex];
        pre = new Integer[numVertex];

        for (int i = 0; i < pre.length; i++) {
            pre[i] = -1;
        }
    }

    /**
     * 插入节点
     * @param start
     * @param end
     */
    public void insertEdge(Integer start, Integer end) {
        VertexNode vertexNode = vertexNodes[start];
        EdgeNode edgeNode = new EdgeNode(end, null);

        EdgeNode firstEdgeNode = vertexNode.firstEdge;
        if (firstEdgeNode == null) {
            vertexNode.firstEdge = edgeNode;
        } else {
            edgeNode.next = firstEdgeNode;
            vertexNode.firstEdge = edgeNode;
        }
    }

    /**
     * dfs遍历
     * @param root
     */
    public void dfs(int root) {
        VertexNode vertexNode = this.vertexNodes[root];
        vst[root] = true;
        System.out.print(vertexNode.data + " ");

        EdgeNode currentEdgeNode = vertexNode.firstEdge;

        while (currentEdgeNode != null) {
            int vertexNodeIndex = currentEdgeNode.adjvex;
            if (vst[vertexNodeIndex] == false) {
                dfs(vertexNodeIndex);
            }
            currentEdgeNode = currentEdgeNode.next;
        }
    }

    /**
     * bfs遍历
     * @param root
     */
    public void bfs(int root) throws InterruptedException {

        Queue<Integer> queue = new LinkedBlockingQueue<>();
        ((LinkedBlockingQueue<Integer>) queue).put(root);
        while (queue.size()!=0)
        {
            int node = queue.poll();
            if(!vst[node])
            {
                VertexNode vertexNode = this.vertexNodes[node];
                vst[node] = true;
                System.out.print(vertexNode.data + " ");

                EdgeNode currentEdgeNode = vertexNode.firstEdge;

                    while (currentEdgeNode != null) {
                        node=currentEdgeNode.adjvex;
                        if(!vst[node]) {
                        ((LinkedBlockingQueue<Integer>) queue).put(node);

                    } currentEdgeNode = currentEdgeNode.next;
                }
            }

        }
    }



 

    /**
     * 打印邻接表
     * @param graph
     */
    public static void printTable(GraphDfs graph,VertexNode[] vertexNodes) {
        //   打印邻接表结构
        for (int i = 0; i < graph.numVertex; i++) {
            VertexNode vertexNode = graph.vertexNodes[i];
            EdgeNode firstEdge = vertexNode.firstEdge;

            EdgeNode currentEdge = firstEdge;
            System.out.print(vertexNode.data + ":");
            while (currentEdge != null) {
                int vertexNodeIndex = currentEdge.adjvex;
                System.out.print("->" + vertexNodes[vertexNodeIndex].data);
                currentEdge = currentEdge.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        VertexNode[] vertexNodes = {
                new VertexNode(0, "a", null),
                new VertexNode(1, "b", null),
                new VertexNode(2, "c", null),
                new VertexNode(3, "d", null),
                new VertexNode(4, "e", null),
                new VertexNode(5, "f", null),
                new VertexNode(6, "g", null),
                new VertexNode(7, "h", null),
                new VertexNode(8, "i", null),
                new VertexNode(9, "j", null),

        };

        GraphDfs graph = new GraphDfs(vertexNodes);

        //初始边数11
        graph.insertEdge(0, 8);
        graph.insertEdge(0, 9);
        graph.insertEdge(0, 2);
        graph.insertEdge(0, 7);
        graph.insertEdge(0, 1);
        graph.insertEdge(1, 4);
        graph.insertEdge(1, 5);
        graph.insertEdge(1, 6);
        graph.insertEdge(6, 7);
        graph.insertEdge(3, 9);
        graph.insertEdge(3, 4);

        //无向图对称
        graph.insertEdge(8, 0);
        graph.insertEdge(9, 0);
        graph.insertEdge(2, 0);
        graph.insertEdge(7, 0);
        graph.insertEdge(1, 0);
        graph.insertEdge(4, 1);
        graph.insertEdge(5, 1);
        graph.insertEdge(6, 1);
        graph.insertEdge(7, 6);
        graph.insertEdge(9, 3);
        graph.insertEdge(4, 3);

        //过滤边数为1的节点
        for(int i=0;i<vertexNodes.length;i++)
        {
            if(vertexNodes[i].firstEdge.next==null)
            {
                VertexNode vertexNode = vertexNodes[i];
                vertexNode.firstEdge=null;
                vertexNodes[i]=vertexNode;
            }
        }
        firstNode = 0;
        //graph.findRing(firstNode,1);
        //graph.dfs(0);
        graph.bfs(0);
        //printTable(graph,vertexNodes);

    }
}

package com.cy.数据结构算法.graph;

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
/**
 * 边节点
 *
 * @author cy
 * @date 2019/10/26
 */
public class EdgeNode {
    /**
     * 每条边的下一结点
     * */
    public Integer adjvex;
    /**
     * 下一个边结点
     * */
    public EdgeNode next;
}

}

package com.cy.数据结构算法.graph;

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
/**
 * 表头节点
 *
 * @author cy
 * @date 2019/10/26
 */
public class VertexNode {
    /**
     * 结点序号
     * */
    public Integer id;
    /**
     * 结点信息
     * */
    public String data;
    /**
     * 第一条边
     * */
    public EdgeNode firstEdge;

}