基本概念
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
无向图
在这张图中，有点集V = { 1 , 2 , 3 , 4 , 5 , 6 }，边集E = { ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 5 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 4 , 6 ) } 。在无向图中，边( u , v ) (u,v)是一样的，因此只要记录一个就行了，也就是说方向是无关的。
有向图
有向图也很好理解，就是加上了方向性，顶点( u , v )之间的关系和顶点(v,u)之间的关系不同。例如你是我微信好友，我是你微信好友属于无向图关系你跟我是好友是一样的。而你欠我的钱和我欠你的钱关系就属于有向图关系，这可不能没有方向了。
加权图、无权图
与加权图对应的就是无权图，或叫等权图。如果一张图不含权重信息，我们就认为边与边之间没有差别。不过，具体建模的时候，很多时候都需要有权重，比如对中国重要城市间道路联系的建模，总不能认为从北京去上海和从北京去广州一样远(等权)。
图的存储
-
1.邻接矩阵
拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个。因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用二维数组（矩阵）。
如图所示，顶点0和顶点1之间有边关联，那么矩阵中的元素A[0][1]与A[1][0]的值就是1；顶点1和顶点2之间没有边关联，那么矩阵中的元素A[1][2]与A[2][1]的值就是0。
像这样表达图中顶点关联关系的矩阵，就叫做邻接矩阵。
-
2.邻接表
邻接矩阵的缺点是什么呢？占用了太多的空间。试想，如果一个图有1000个顶点，其中只有10个顶点之间有关联（这种情况叫做稀疏图），却不得不建立一个1000X1000的二维数组，实在太浪费了。为了解决邻接矩阵占用空间大的问题，人们想到了另一种图的表示方法：邻接表。
在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。
入度
是图论算法中重要的概念之一。它通常指有向图中某点作为图中边的终点的次数之和。当入度为 0 时，指有向图中的点不作为任何边的终点，也就是说，这一点所连接的边都把这一点作为起点。
1557. 可以到达所有点的最少点数目
给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。
找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
你可以以任意顺序返回这些节点编号。
示例 1：
输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出：[0,3]
解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。
题解：
class Solution {
/**
* 思路：
* 如果图中有一条a->b的边，那么b一定不会在最小的点集中，因为b能到达的点a也一定能到达，且a还能比b多到达一个点（a自己），选b不如选a。因此，只有入度为0的点才可能在最小点集中。
* 最小点集中必须包括所有入度为0的点，假如某个入度为0的点a不在最小点集中，那么最小点集中的其他点一定无法访问到a点，不符合最小点集能到达图中所有点的要求。
* 因此最小点集为图中所有入度为0的点。
*/
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
Set<Integer> tails = new HashSet<>(); //暂存尾节点数据
Set<Integer> nodes = new HashSet<>(); //最小子集合
for (List<Integer> list : edges) {
tails.add(list.get(1)); //遍历存储每个子集合的尾数据
}
//遍历每个子集合，判断首数据，如果在所有尾数据都不包含，则该点入度为0
for (List<Integer> list : edges) {
if (tails.contains(list.get(0))) {
//该点不是入度为0，继续下一个数判断
continue;
}
//该点入度为0
nodes.add(list.get(0));
}
List<Integer> listNode = new ArrayList<>();
for (Integer node : nodes) {
listNode.add(node);
}
return listNode;
}
}
