学习笔记之图的遍历

学习笔记之图的遍历

Model

package dfs;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Objects;

public class Graph {

  static class Node {

    int n;
    String name;
    boolean visited;

    public Node(int n, String name) {
      this.n = n;
      this.name = name;
    }

    public void visit() {
      this.visited = true;
    }

    public void unvisit() {
      this.visited = false;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Node node = (Node) o;
      return n == node.n &&
        Objects.equals(name, node.name);
    }

    @Override
    public int hashCode() {
      return Objects.hash(n, name);
    }
  }

  HashMap<Node, LinkedList<Node>> adjacencyMap;
  boolean directed;

  public Graph(boolean directed) {
    this.directed = directed;
    adjacencyMap = new HashMap<>();
  }

  public void addEdgeHelper(Node a, Node b) {
    LinkedList<Node> tmp = adjacencyMap.get(a);

    if (tmp != null) {
      tmp.remove(b);
    } else {
      tmp = new LinkedList<>();
    }
    tmp.add(b);
    adjacencyMap.put(a, tmp);
  }

  public void addEdge(Node source, Node destination) {

    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source)) {
      adjacencyMap.put(source, null);
    }

    if (!adjacencyMap.keySet().contains(destination)) {
      adjacencyMap.put(destination, null);
    }

    addEdgeHelper(source, destination);

    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
      addEdgeHelper(destination, source);
    }
  }

  public void printEdges() {
    for (Node node : adjacencyMap.keySet()) {
      System.out.print("The " + node.name + " has an edge towards: ");
      for (Node neighbor : adjacencyMap.get(node)) {
        System.out.print(neighbor.name + " ");
      }
      System.out.println();
    }
  }

  public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source).contains(destination);
  }

}

深度优先遍历

从图中某个顶点V出发，访问该顶点，然后从V的未被访问的邻接点出发递归比那里，直到和V有路径连通的所有顶点都被访问到。

然而对于非连通图，在选定一个顶点进行深度优先遍历后，若图中还有顶点未被访问，则选择图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。

package dfs;

import java.util.LinkedList;
import java.util.Set;

public class DFS {

  private Graph graph;

  public DFS(Graph graph) {
    this.graph = graph;
  }

  public void dfs() {

    Set<Graph.Node> nodes = graph.adjacencyMap.keySet();

    for (Graph.Node node : nodes) {
      if (!node.visited) {
        dfsHelper(node);
      }
    }
  }

  private void  dfsHelper(Graph.Node node) {
    node.visit();
    System.out.println(node.name + " ");

    LinkedList<Graph.Node> adjacentNodes = graph.adjacencyMap.get(node);
    if (adjacentNodes == null) {
      return;
    }

    for (Graph.Node adjacentNode : adjacentNodes) {
      if (!adjacentNode.visited) {
        dfsHelper(adjacentNode);
      }
    }

  }

  public static void main(String[] args) {

    Graph graph = new Graph(true);
    Graph.Node zero = new Graph.Node(0, "0");
    Graph.Node one = new Graph.Node(1, "1");
    Graph.Node two = new Graph.Node(2, "2");
    Graph.Node three = new Graph.Node(3, "3");
    Graph.Node four = new Graph.Node(4, "4");
    Graph.Node five = new Graph.Node(5, "5");
    Graph.Node six = new Graph.Node(6, "6");
    Graph.Node seven = new Graph.Node(7, "7");
    Graph.Node eight = new Graph.Node(8, "8");

    graph.addEdge(one,zero);
    graph.addEdge(three,one);
    graph.addEdge(two,seven);
    graph.addEdge(two,four);
    graph.addEdge(five,two);
    graph.addEdge(five,zero);
    graph.addEdge(six,five);
    graph.addEdge(six,three);
    graph.addEdge(six,eight);
    graph.addEdge(seven,five);
    graph.addEdge(seven,six);
    graph.addEdge(seven,eight);

    DFS dfs = new DFS(graph);
    dfs.dfs();


  }
}

广度优先遍历

类似树的层序遍历，借助队列。

package bfs;

import java.util.LinkedList;

public class BFS {

    private Graph graph;
    private Graph.Node start;

    public BFS(Graph graph, Graph.Node start) {
        this.graph = graph;
        this.start = start;
    }

    public void bfs() {

        LinkedList<Graph.Node> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            Graph.Node node = queue.removeFirst();

            if (node.visited) {
                continue;
            }

            node.visit();
            System.out.print(node.name + " ");

            LinkedList<Graph.Node> allNeighbors = graph.adjacencyMap.get(node);

            if (allNeighbors == null) {
                continue;
            }

            for (Graph.Node neighbor: allNeighbors) {
                if (!neighbor.visited) {
                    queue.add(neighbor);
                }
            }

        }

    }

    public static void main(String[] args) {
        Graph graph = new Graph(true);
        Graph.Node zero = new Graph.Node(0, "0");
        Graph.Node one = new Graph.Node(1, "1");
        Graph.Node two = new Graph.Node(2, "2");
        Graph.Node three = new Graph.Node(3, "3");
        Graph.Node four = new Graph.Node(4, "4");
        Graph.Node five = new Graph.Node(5, "5");
        Graph.Node six = new Graph.Node(6, "6");
        Graph.Node seven = new Graph.Node(7, "7");
        Graph.Node eight = new Graph.Node(8, "8");

        graph.addEdge(one,zero);
        graph.addEdge(three,one);
        graph.addEdge(two,seven);
        graph.addEdge(two,four);
        graph.addEdge(five,two);
        graph.addEdge(five,zero);
        graph.addEdge(six,five);
        graph.addEdge(six,three);
        graph.addEdge(six,eight);
        graph.addEdge(seven,five);
        graph.addEdge(seven,six);
        graph.addEdge(seven,eight);

        BFS bfs = new BFS(graph, two);
        bfs.bfs();

    }
}

https://stackabuse.com/graphs-in-java-depth-first-search-dfs/

https://stackabuse.com/graphs-in-java-breadth-first-search-bfs/