/**
 * 圖的深度優(yōu)先搜索算法
 *
 * @author alvin
 * @date 2022/10/31
 * @since 1.0
 **/
public class DepthFirstSearch {
    //索引代表頂點，值表示當(dāng)前頂點是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄有多少個頂點與s頂點相通
    private int count;

    //構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點的所有相鄰頂點
    public DepthFirstSearch(Graph G, int s) {
        //創(chuàng)建一個和圖的頂點數(shù)一樣大小的布爾數(shù)組
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    //使用深度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點
    private void dfs(Graph G, int v) {
        //把當(dāng)前頂點標(biāo)記為已搜索
        marked[v] = true;
        //遍歷v頂點的鄰接表，得到每一個頂點w
        for (Integer w : G.adj(v)) {
            //遍歷v頂點的鄰接表，得到每一個頂點w
            if (!marked[w]) {
                //如果當(dāng)前頂點w沒有被搜索過，則遞歸搜索與w頂點相通的其他頂點
                dfs(G, w);
            }
        }

        //相通的頂點數(shù)量+1
        count++;
    }

    //判斷w頂點與s頂點是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //獲取與頂點s相通的所有頂點的總數(shù)
    public int count() {
        return count;
    }
}

public class DepthFirstSearchTest {

    @Test
    public void test() {
        //準(zhǔn)備Graph對象
        Graph G = new Graph(13);
        G.addEdge(0,5);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(0,6);
        G.addEdge(5,3);
        G.addEdge(5,4);
        G.addEdge(3,4);
        G.addEdge(4,6);
        G.addEdge(7,8);
        G.addEdge(9,11);
        G.addEdge(9,10);
        G.addEdge(9,12);
        G.addEdge(11,12);

        //準(zhǔn)備深度優(yōu)先搜索對象
        DepthFirstSearch search = new DepthFirstSearch(G, 0);
        //測試與某個頂點相通的頂點數(shù)量
        int count = search.count();
        System.out.println("與起點0相通的頂點的數(shù)量為:"+count);
        //測試某個頂點與起點是否相同
        boolean marked1 = search.marked(5);
        System.out.println("頂點5和頂點0是否相通："+marked1);
        boolean marked2 = search.marked(7);
        System.out.println("頂點7和頂點0是否相通："+marked2);
    }
}

/**
 * 圖的廣度優(yōu)先搜索算法
 *
 * @author alvin
 * @date 2022/10/31
 * @since 1.0
 **/
public class BreadthFirstSearch {
    //索引代表頂點，值表示當(dāng)前頂點是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄有多少個頂點與s頂點相通
    private int count;
    //用來存儲待搜索鄰接表的點
    private Queue<Integer> waitSearch;

    //構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點的所有相鄰頂點
    public BreadthFirstSearch(Graph G, int s) {
        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new ArrayDeque<>();

        bfs(G, s);
    }

    //使用廣度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點
    private void bfs(Graph G, int v) {
        //把當(dāng)前頂點v標(biāo)識為已搜索
        marked[v] = true;
        //讓頂點v進(jìn)入隊列，待搜索
        waitSearch.add(v);
        //通過循環(huán)，如果隊列不為空，則從隊列中彈出一個待搜索的頂點進(jìn)行搜索
        while (!waitSearch.isEmpty()) {
            //彈出一個待搜索的頂點
            Integer wait = waitSearch.poll();
            //遍歷wait頂點的鄰接表
            for (Integer w : G.adj(wait)) {
                if (!marked[w]) {
                    bfs(G, w);
                }
            }
        }
        //讓相通的頂點+1；
        count++;

    }

    //判斷w頂點與s頂點是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //獲取與頂點s相通的所有頂點的總數(shù)
    public int count() {
        return count;
    }
}

public class BreadthFirstSearchTest {

    @Test
    public void test() {
        //準(zhǔn)備Graph對象
        Graph G = new Graph(13);
        G.addEdge(0, 5);
        G.addEdge(0, 1);
        G.addEdge(0, 2);
        G.addEdge(0, 6);
        G.addEdge(5, 3);
        G.addEdge(5, 4);
        G.addEdge(3, 4);
        G.addEdge(4, 6);
        G.addEdge(7, 8);
        G.addEdge(9, 11);
        G.addEdge(9, 10);
        G.addEdge(9, 12);
        G.addEdge(11, 12);

        //準(zhǔn)備廣度優(yōu)先搜索對象
        BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
        //測試與某個頂點相通的頂點數(shù)量
        int count = search.count();
        System.out.println("與起點0相通的頂點的數(shù)量為:" + count);
        //測試某個頂點與起點是否相同
        boolean marked1 = search.marked(5);
        System.out.println("頂點5和頂點0是否相通：" + marked1);
        boolean marked2 = search.marked(7);
        System.out.println("頂點7和頂點0是否相通：" + marked2);
    }
}

public class TrafficProjectGraph {

    public static void main(String[] args) throws Exception{
        //城市數(shù)量
        int totalNumber =  20;
        Graph G = new Graph(totalNumber);
        //添加城市的交通路線
        G.addEdge(0,1);
        G.addEdge(6,9);
        G.addEdge(3,8);
        G.addEdge(5,11);
        G.addEdge(2,12);
        G.addEdge(6,10);
        G.addEdge(4,8);

        //構(gòu)建一個深度優(yōu)先搜索對象，起點設(shè)置為頂點9
        DepthFirstSearch search = new DepthFirstSearch(G, 9);

        //調(diào)用marked方法，判斷8頂點和10頂點是否與起點9相通
        System.out.println("頂點8和頂點9是否相通："+search.marked(8));
        System.out.println("頂點10和頂點9是否相通："+search.marked(10));

    }
}