前言： 该篇文章将介绍如何应付面试中的图结构，并且还简单介绍了图的宽度优先遍历和深度优先遍历

1. 图的基本介绍

基本概念：

• 图由点的集合和边的集合构成
• 虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达
• 边上可能带有权值

图的结构：

• 邻接表法
• 邻接矩阵法
• 还有其它众多的方式

如何搞定图的面试题： 图的算法都不难，但是写代码时会很复杂，coding 代价比较高，因此可以通过以下的方式来应付图的面试题

• 先用自己最熟练的方式，实现图结构的表达
• 在自己熟悉的结构上，实现所有常用图的算法作为模板
• 把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可（做一个适配器）

2. 图的实现

实现代码：

• 点结构的实现

import java.util.ArrayList;

// 点结构的描述
public class Node {
	// 该点的值
	public int value;
	// 该点的入度数
	public int in;
	// 该点的出度数
	public int out;
	// 该点的相邻点（指该点指向的点）
	public ArrayList<Node> nexts;
	// 该点的相邻边（指该点指向的边）
	public ArrayList<Node> 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;
	}
}

• 图结构的实现

import java.util.HashMap;
import java.util.HashSet;

// 图的描述
public class Graph {
	// 点的集合，Integer 表示节点的值，先有值，再创建节点
	public HashMap<Integer, Node> nodes;
	// 边的集合
	public HashSet<Edge> edges;

	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>();
	}
}

常见面试题的图结构：

• 用一个二维数组表示，每个一维数组里面有三个值
• 第一个值表示边的权重
• 第二个值表示边的出发节点
• 第三个值表示边的目的节点

假设现有一个数组表示是这样的：{{3, 0, 7}, {5, 1, 2}, {6, 2, 7}}，它符合上面图的结构，那么它用图表示如下

当我们面试遇见这种结构的图时，就可以使用我们上述已经定义好的图的结构来表示，因此我们只需要再做一个适配的过程

适配代码：

public class Create {
	
	public static Graph createGraph(int[][] matrix) {
		Graph graph=new Graph();
		for(int i=0;i<matrix.length;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 edge=new Edge(weight,fromNode,toNode);
			fromNode.out++;
			toNode.in++;
			fromNode.nexts.add(toNode);
			fromNode.edges.add(edge);
			graph.edges.add(edge);
		}
		return graph;
	}
}

3. 图的宽度优先遍历（BFS）

图的宽度优先遍历方式：
从图中弹出最高层的节点，用一个集合 Set 注册该节点，然后将该节点入队列。当我们从队列中将它弹出时，将它的相邻节点（指向的节点）进行入队列，但是首先需要判断相邻节点是否在集合中注册，如果注册了，就不做处理；如果未注册，就进行注册，并将该节点进行入队列。然后重复刚刚的操作，对每层进行遍历

方法模板：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {
	// BFS 需要有一个头节点
	public static void bfs(Node start) {
		if (start == null) {
			return;
		}
		Queue<Node> queue = new LinkedList<>();
		HashSet<Node> set = new HashSet<>();
		queue.add(start);
		set.add(start);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			System.out.println(node.value);
			for (Node cur : node.nexts) {
				if (!set.contains(cur)) {
					set.add(cur);
					queue.add(cur);
				}
			}
		}
	}
}

4. 图的深度优先遍历（DFS）

图的宽度优先遍历方式：
一条路走到底为止，但是不能形成环路，当到底为止后，就返回上一个节点，如果该节点没有其它路，就继续往上。当某个节点还有其它路，先判断新的节点是否已经打印果过，打印过就继续往上，直到找到新的节点且未打印过。当最终返回头节点，则深度遍历结束。其中使用集合 Set 来标记该节点是否走过或打印过，使用栈来存储当前遍历路线的节点

方法模板：

import java.util.HashSet;
import java.util.Stack;

public class DFS {

	public static void dfs(Node node) {
		if (node == null) {
			return;
		}
		Stack<Node> stack = new Stack<>();
		HashSet<Node> set = new HashSet<>();
		stack.add(node);
		set.add(node);
		// 在入栈时就进行打印
		System.out.println(node.value);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			for (Node next : cur.nexts) {
				if (!set.contains(next)) {
					stack.add(cur);
					stack.add(next);
					set.add(next);
					System.out.println(next.value);
					break;
				}
			}
		}
	}
}