/**
 * 無向圖鄰接鏈表簡單實現(xiàn)
 * {@link UndirectedAdjacencyList#UndirectedAdjacencyList(E[], E[][])}  構(gòu)建無向圖
 * {@link UndirectedAdjacencyList#DFS()}  深度優(yōu)先遍歷無向圖
 * {@link UndirectedAdjacencyList#BFS()}  廣度優(yōu)先遍歷無向圖
 * {@link UndirectedAdjacencyList#toString()} ()}  輸出無向圖
 *
 * @author lx
 */
public class UndirectedAdjacencyList<E> {
    /**
     * 頂點(diǎn)類
     *
     * @param <E>
     */
    private class Node<E> {
        /**
         * 頂點(diǎn)信息
         */
        E data;
        /**
         * 指向第一條依附該頂點(diǎn)的邊
         */
        LNode firstEdge;

        public Node(E data, LNode firstEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
        }
    }

    /**
     * 邊表節(jié)點(diǎn)類
     */
    private class LNode {
        /**
         * 該邊所指向的頂點(diǎn)的索引位置
         */
        int vertex;
        /**
         * 指向下一條邊的指針
         */
        LNode nextEdge;
    }

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Node<E>[] vertexs;

    /**
     * 創(chuàng)建圖
     *
     * @param vexs  頂點(diǎn)數(shù)組
     * @param edges 邊二維數(shù)組
     */
    public UndirectedAdjacencyList(E[] vexs, E[][] edges) {
        /*初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)*/
        vertexs = new Node[vexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            vertexs[i] = new Node<>(vexs[i], null);
        }
        /*初始化邊表,并添加邊節(jié)點(diǎn)到邊表尾部,即采用尾插法*/
        for (E[] edge : edges) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
            int p1 = getPosition(edge[0]);
            int p2 = getPosition(edge[1]);
            /*這里需要相互添加邊節(jié)點(diǎn),無向圖可以看作相互可達(dá)的有向圖*/
            // 初始化lnode1邊節(jié)點(diǎn)
            LNode lnode1 = new LNode();
            lnode1.vertex = p2;
            // 將LNode鏈接到"p1所在鏈表的末尾"
            if (vertexs[p1].firstEdge == null) {
                vertexs[p1].firstEdge = lnode1;
            } else {
                linkLast(vertexs[p1].firstEdge, lnode1);
            }
            // 初始化lnode2邊節(jié)點(diǎn)
            LNode lnode2 = new LNode();
            lnode2.vertex = p1;
            // 將lnode2鏈接到"p2所在鏈表的末尾"
            if (vertexs[p2].firstEdge == null) {
                vertexs[p2].firstEdge = lnode2;
            } else {
                linkLast(vertexs[p2].firstEdge, lnode2);
            }
        }
    }

    /**
     * 獲取某條邊的某個頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
     *
     * @param e 頂點(diǎn)的值
     * @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].data == e) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 將lnode節(jié)點(diǎn)鏈接到邊表的最后,采用尾插法
     *
     * @param first 邊表頭結(jié)點(diǎn)
     * @param node  將要添加的節(jié)點(diǎn)
     */
    private void linkLast(LNode first, LNode node) {
        while (true) {
            if (first.vertex == node.vertex) {
                return;
            }
            if (first.nextEdge == null) {
                break;
            }
            first = first.nextEdge;
        }
        first.nextEdge = node;
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引標(biāo)記為true ,表示已經(jīng)訪問了
        visited[i] = true;
        System.out.print(vertexs[i].data + " ");
        //獲取該頂點(diǎn)的邊表頭結(jié)點(diǎn)
        LNode node = vertexs[i].firstEdge;
        //循環(huán)遍歷該頂點(diǎn)的鄰接點(diǎn),采用同樣的方式遞歸搜索
        while (node != null) {
            if (!visited[node.vertex]) {
                DFS(node.vertex, visited);
            }
            node = node.nextEdge;
        }
    }

    /**
     * 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        /*循環(huán)搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果對應(yīng)索引的頂點(diǎn)的訪問標(biāo)記為false,則搜索該頂點(diǎn)
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到這一步,說明頂點(diǎn)訪問標(biāo)記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/
        System.out.println();
    }

    /**
     * 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            //如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判斷隊列是否有值,有就開始遍歷
            if (!indexLinkedList.isEmpty()) {
                //出隊列
                Integer j = indexLinkedList.poll();
                LNode node = vertexs[j].firstEdge;
                while (node != null) {
                    int k = node.vertex;
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k].data + " ");
                        //繼續(xù)入隊列
                        indexLinkedList.add(k);
                    }
                    node = node.nextEdge;
                }
            }
        }
        System.out.print("\n");
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
            LNode node = vertexs[i].firstEdge;
            while (node != null) {
                stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
                node = node.nextEdge;
                if (node != null) {
                    stringBuilder.append("->");
                } else {
                    break;
                }
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        //頂點(diǎn)數(shù)組 添加的先后順序?qū)τ诒闅v結(jié)果有影響
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊二維數(shù)組 添加的先后順序?qū)τ诒闅v結(jié)果有影響
        Character[][] edges = {
                {'A', 'C'},
                //對于無向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會重復(fù)添加
                {'A', 'D'},
                {'A', 'D'},
                {'D', 'A'},

                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'E', 'B'},
                {'D', 'B'},
                {'F', 'G'}};
        //構(gòu)建圖
        UndirectedAdjacencyList<Character> undirectedAdjacencyList = new UndirectedAdjacencyList<>(vexs, edges);
        //輸出圖
        System.out.println(undirectedAdjacencyList);
        //深度優(yōu)先遍歷
        undirectedAdjacencyList.DFS();
        //廣度優(yōu)先遍歷
        undirectedAdjacencyList.BFS();
    }
}

/**
 * 有向圖鄰接鏈表簡單實現(xiàn)
 * {@link AdjacencyList#AdjacencyList(E[], E[][])}  構(gòu)建有向圖
 * {@link AdjacencyList#DFS()}  深度優(yōu)先遍歷有向圖
 * {@link AdjacencyList#BFS()}  廣度優(yōu)先遍歷有向圖
 * {@link AdjacencyList#toString()} ()}  輸出有向圖
 *
 * @author lx
 */
public class AdjacencyList<E> {
    /**
     * 頂點(diǎn)類
     *
     * @param <E>
     */
    private class Node<E> {
        /**
         * 頂點(diǎn)信息
         */
        E data;
        /**
         * 指向第一條依附該頂點(diǎn)的邊
         */
        LNode firstEdge;

        public Node(E data, LNode firstEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
        }
    }

    /**
     * 邊表節(jié)點(diǎn)類
     */
    private class LNode {
        /**
         * 該邊所指向的頂點(diǎn)的索引位置
         */
        int vertex;
        /**
         * 指向下一條弧的指針
         */
        LNode nextEdge;
    }

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Node<E>[] vertexs;

    /**
     * 創(chuàng)建圖
     *
     * @param vexs  頂點(diǎn)數(shù)組
     * @param edges 邊二維數(shù)組
     */
    public AdjacencyList(E[] vexs, E[][] edges) {
        /*初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)*/
        vertexs = new Node[vexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            vertexs[i] = new Node<>(vexs[i], null);
        }
        /*初始化邊表,并添加邊節(jié)點(diǎn)到邊表尾部,即采用尾插法*/
        for (E[] edge : edges) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
            int p1 = getPosition(edge[0]);
            int p2 = getPosition(edge[1]);
            // 初始化lnode1邊節(jié)點(diǎn) 即表示p1指向p2的邊
            LNode lnode1 = new LNode();
            lnode1.vertex = p2;
            // 將LNode鏈接到"p1所在鏈表的末尾"
            if (vertexs[p1].firstEdge == null) {
                vertexs[p1].firstEdge = lnode1;
            } else {
                linkLast(vertexs[p1].firstEdge, lnode1);
            }
        }
    }

    /**
     * 獲取某條邊的某個頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
     *
     * @param e 頂點(diǎn)的值
     * @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i].data == e) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 將lnode節(jié)點(diǎn)鏈接到邊表的最后,采用尾插法
     *
     * @param first 邊表頭結(jié)點(diǎn)
     * @param node  將要添加的節(jié)點(diǎn)
     */
    private void linkLast(LNode first, LNode node) {
        while (true) {
            if (first.vertex == node.vertex) {
                return;
            }
            if (first.nextEdge == null) {
                break;
            }
            first = first.nextEdge;
        }
        first.nextEdge = node;
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        //索引索引標(biāo)記為true ,表示已經(jīng)訪問了
        visited[i] = true;
        System.out.print(vertexs[i].data + " ");
        //獲取該頂點(diǎn)的邊表頭結(jié)點(diǎn)
        LNode node = vertexs[i].firstEdge;
        //循環(huán)遍歷該頂點(diǎn)的鄰接點(diǎn),采用同樣的方式遞歸搜索
        while (node != null) {
            if (!visited[node.vertex]) {
                DFS(node.vertex, visited);
            }
            node = node.nextEdge;
        }
    }

    /**
     * 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        /*循環(huán)搜索*/
        for (int i = 0; i < vertexs.length; i++) {
            //如果對應(yīng)索引的頂點(diǎn)的訪問標(biāo)記為false,則搜索該頂點(diǎn)
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        /*走到這一步,說明頂點(diǎn)訪問標(biāo)記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/
        System.out.println();
    }


    /**
     * 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
     * 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            //如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i].data + " ");
                indexLinkedList.add(i);
            }
            //判斷隊列是否有值,有就開始遍歷
            if (!indexLinkedList.isEmpty()) {
                //出隊列
                Integer j = indexLinkedList.poll();
                LNode node = vertexs[j].firstEdge;
                while (node != null) {
                    int k = node.vertex;
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k].data + " ");
                        //繼續(xù)入隊列
                        indexLinkedList.add(k);
                    }
                    node = node.nextEdge;
                }
            }
        }
        System.out.println("\n");
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
            LNode node = vertexs[i].firstEdge;
            while (node != null) {
                stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
                node = node.nextEdge;
                if (node != null) {
                    stringBuilder.append("->");
                } else {
                    break;
                }
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        //頂點(diǎn)數(shù)組 添加的先后順序?qū)τ诒闅v結(jié)果有影響
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邊二維數(shù)組 {'a', 'b'}表示頂點(diǎn)a->b的邊  添加的先后順序?qū)τ诒闅v結(jié)果有影響
        Character[][] edges = {
                {'A', 'C'},
                {'A', 'D'},
                //對于有向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會重復(fù)添加
                {'A', 'D'},
                //對于有向圖來說不是多余的邊關(guān)系
                {'D', 'A'},

                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'E', 'B'},
                {'D', 'B'},
                {'F', 'G'}};
        // 構(gòu)建圖有向圖
        AdjacencyList<Character> adjacencyList = new AdjacencyList<>(vexs, edges);
        //輸出圖
        System.out.println(adjacencyList);
        //深度優(yōu)先遍歷
        adjacencyList.DFS();
        //廣度優(yōu)先遍歷
        adjacencyList.BFS();
    }
}

/**
 * 無向圖鄰接矩陣簡單實現(xiàn)
 * {@link UndirectedAdjacencyMatrix#UndirectedAdjacencyMatrix(E[], E[][])}  構(gòu)建無向圖
 * {@link UndirectedAdjacencyMatrix#DFS()}  深度優(yōu)先遍歷無向圖
 * {@link UndirectedAdjacencyMatrix#BFS()}  廣度優(yōu)先遍歷無向圖
 * {@link UndirectedAdjacencyMatrix#toString()} ()}  輸出無向圖
 *
 * @author lx
 */
public class UndirectedAdjacencyMatrix<E> {

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Object[] vertexs;
    /**
     * 鄰接矩陣
     */
    private int[][] matrix;


    /*
     * 創(chuàng)建圖
     *
     * 參數(shù)說明：
     *     vexs  -- 頂點(diǎn)數(shù)組
     *     edges -- 邊數(shù)組
     */

    /**
     * 創(chuàng)建無向圖
     *
     * @param vexs  頂點(diǎn)數(shù)組
     * @param edges 邊二維數(shù)組
     */
    public UndirectedAdjacencyMatrix(E[] vexs, E[][] edges) {
        // 初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)
        vertexs = Arrays.copyOf(vexs, vexs.length);
        // 初始化邊矩陣,并填充邊信息
        matrix = new int[vexs.length][vexs.length];
        for (E[] edge : edges) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
            int p1 = getPosition(edge[0]);
            int p2 = getPosition(edge[1]);
            //對稱的兩個點(diǎn)位都置為1,無向圖可以看作相互可達(dá)的有向圖
            matrix[p1][p2] = 1;
            matrix[p2][p1] = 1;
        }
    }

    /**
     * 獲取某條邊的某個頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
     *
     * @param e 頂點(diǎn)的值
     * @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == e) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        System.out.println();
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        visited[i] = true;
        System.out.print(vertexs[i] + " ");
        // 遍歷該頂點(diǎn)的所有鄰接點(diǎn)。若該鄰接點(diǎn)是沒有訪問過，那么繼續(xù)遞歸遍歷領(lǐng)接點(diǎn)
        for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
            if (!visited[w]) {
                DFS(w, visited);
            }
        }
    }

    /**
     * 返回頂點(diǎn)v的第一個鄰接頂點(diǎn)的索引，失敗則返回-1
     *
     * @param v 頂點(diǎn)v在數(shù)組中的索引
     * @return 返回頂點(diǎn)v的第一個鄰接頂點(diǎn)的索引，失敗則返回-1
     */
    private int firstVertex(int v) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1)) {
            return -1;
        }
        /*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
         * 從i=0開始*/
        for (int i = 0; i < vertexs.length; i++) {
            if (matrix[v][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回頂點(diǎn)v相對于w的下一個鄰接頂點(diǎn)的索引，失敗則返回-1
     *
     * @param v 頂點(diǎn)索引
     * @param w 第一個鄰接點(diǎn)索引
     * @return 返回頂點(diǎn)v相對于w的下一個鄰接頂點(diǎn)的索引，失敗則返回-1
     */
    private int nextVertex(int v, int w) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
            return -1;
        }
        /*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
         * 由于鄰接點(diǎn)w的索引已經(jīng)獲取了,所以從i=w+1開始尋找*/
        for (int i = w + 1; i < vertexs.length; i++) {
            if (matrix[v][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /*
     * 廣度優(yōu)先搜索（類似于樹的層次遍歷）
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i] + " ");
                indexLinkedList.add(i);
            }
            if (!indexLinkedList.isEmpty()) {
                //j索引出隊列
                Integer j = indexLinkedList.poll();
                //繼續(xù)訪問j的鄰接點(diǎn)
                for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k] + " ");
                        //繼續(xù)入隊列
                        indexLinkedList.add(k);
                    }
                }
            }
        }
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                stringBuilder.append(matrix[i][j]).append(" ");
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }


    public static void main(String[] args) {
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Character[][] edges = {
                {'A', 'C'},
                //對于無向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會重復(fù)添加
                {'A', 'D'},
                {'A', 'D'},
                {'D', 'A'},

                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'E', 'B'},
                {'D', 'B'},
                {'F', 'G'}};
        //構(gòu)建圖
        UndirectedAdjacencyMatrix<Character> undirectedAdjacencyMatrix = new UndirectedAdjacencyMatrix<>(vexs, edges);
        //輸出圖
        System.out.println(undirectedAdjacencyMatrix);
        //深度優(yōu)先遍歷
        undirectedAdjacencyMatrix.DFS();
        //廣度優(yōu)先遍歷
        undirectedAdjacencyMatrix.BFS();
    }
}

/**
 * 有向圖鄰接矩陣簡單實現(xiàn)
 * {@link AdjacencyMatrix#AdjacencyMatrix(E[], E[][])}  構(gòu)建有向圖
 * {@link AdjacencyMatrix#DFS()}  深度優(yōu)先遍歷無向圖
 * {@link AdjacencyMatrix#BFS()}  廣度優(yōu)先遍歷無向圖
 * {@link AdjacencyMatrix#toString()} ()}  輸出無向圖
 *
 * @author lx
 */
public class AdjacencyMatrix<E> {

    /**
     * 頂點(diǎn)數(shù)組
     */
    private Object[] vertexs;
    /**
     * 鄰接矩陣
     */
    private int[][] matrix;

    /**
     * 創(chuàng)建有向圖
     *
     * @param vexs  頂點(diǎn)數(shù)組
     * @param edges 邊二維數(shù)組
     */
    public AdjacencyMatrix(E[] vexs, E[][] edges) {
        // 初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)
        vertexs = Arrays.copyOf(vexs, vexs.length);
        // 初始化邊矩陣,并填充邊信息
        matrix = new int[vexs.length][vexs.length];
        for (E[] edge : edges) {
            // 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值 p1,p2表示邊方向p1->p2
            int p1 = getPosition(edge[0]);
            int p2 = getPosition(edge[1]);
            //p1 出度的位置 置為1
            matrix[p1][p2] = 1;
            //無向圖和有向圖的鄰接矩陣實現(xiàn)的區(qū)別就在于下面這一行代碼
            //matrix[p2][p1] = 1;
        }
    }

    /**
     * 獲取某條邊的某個頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
     *
     * @param e 頂點(diǎn)的值
     * @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
     */
    private int getPosition(E e) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == e) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
     */
    public void DFS() {
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        //初始化所有頂點(diǎn)都沒有被訪問
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("DFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                DFS(i, visited);
            }
        }
        System.out.println();
    }

    /**
     * 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
     * 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
     *
     * @param i       頂點(diǎn)索引
     * @param visited 訪問標(biāo)志數(shù)組
     */
    private void DFS(int i, boolean[] visited) {
        visited[i] = true;
        System.out.print(vertexs[i] + " ");
        // 遍歷該頂點(diǎn)的所有鄰接點(diǎn)。若該鄰接點(diǎn)是沒有訪問過，那么繼續(xù)遞歸遍歷領(lǐng)接點(diǎn)
        for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
            if (!visited[w]) {
                DFS(w, visited);
            }
        }
    }

    /**
     * 返回頂點(diǎn)v的第一個鄰接頂點(diǎn)的索引，失敗則返回-1
     *
     * @param v 頂點(diǎn)v在數(shù)組中的索引
     * @return 返回頂點(diǎn)v的第一個鄰接頂點(diǎn)的索引，失敗則返回-1
     */
    private int firstVertex(int v) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1)) {
            return -1;
        }
        /*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
         * 從i=0開始*/
        for (int i = 0; i < vertexs.length; i++) {
            if (matrix[v][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回頂點(diǎn)v相對于w的下一個鄰接頂點(diǎn)的索引，失敗則返回-1
     *
     * @param v 頂點(diǎn)索引
     * @param w 第一個鄰接點(diǎn)索引
     * @return 返回頂點(diǎn)v相對于w的下一個鄰接頂點(diǎn)的索引，失敗則返回-1
     */
    private int nextVertex(int v, int w) {
        //如果索引超出范圍,則返回-1
        if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
            return -1;
        }
        /*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
         * 由于鄰接點(diǎn)w的索引已經(jīng)獲取了,所以從i=w+1開始尋找*/
        for (int i = w + 1; i < vertexs.length; i++) {
            if (matrix[v][i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /*
     * 廣度優(yōu)先搜索（類似于樹的層次遍歷）
     */
    public void BFS() {
        // 輔組隊列
        Queue<Integer> indexLinkedList = new LinkedList<>();
        //新建頂點(diǎn)訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
        boolean[] visited = new boolean[vertexs.length];
        for (int i = 0; i < vertexs.length; i++) {
            visited[i] = false;
        }
        System.out.println("BFS: ");
        for (int i = 0; i < vertexs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                System.out.print(vertexs[i] + " ");
                indexLinkedList.add(i);
            }
            if (!indexLinkedList.isEmpty()) {
                //j索引出隊列
                Integer j = indexLinkedList.poll();
                //繼續(xù)訪問j的鄰接點(diǎn)
                for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.print(vertexs[k] + " ");
                        //繼續(xù)入隊列
                        indexLinkedList.add(k);
                    }
                }
            }
        }
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                stringBuilder.append(matrix[i][j]).append(" ");
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }


    public static void main(String[] args) {
        Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Character[][] edges = {
                {'A', 'C'},
                //對于無向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會重復(fù)添加
                {'A', 'D'},
                {'A', 'D'},
                {'D', 'A'},

                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'E', 'B'},
                {'D', 'B'},
                {'F', 'G'}};
        //構(gòu)建圖
        AdjacencyMatrix<Character> undirectedAdjacencyMatrix = new AdjacencyMatrix<>(vexs, edges);
        //輸出圖
        System.out.println(undirectedAdjacencyMatrix);
        //深度優(yōu)先遍歷
        undirectedAdjacencyMatrix.DFS();
        //廣度優(yōu)先遍歷
        undirectedAdjacencyMatrix.BFS();
    }
}