[数据结构与算法]数据结构Graph的深度优先遍历DFS和广度优先遍历BFS

图可以看做是顶点和边相连组成的结构.根据边是否有方向，分为有向图和无向图

图的实现方式

一般通过邻接矩阵和邻接表来表示图

邻接链表

Java 代码实现

public class Graph {
    ArrayList<ArrayList<Integer>> graph;
    public Graph(int v){
        graph = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            graph.add(new ArrayList<>());
        }
    }
    public void addEdge(int start,int end){
        graph.get(start).add(end);
    }
    public void removeEdge(int start,int end){
        graph.get(start).remove((Integer) end);
    }
}

图的遍历

深度优先遍历

class GraphTraversal{
    Graph graph;
    boolean[] visited;
    public GraphTraversal(Graph graph){
        this.graph = graph;
        visited = new boolean[graph.graph.size()];
    }
    //深度优先遍历
    public void DFSTraversal(int v){
        if(visited[v]) return;
        visited[v] = true;
        System.out.println(v + "->");
        ListIterator<Integer> neighbors = graph.graph.get(v).listIterator();
        while (neighbors.hasNext()){
            Integer next = neighbors.next();
            if(! visited[next]){
                DFSTraversal(next);
            }
        }
    }
    public void DFS(){
        for (int i = 0; i < graph.graph.size(); i++) {
            if(! visited[i]){
                DFSTraversal(i);
            }
        }
    }
}

广度优先遍历

class GraphTraversal{
    Graph graph;
    boolean[] visited;
    public GraphTraversal(Graph graph){
        this.graph = graph;
        visited = new boolean[graph.graph.size()];
    }
//广度优先遍历
    public void BFSTraversal(int v){
        Deque<Integer> queue = new LinkedList<>();
        visited[v] = true;
        queue.addFirst(v);
        while (queue.size() != 0){
            Integer cur = queue.pollFirst();
            System.out.println(cur + "->");
            ListIterator<Integer> neighbors = graph.graph.get(cur).listIterator();
            while (neighbors.hasNext()){
                Integer next = neighbors.next();
                if(! visited[next]){
                    queue.offerLast(next);
                    visited[next] = true;
                }
            }
        }
    }
    public void BFS(){
        for (int i = 0; i < graph.graph.size(); i++) {
            if(! visited[i]){
                BFSTraversal(i);
            }
        }
    }
}