一、图的基本构成

地图上有很多的建筑，每个建筑之间有着四通八达的道路连接着，如果想要使用数据结构来表示建筑和建筑之间的道路，就应该选择图。

树是由节点构成的，存在一对多的关系，并且节点之间有着父节点、子节点的划分。图是比树结构更加复杂的数据结构

树里面的节点放在图中指的是顶点，是图中最基本的单元，存在着多对多的关系，顶点之间都是平等的，没有父顶点、子顶点这样的说法

连接各个顶点的是边，对于带权图来说，边并不是一样的，有各自的权重，就像是城市之间的道路有各自的长短一样。并且边是存在方向的，对于有向图来说，顶点A能够到达顶点B，但是顶点B没有办法到达顶点A，对于无向图来说，顶点A、B之间就是互通的

二、图的表达方式

关于图的表达方式有很多种，常见的有邻接矩阵、邻接表、数组 …

1）邻接矩阵

邻接矩阵是用来表达顶点之间关联关系的矩阵，就是通过一个 n * n 的数组将图表述出来

如上图所示，由于有5个顶点，因此创建 5 * 5 的二维数组，数组的行代表着起始顶点，列代表着终止顶点，元素值代表着从起始顶点到终止顶点的权重。

顶点 A 可以通向顶点 B ，权重为 9，数组元素 arr[0][1] 就是 9。当然像顶点 A 到顶点 A 这样的情况，对应的值必然是 0

如果这个图是一个无向图，最后得到的二维数组一定是一个对称的数组，顶点 A 和顶点 B 有关联，顶点 B 必然和顶点 A 有关联

2）邻接表

邻接矩阵的缺点就在于空间占用量太大，如果有 N 个顶点，意味着需要使用到 N * N 的二维数组，N 非常大时，太浪费空间，邻接表法就是一个相对来说更加节省空间的表示图的方法

在邻接表中，图的每个顶点都会是链表的头节点，一共有 5 个顶点，表示有 5 个链表，头节点后面依次连接着该顶点可以到达的相邻顶点。链表节点由三部分组成：顶点值，到目标顶点的权重，指向下一个节点的地址

如果想要知道顶点 C 是否可以到达顶点 D，只需要对以顶点 C 为链表头节点的链表进行遍历即可，若存在，表示可达，否则不可达

当然如果想要有多少顶点可以到达顶点 D，我们可以选择将所有的链表都进行遍历操作，但是会有一点浪费时间，因此我们可以使用逆邻接表来解决

逆邻接表每个顶点也作为链表的头节点，链表后面依次跟着的节点是可以到达该顶点的临近顶点，想要找可以到达顶点 D 的顶点都有哪些，直接找到以顶点 D 为头节点的链表进行遍历即可

3）数组

数组也是一种很常见的表达图的方式，使用一个二维数组，其中每一行有三个元素：起点顶点值，目标顶点值，两顶点间的权重

4）综合

表达图的方式有太多种，在写相关题目的时候，就需要根据题目提供的图的模型来解决问题。为了能够更加快速的解决问题，就需要准备一个图的标准模板，只需要掌握了标准模板解决问题的方法，将题目提供的图的模型转换成标准模板即可

顶点：

public class Node {//顶点的值public Integer value;//顶点的出度(有多少条边以该顶点为起点)public int out;//顶点的入度(有多少条边以该顶点为终点)public int in;//有这个顶点发散出去的相邻顶点有哪些public ArrayList<Node> nextNodes;//由这个顶点发散出去的边有哪些public ArrayList<Edge> borderEdges;public Node(Integer value) {this.value = value;out = 0;in = 0;nextNodes = new ArrayList<>();borderEdges = new ArrayList<>();}
}

边：

public class Edge {//边的起点public Node from;//边的终点public Node to;//边的权值public int weight;public Edge(Node from,Node to,int weight) {this.from = from;this.to = to;this.weight = weight;}
}

图：

//图所包含的两大要素，顶点和边
public class Graph {//图中所有的顶点，key是顶点的值，value是对应的顶点的具体信息public HashMap<Integer,Node> nodes;//图中的边public HashSet<Edge> edges;public Graph() {nodes = new HashMap<>();edges = new HashSet<>();}
}

例如：将通过数组表达的图转换成标准模板

public class ChangeGraph {//提供一个二维数组，其中的每一个一维数组由三个元素组成[原点，终点，权值]public Graph ChangeCase(int[][] array) {Graph graph = new Graph();//创建一个新的图for (int i = 0;i < array.length;i ++) {int from = array[i][0];int to = array[i][1];if(!graph.nodes.containsKey(from)) {//没有包含起始点，就创建一个新点Node fromNode = new Node(from);fromNode.out++;//出度加一graph.nodes.put(from,fromNode);//添加到图的模型中}else {//已经包含起始点，那就单纯出度加一graph.nodes.get(from).out++;}if (!graph.nodes.containsKey(to)) {//没有包含终点，就创建一个终点Node toNode = new Node(to);toNode.in++;//入度加一graph.nodes.put(to,toNode);//添加到图的模型中}else {//已经包含终点，就单纯入度加一graph.nodes.get(to).in++;}Node node1 = graph.nodes.get(from);Node node2 = graph.nodes.get(to);node1.nextNodes.add(node2);//新添加临近点Edge newEdge = new Edge(node1,node2,array[i][2]);//创建新边graph.edges.add(newEdge);//添加到图的模型中node1.borderEdges.add(newEdge);//新添加临近边}return graph;}
}