（如代码有误，烦请各位指正）
1.图的结构：用点集加边集的形式来实现//图定义包含两部分：点集和边集
class Graph{
HashMap nodes;
HashSet edges;
public Graph(){
nodes=new HashMap();
edges=new HashSet();
}
}
//点集：该点的值；进入该点的边数；从该点出去的边数；从该点出去相连的点的集合；从该点出去的边的集合
class Node{
int value;
int in;
int out;
ArrayList nexts;
ArrayList edges;
public Node(){
in=0;
out=0;
nexts=new ArrayList<>();
edges=new ArrayList<>();
}
}
//边集：该边的权重；与该边相连的两个点
class Edge{
int weight;
Node from;
Node to;
public Edge(int weight,Node from,Node to){
this.weight=weight;
this.from=from;
this.to=to;
}
}
2.图的宽度优先遍历（Breadth First Search）
图的宽度优先遍历跟二叉树的优先遍历类似，不过要防止图中的环使程序无法停止的情况。
解决方法：增加一个集合，用来记录已经遍历过了哪些点，保证不发生一个点被重复遍历的情况。
public static void GraphBFS(Node head){
if(head==null){
return;
}
HashSet set=new HashSet<>();
Queue queue=new LinkedList<>();
set.add(head);
queue.add(head);
while(!queue.isEmpty()){
Node cur=queue.poll();
System.out.println(cur.value);
for(Node next: cur.nexts){
if(!set.contains(next)){
set.add(next);
queue.add(next);
}
}
}
}
3.图的深度优先遍历（Deepth First Search）
//图的深度优先遍历
public static void GraphDFS(Node head){
if(head==null){
return;
}
Stack stack=new Stack<>();
HashSet set=new HashSet<>();
stack.add(head);
set.add(head);
System.out.println(head.value);//压入栈即打印
while(!stack.isEmpty()){
Node cur=stack.pop();
for(Node next:cur.nexts){
if(!set.contains(next)){
stack.add(cur);//cur还有其他nexts点没被输出，等待下一次，需要压入栈
stack.add(next);
set.add(next);
System.out.println(next.value);//往下找到一个点就打印
break;//深度优先遍历，每次只往下取一个点
}
}
}
}
4.拓扑排序（有向无环图）
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。拓扑排序
思路：先找入度为0的点，输出，把该点有关的影响全部删掉，再找入度为0的点，重复此过程。
//拓扑排序
public static List sortedTopology(Graph graph){
//记录图各个点的入度是多少
HashMap inMap=new HashMap<>();
//入度为0的点进入队列（使用队列的先进先出）
Queue zeroInQueue=new LinkedList<>();
//遍历图中的节点，找到入度为0的节点进入队列，确定每个节点的入度并更新哈希表
for (Node cur:graph.nodes.values()){
inMap.put(cur, cur.in);
if(cur.in==0){
zeroInQueue.add(cur);
}
}
ArrayList result=new ArrayList<>();
while(!zeroInQueue.isEmpty()){
Node cur=zeroInQueue.poll();
result.add(cur);//将弹出的入度为0的节点保留在result中
for(Node next: cur.nexts){
inMap.put(next, next.in-1);//消除已弹出节点的影响
if(inMap.get(next)==0){
zeroInQueue.add(next);//队列中加入新的入度为0的节点
}
}
}
return result;
}
5.最小生成树（无向图）
（1）k算法*kruskal：从边的角度出发，依次选择最小的边，看有没有形成环，没形成环则加上，形成则不加。
难点：怎么确定能不能形成环：集合查询合并（假定所有的点一开始是一个单独的集合，加一条边，则边连的点聚合成一个集合，若边的点在同一个集合里，则不要该条边）
代码后续补
（2）p算法（prim）：从点的角度出发，从被解锁的边中选一条权重最小的边，加入相连的点，再根据这个点，解锁相连的边，从所有被解锁的边中选权重最小且之前没有被选择的一条边（这条边要拽进来一个新的点），重复上述步骤。
//p算法
//implements用来实现接口
public static class EdgeCompartor implements Comparator{
@Override//加上Override标签后如果你写错重写的方法，系统会给你检验
public int compare(Edge e1, Edge e2){
return e1.weight-e2.weight;
}
}
public static Set primMST(Graph graph){
//小根堆存储已经被解锁的边，用来排序，方便弹出最短的边（用自己规定的比较方法）
PriorityQueue priorityQueue=new PriorityQueue<>(new EdgeCompartor());
//用来记录已经被解锁的点
HashSet nodeSet=new HashSet<>();
//用来存储被选择的边
HashSet result=new HashSet<>();
//循环是为了解决图的点存在不连通的情况
for(Node node:graph.nodes.values()){
if(!nodeSet.contains(node)){
nodeSet.add(node);
for(Edge edge:node.edges){
priorityQueue.add(edge);//解锁该点相关的边，会有重复的边进入，但是有nodeSet
}
while(!priorityQueue.isEmpty()){
Edge curEdge=priorityQueue.poll();//弹出最小的一个边
Node toNode=curEdge.to;
if(!nodeSet.contains(toNode)){
result.add(curEdge);//确定该条边可以解锁一个新的点
nodeSet.add(toNode);//解锁新的点要加入到nodeSet中
for(Edge edge:toNode.edges){
priorityQueue.add(edge);//解锁该点相关的边，会有重复的边进入，但是有nodeSet
}
}
}
}
}
return result;
}
6.Dijkstra算法（没有权值和为负的环，一定要规定出发点）
从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra
思路：首先初始化一张表，记录出发点到所有点的初始距离；看出发点到所有点的距离，当某一个点的距离变小时更新表。
代码后续补
