图

图的定义

1）由点的集合和边的集合构成

2）虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达

3）边上可能带有权值

1.图结构的表达

1）邻接表法

2）邻接矩阵法

3）除此之外还有其他众多的方式

2.图的面试题如何搞定

图的算法都不算难，只不过coding的代价比较高

1）先用自己最熟练的方式，实现图结构的表达

2）在自己熟悉的结构上，实现所有常用的图算法作为模板

3）把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可 ==adapter==

3.点结构和边结构和图

// 点结构的描述
public class Node {
  //值多少
	public int value;
  //入度,多少个进来的边
	public int in;
  //出度,多少个出去的边
	public int out;
  //直接到达的节点
	public ArrayList<Node> nexts;
  //直接出去的边
	public ArrayList<Edge> edges;

	public Node(int value) {
		this.value = value;
		in = 0;
		out = 0;
		nexts = new ArrayList<>();
		edges = new ArrayList<>();
	}
}

//边
public class Edge {
  //权重
   public int weight;
  //从哪个点到哪个点的一条边的描述
   public Node from;
   public Node to;

   public Edge(int weight, Node from, Node to) {
      this.weight = weight;
      this.from = from;
      this.to = to;
   }
}

//图
public class Graph {
  //为什么是一张哈希表,用户给的是一个int值,例如一个城市,用0替代,所以我们0对应着0的node,
	public HashMap<Integer, Node> nodes;
	public HashSet<Edge> edges;
	
	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>();
	}
}

4.接口转化

上面提到的,面试题表示方法千奇百怪,我们不能够每种都来一套算法,我们就给他的结构转成我们的结构,然后在我们玩的6的结构里玩

public class GraphGenerator {

   // matrix 所有的边
   // N*3 的矩阵
   // [weight, from节点上面的值，to节点上面的值]
   // 
   // [ 5 , 0 , 7]
   // [ 3 , 0,  1]
   // 
   public static Graph createGraph(int[][] matrix) {
      Graph graph = new Graph();
      for (int i = 0; i < matrix.length; i++) {
          // 拿到每一条边， matrix[i] 
         int weight = matrix[i][0];
         int from = matrix[i][1];
         int to = matrix[i][2];
         if (!graph.nodes.containsKey(from)) {
            graph.nodes.put(from, new Node(from));
         }
         if (!graph.nodes.containsKey(to)) {
            graph.nodes.put(to, new Node(to));
         }
         Node fromNode = graph.nodes.get(from);
         Node toNode = graph.nodes.get(to);
         Edge newEdge = new Edge(weight, fromNode, toNode);
         fromNode.nexts.add(toNode);
         fromNode.out++;
         toNode.in++;
         fromNode.edges.add(newEdge);
         graph.edges.add(newEdge);
      }
      return graph;
   }

}

5.图的宽度优先遍历

1. 利用队列实现
2. 从源节点开始依次按照宽度进队列，然后弹出
3. 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
4. 直到队列变空

6.图的深度优先遍历

1. 利用栈实现
2. 从源节点开始把节点按照深度放入栈，然后弹出
3. 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈(栈中,就是我的深度链逆序)
4. 直到栈变空