图的最深首次搜索或DFS

package com.company.algs.graph.dfs;//时 代 J a v a - N o w J a v a . c o m 提供


import java.util.Arrays;

import java.util.Collections;

import java.util.LinkedList;

import java.util.List;


@SuppressWarnings({ "Duplicates", "WeakerAccess" })

public class DFS {

    public Vertex search(Vertex startVertex, String searchVertexName) {

        LinkedList<Vertex> stack = new LinkedList<>();

        stack.add(startVertex);


        int step = -1;

        while (!stack.isEmpty()) {

            step++;

            Vertex top = stack.pollFirst();/** 时 代 J a v a 公 众 号 提供 **/

            if (top.name.equals(searchVertexName)) {

                top.mark = true;

                top.step = step;

                return top;

            } else {

                if (!top.mark) {

                    top.mark = true;

                    for (Vertex v : top.adjacentVertices) {

                        if (!v.mark) {

                            v.depth = top.depth + 1;

                            stack.addFirst(v);

                        }

                    }

                }

            }

        }


        return null;

    }


    public void recursiveSearch(Vertex startVertex) {

        startVertex.mark = true;

        System.out.println("In: " + startVertex);

        for (Vertex v : startVertex.adjacentVertices) {

            if (!v.mark) {

                recursiveSearch(v);

            }

        }

        System.out.println("Out: " + startVertex);

    }


    public static void main(String[] args) {

        Vertex vertexA = new Vertex("A");

        Vertex vertexB = new Vertex("B");

        Vertex vertexC = new Vertex("C");

        Vertex vertexD = new Vertex("D");

        Vertex vertexE = new Vertex("E");

        Vertex vertexF = new Vertex("F");

        Vertex vertexG = new Vertex("G");


        vertexA.adjacentVertices = Arrays.asList(vertexB, vertexC);

        vertexB.adjacentVertices = Arrays.asList(vertexA, vertexD);

        vertexC.adjacentVertices = Arrays.asList(vertexA, vertexE);

        vertexD.adjacentVertices = Arrays.asList(vertexB, vertexE);

        vertexE.adjacentVertices = Arrays.asList(vertexC, vertexF, vertexD);

        vertexF.adjacentVertices = Arrays.asList(vertexE, vertexG);

        vertexG.adjacentVertices = Collections.singletonList(vertexF);


        DFS dfs = new DFS();

        dfs.recursiveSearch(vertexA);

        //        Vertex vertex = dfs.search(vertexA, "B");

        //        System.out.println(vertex == null ? "Not found" : vertex);

    }


    private static class Vertex {

        private List<Vertex> adjacentVertices;

        private String name;

        private