图之基础概念

图的表示法

1. 邻接矩阵
2. 邻接列表

邻接矩阵比较消耗内存，不适合使用稀疏情况

节点

public class Node {  
   public int value;  
   public int in;  
   public int out;  
   public ArrayList<Edge> edges;  
}

边

public class Edge {  
   public int weight;  
   public Node from;  
   public Node to;  
}

图

public class Graph {  
   public HashMap<Integer,Node> nodes;  
   public HashSet<Edge> edges;  
}

模板

bfs

public static void bfs(Node node) {  
   Queue<Node> queue = new LinkedList<>();  
   HashSet<Node> map = new HashSet<>();  
   queue.add(node);  
   map.add(node);  
   
   while (!queue.isEmpty()) {  
      Node cur = queue.poll();  
      System.out.println(cur.value);  
      for (Node next : cur.nexts) {  
         if (!map.contains(next)) {  
            map.add(next);  
            queue.add(next);  
         }  
      }  
   }  
}

dfs

public static void dfs(Node node) {  

   Stack<Node> stack = new Stack<>();  
   HashSet<Node> set = new HashSet<>();  
   stack.add(node);  
   set.add(node);  

   while (!stack.isEmpty()) {  
      Node cur = stack.pop();  
      for (Node next : cur.nexts) {  
         if (!set.contains(next)) {  
            stack.push(cur);  
            stack.push(next);  
            set.add(next);  
            System.out.println(next.value);  
            break;  
         }  
      }  
   }  
}