Java深度优先遍历和广度优先遍历邻接表算法-数据结构和算法-07-图

 自行了解邻接矩阵和邻接表的图的存储，其实一个是顺序存储一个是链表存储，大概的含义。。

图

解析图

代码

package com.my.data.structure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 邻接表深度优先和官渡优先遍历
 */
public class GraphTest02 {

    public List<VertexNode> vertexNodeList = new ArrayList<VertexNode>();
    public int numVertexes = 8;

    class EdgeNode {
        int adjVex;     //邻接点城，存储该顶点对应的下标
        int weight;     //存储权值
        EdgeNode next;  //链城，指向下一个邻接点

        EdgeNode(int a, int w, EdgeNode n) {
            this.adjVex = a;
            this.weight = w;
            this.next = n;
        }

        public void addNext(EdgeNode n) {
            this.next = n;
        }
    }

    class VertexNode {
        String v;               //存储顶点信息
        EdgeNode firstEdge;     //边表头指针

        VertexNode(String val, EdgeNode edgeNode) {
            v = val;
            firstEdge = edgeNode;
        }

        public void addFirstEdge(EdgeNode n) {
            this.firstEdge = n;
        }
    }

    public void createAlGraph() {
        //初始化顶点 V1-V8
        for (int i = 0; i < numVertexes; i++) {
            vertexNodeList.add(new VertexNode("V" + (i + 1), null));
        }

        /** 邻接矩阵存储
         *    V1 V2 V3 V4 V5 V6 V7 V8
         * V1 0  1  1  0  0  0  0  0
         * V2 1  0  0  1  1  0  0  0
         * V3 1  0  0  0  0  1  1  0
         * V4 0  1  0  0  0  0  0  1
         * V5 0  1  0  0  0  0  0  1
         * V6 0  0  1  0  0  0  1  0
         * V7 0  0  1  0  0  1  0  0
         * V8 0  0  0  1  1  0  0  0
         */
        //边处理
        for (int j = 0; j < numVertexes; j++) {
            vertexNodeList.get(j).addFirstEdge(new EdgeNode(j, 0, null));
            if (j == 0) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(2, 0, null)));
            if (j == 1)
                vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(0, 0, new EdgeNode(3, 0, new EdgeNode(4, 0, null))));
            if (j == 2)
                vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(0, 0, new EdgeNode(5, 0, new EdgeNode(6, 0, null))));
            if (j == 3) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(7, 0, null)));
            if (j == 4) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(1, 0, new EdgeNode(7, 0, null)));
            if (j == 5) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(2, 0, new EdgeNode(6, 0, null)));
            if (j == 6) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(2, 0, new EdgeNode(5, 0, null)));
            if (j == 7) vertexNodeList.get(j).firstEdge.addNext(new EdgeNode(3, 0, new EdgeNode(4, 0, null)));
        }
    }

    boolean[] dfsVisit = new boolean[numVertexes];
    boolean[] bfsVisit = new boolean[numVertexes];

    /**
     * 邻接表深度优先遍历
     *
     * @param idx
     */
    public void dfs(int idx) {
        System.out.print(vertexNodeList.get(idx).v + " ");
        dfsVisit[idx] = true;

        Queue<EdgeNode> queue = new LinkedList<>();
        if(vertexNodeList.get(idx).firstEdge.next!=null)
            queue.add(vertexNodeList.get(idx).firstEdge.next);
        while (!queue.isEmpty()){
            EdgeNode cur = queue.poll();
            if(!dfsVisit[cur.adjVex]) {
                dfs(cur.adjVex);
            }else {
                if(cur.next != null) queue.add(cur.next);
            }
        }
    }

    /**
     * 邻接表广度优先遍历
     *
     * @param idx
     */
    public void bfs(int idx) {
        if(!bfsVisit[idx]) {
            System.out.print(vertexNodeList.get(idx).v + " ");
            bfsVisit[idx] = true;
        }

        Queue<EdgeNode> queue = new LinkedList<>();
        if(vertexNodeList.get(idx).firstEdge.next!=null)
            queue.add(vertexNodeList.get(idx).firstEdge.next);
        while (!queue.isEmpty()){
            EdgeNode cur = queue.poll();
            if(!bfsVisit[cur.adjVex]) {
                System.out.print(vertexNodeList.get(cur.adjVex).v + " ");
                bfsVisit[cur.adjVex] = true;
            }
            if(cur.next != null) queue.add(cur.next);
        }
    }

    public static void main(String[] args) {
        GraphTest02 graphTest02 = new GraphTest02();
        graphTest02.createAlGraph();
        System.out.println("邻接表深度优先遍历");
        for (int i = 0; i < graphTest02.numVertexes; i++) {
            if(!graphTest02.dfsVisit[i]) graphTest02.dfs(i);
        }
        System.out.println();
        System.out.println("邻接表广度优先遍历");
        for (int i = 0; i < graphTest02.numVertexes; i++) {
            graphTest02.bfs(i);
        }
    }
}

• 结果

邻接表深度优先遍历
V1 V2 V4 V8 V5 V3 V6 V7 
邻接表广度优先遍历
V1 V2 V3 V4 V5 V6 V7 V8