目录

一、图（Graph）

1.概念

2.有向图

 3.出度、入度

4.无向图

5.简单图、多重图

6.无向完全图

 7.有向完全图

8.有权图

9.连通图

 10.连通分量（无向图）

 11.强连通图（有向图）

12.强连通分量

 13.邻接矩阵

1.基本概念

2.邻接矩阵--有权图

14.邻接表

 1.基本概念 

 2.有权图

15.图的实现

图的基础接口

 添加边addEdge

图的总边（edgesSize）

图的点的接口

图的边的接口

删除边removeEdge

完整代码

二、图的遍历

新的图接口

三、广度优先搜索（BFS）

1.图解

​编辑 2.思路

3.代码实现

四、深度优先搜索（DFS）

1.前序遍历

 2.图解

3.递归实现

 4.通过栈-----非递归实现

1）步骤

2)图解

 3）代码实现

五、AOV网（Activity On Vertex Network）

六、拓扑排序（Topological Sort） 

1.简介

 2.思路

3.代码实现

一、图（Graph）

1.概念

2.有向图

 3.出度、入度

4.无向图

 

5.简单图、多重图

6.无向完全图

 7.有向完全图

8.有权图

 

9.连通图

 10.连通分量（无向图）

 11.强连通图（有向图）

12.强连通分量

 13.邻接矩阵

1.基本概念

2.邻接矩阵--有权图

 

14.邻接表

 1.基本概念 

 2.有权图

15.图的实现

图的基础接口

package graph;public interface Graph<V,E> {
//    边的数量int edgesSize();
//    顶点数量int verticesSize();//    添加顶点void addVertex(V v);
//    添加边（无权值）void addEdge(V from,V to);
//    添加边（有权值）void addEdge(V from,V to,E weight);//    删除顶点void removeVertex(V v);
//    删除边void removeEdge(V from,V to);interface vertexVisitor<V>{boolean visit(V v);}void print();
}

 添加边addEdge

    /*** 添加无权值的边* @param from* @param to*/@Overridepublic void addEdge(V from, V to) {addEdge(from,to,null);}/*** 添加有权值的边* @param from* @param to* @param weight*/@Overridepublic void addEdge(V from, V to, E weight) {//根据传入的参数from找到出发点，如果不存在则创建Vertex<V,E> fromVertex=vertices.get(from);if (fromVertex==null){fromVertex=new Vertex<>(from);//将点和对应的点关系存入vertices.put(from,fromVertex);}//根据传入参数to找到终点，如果找不到则创建Vertex<V,E> toVertex=vertices.get(to);if (toVertex==null){toVertex=new Vertex<>(to);//将点和对应的点关系存入vertices.put(to,toVertex);}//根据出发点和终点，创建边Edge<V,E> edge=new Edge<>(fromVertex,toVertex);edge.weight=weight;//有权值加上，无权值则为null//不管原来是否存在，都先删除，在添加进去if (fromVertex.outEdges.contains(edge)){ //说明存在toVertex.inEdges.remove(edge);//在整个图中的边减少edges.remove(edge);}fromVertex.outEdges.add(edge);toVertex.inEdges.add(edge);//在整个图中的边增加edges.add(edge);}

图的总边（edgesSize）

    public int edgesSize() {return edges.size();}

图的点的接口

    /*** 顶点* @param <V>* @param <E>*/private static class Vertex<V,E>{//顶点值V value;Set<Edge<V,E>> inEdges=new HashSet<>();Set<Edge<V,E>> outEdges=new HashSet<>();public Vertex(V value) {this.value = value;}/*** 比较两个顶点是否相等* @param obj* @return*/@Overridepublic boolean equals(Object obj) {return Objects.equals(value,((Vertex<V,E>)obj).value);}@Overridepublic int hashCode() {return value==null ? 0: value.hashCode();}}

图的边的接口

    /*** 边* @param <V>* @param <E>*/private static class Edge<V,E> {Vertex<V,E> from;Vertex<V,E> to;E weight;public Edge(Vertex<V, E> from, Vertex<V, E> to) {this.from = from;this.to = to;}/*** 判断两条边是否相同* @param obj* @return*/@Overridepublic boolean equals(Object obj) {Edge<V,E> edge=(Edge<V, E>) obj;return Objects.equals(from,edge.from) && Objects.equals(to,edge.to);}/*** 如果equals的结果是true说明一样，则hashcode值也一样* @return*/@Overridepublic int hashCode() {return from.hashCode()+to.hashCode();}}

删除边removeEdge

    /*** 删除边* @param from* @param to*/@Overridepublic void removeEdge(V from, V to) {
//        根据传入的from获得起点，不存在则不需要删除Vertex<V,E> fromVertex=vertices.get(from);if (fromVertex ==null){return;}
//        根据传入的to找到终点，不存在则不需要删除Vertex<V,E> toVertex=vertices.get(to);if (toVertex==null) return;//        根据起点和终点获得边，然后删除Edge<V,E> edge=new Edge<>(fromVertex,toVertex);if (fromVertex.outEdges.remove(edge)){ //表示删除成功toVertex.inEdges.remove(edge);edges.remove(edge);}}

完整代码

package graph;import java.util.*;public class ListGraph<V,E> implements Graph<V,E>{// 传入的V与顶点类Vertex的映射【要记录该点的出入是inEdges还是outEdges】private Map<V, Vertex<V, E>> vertices = new HashMap<>();// 边的Set集合private Set<Edge<V, E>> edges = new HashSet<>();public void print(){System.out.println("[顶点]-------------------");vertices.forEach((V v, Vertex<V, E> vertex) -> {System.out.println(v);System.out.println("out-----------");System.out.println(vertex.outEdges);System.out.println("int-----------");System.out.println(vertex.inEdges);});System.out.println("[边]-------------------");edges.forEach((Edge<V, E> edge) -> {System.out.println(edge);});}@Overridepublic int edgesSize() {return edges.size();}@Overridepublic int verticesSize() {return vertices.size();}@Overridepublic void addVertex(V v) {
//        put(key,value)vertices.put(v,new Vertex<>(v));}/*** 添加无权值的边* @param from* @param to*/@Overridepublic void addEdge(V from, V to) {addEdge(from,to,null);}/*** 添加有权值的边* @param from* @param to* @param weight*/@Overridepublic void addEdge(V from, V to, E weight) {//根据传入的参数from找到出发点，如果不存在则创建Vertex<V,E> fromVertex=vertices.get(from);if (fromVertex==null){fromVertex=new Vertex<>(from);//将点和对应的点关系存入vertices.put(from,fromVertex);}//根据传入参数to找到终点，如果找不到则创建Vertex<V,E> toVertex=vertices.get(to);if (toVertex==null){toVertex=new Vertex<>(to);//将点和对应的点关系存入vertices.put(to,toVertex);}//根据出发点和终点，创建边Edge<V,E> edge=new Edge<>(fromVertex,toVertex);edge.weight=weight;//有权值加上，无权值则为null//不管原来是否存在，都先删除，在添加进去if (fromVertex.outEdges.contains(edge)){ //说明存在toVertex.inEdges.remove(edge);//在整个图中的边减少edges.remove(edge);}fromVertex.outEdges.add(edge);toVertex.inEdges.add(edge);//在整个图中的边增加edges.add(edge);}/*** 删除点* @param v*/@Overridepublic void removeVertex(V v) {//根据传入的值找到点并且删除，不存在则不做操作Vertex<V,E> vertex=vertices.remove(v);if (vertex==null) return;
//        迭代器遍历集合vertex.outEdges，删除所有从该点出去的边
//        iterator.hasNext():相当于i++for (Iterator<Edge<V,E>> iterator = vertex.inEdges.iterator();iterator.hasNext();){Edge<V,E> edge=iterator.next();//遍历从该点出去的边edge.to.inEdges.remove(edge);//获取终点进入的边，并从中删除遍历到的边//这个remove方法是将当前的这个边删除iterator.remove();//将当前遍历到当前遍历到的元素edge从集合vertex.outEdges中删除edges.remove(edge);}// 迭代器遍历集合vertex.inEdges, 删除所有进入该点的边for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {Edge<V, E> edge = iterator.next(); // 遍历到的进入该点的边edge.from.outEdges.remove(edge); // 获取起点出去的边,并从中删除遍历到的边iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉edges.remove(edge);}}/*** 删除边* @param from* @param to*/@Overridepublic void removeEdge(V from, V to) {
//        根据传入的from获得起点，不存在则不需要删除Vertex<V,E> fromVertex=vertices.get(from);if (fromVertex ==null){return;}
//        根据传入的to找到终点，不存在则不需要删除Vertex<V,E> toVertex=vertices.get(to);if (toVertex==null) return;//        根据起点和终点获得边，然后删除Edge<V,E> edge=new Edge<>(fromVertex,toVertex);if (fromVertex.outEdges.remove(edge)){ //表示删除成功toVertex.inEdges.remove(edge);edges.remove(edge);}}/*** 顶点* @param <V>* @param <E>*/private static class Vertex<V,E>{//顶点值V value;Set<Edge<V,E>> inEdges=new HashSet<>();Set<Edge<V,E>> outEdges=new HashSet<>();public Vertex(V value) {this.value = value;}/*** 比较两个顶点是否相等* @param obj* @return*/@Overridepublic boolean equals(Object obj) {return Objects.equals(value,((Vertex<V,E>)obj).value);}@Overridepublic int hashCode() {return value==null ? 0: value.hashCode();}}/*** 边* @param <V>* @param <E>*/private static class Edge<V,E> {Vertex<V,E> from;Vertex<V,E> to;E weight;public Edge(Vertex<V, E> from, Vertex<V, E> to) {this.from = from;this.to = to;}/*** 判断两条边是否相同* @param obj* @return*/@Overridepublic boolean equals(Object obj) {Edge<V,E> edge=(Edge<V, E>) obj;return Objects.equals(from,edge.from) && Objects.equals(to,edge.to);}/*** 如果equals的结果是true说明一样，则hashcode值也一样* @return*/@Overridepublic int hashCode() {return from.hashCode()+to.hashCode();}}
}

二、图的遍历

图的遍历

从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次
图有2种常见的遍历方式（有向图、无向图都适用）

• 广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索。
• 深度优先搜索（Depth First Search，DFS）

发明“深度优先搜索”算法的2位科学家在1986年共同获得计算机领域的最高奖：图灵奖。

新的图接口

package graph;import java.util.List;
import java.util.Set;public interface Graph<V,E> {
//    边的数量int edgesSize();
//    顶点数量int verticesSize();//    添加顶点void addVertex(V v);
//    添加边（无权值）void addEdge(V from,V to);
//    添加边（有权值）void addEdge(V from,V to,E weight);//    删除顶点void removeVertex(V v);
//    删除边void removeEdge(V from,V to);void print();void bfs(V begin, vertexVisitor<V> visitor); // 广度优先搜索/*** 非递归版的深度优先搜索* @param begin* @param visitor*/void dfs(V begin, vertexVisitor<V> visitor);List<V> topologicalSort(); // 拓扑排序interface vertexVisitor<V>{boolean visit(V v);}
}

三、广度优先搜索（BFS）

1.图解

之前所学的二叉树层序遍历就是一种广度优先搜索。

注：BFS结果不唯一。

经历一层可以访问到的

 2.思路

将该点从队列取出来，然后再将其所子节点依次放入队列

从某个点开始，将它可以到达的点放入队列，如果已经访问过则跳过，然后从队列中取出点重复该过程。

第一层：假设从点A开始，它可以到达B、F，则将B、F入队。
此时队列中元素 [B、F]
第二层：队头B出队，B可以到达C、I、G，将C、I、G入队。
此时队列中元素 [F、C、I、G]
第三层：队头F出队，F可以到达G、E，但G已访问过，将E入队。
此时队列中元素 [C、I、G、E]
第四层：队头C出队，C可以到达I、D，但I已访问过，将D入队。
此时队列中元素 [I、G、E、D]
第五层：队头I出队，I可以到达D，但D已访问过，不执行操作。
此时队列中元素 [G、E、D]
第六层：队头G出队，G可以到达D、H，但D已访问过，将H入队。
此时队列中元素 [E、D、H]
第七层：队头E出队，E可以到达D、H、F，都访问过，不执行操作。
此时队列中元素 [D、H]
第八层：队头D出队，D可以到达C、H、E，都访问过，不执行操作。
此时队列中元素 [H]
第九层：队头H出队，H可以到达D、G、E，都访问过，不执行操作。
此时队列中元素 []
队列为空，广度优先搜索结束。

3.代码实现

    /*** 广度优先搜索:BFS* @param begin* @param visitor*/@Overridepublic void bfs(V begin, vertexVisitor<V> visitor) {if (visitor ==null) return;//根据传入的值begin找到顶点Vertex<V,E> beginVertex=vertices.get(begin);//该顶点不存在，不做操作if (beginVertex==null) return;//存放已经访问过的节点//因为如果不存放，则遍历到下一个顶点的时候，会将刚刚出队列的数值再一次放入Set<Vertex<V,E>> visitedVertices=new HashSet<>();//临时存放Queue<Vertex<V,E>> queue=new LinkedList<>();queue.offer(beginVertex); //元素入队//将已经加入过队列的元素标记一下visitedVertices.add(beginVertex);//思考参考二叉树层次遍历，队列存放每一层的顶点，用集合记录已经访问过的点while (!queue.isEmpty()){//从队列中取出第一个顶点Vertex<V,E> vertex=queue.poll();if (visitor.visit(vertex.value)) return;//遍历【从队列中取出的顶点】的出去的边，将【这些边的终点】入队，并且标记为已经访问过for (Edge<V,E> edge:vertex.outEdges){//如果集合中已经记录该顶点，说明已经访问过，跳过进行下一轮if (visitedVertices.contains(edge.to)) continue;queue.offer(edge.to);visitedVertices.add(edge.to);}}}

四、深度优先搜索（DFS）

之前所学的二叉树前序遍历就是一种深度优先搜索。

注：DFS结果不唯一。

1.前序遍历

 2.图解

 

3.递归实现

    /*** 递归实现--->深度优先遍历：DFS* @param begin* @param visitedVertices 已经访问过的节点*//*** 递归实现深度优先搜索DFS*/public void dfs(V begin) {Vertex<V, E> beginVertex = vertices.get(begin); // 根据传入的值获取顶点if (beginVertex == null) return; // 顶点不存在则不执行操作dfs(beginVertex, new HashSet<>()); // 传入的集合,用来记录访问过的顶点}private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> vistedVertices){System.out.println(vertex.value);vistedVertices.add(vertex);for(Edge<V, E> edge : vertex.outEdges){if(vistedVertices.contains(edge.to)) continue;//dfs会自己后退dfs(edge.to, vistedVertices);}}

 4.通过栈-----非递归实现

1）步骤

1.从outEdge中选择一条边

2.将选择边的from和to边，按顺序入栈【先入from再入to】

3.打印选择边的to

4.将to边添加到已经访问的范围中

5.break

2)图解

 3）代码实现

    /*** 非递归版（通过栈实现）：深度优先搜索（DFS）* @param*/@Overridepublic void dfs(V begin, vertexVisitor<V> visitor) {if (visitor ==null) return;//查看该点是否存在Vertex<V,E> beginVertex=vertices.get(begin);if (begin==null) return;//创建一个set存放已经访问过的节点Set<Vertex<V,E>> visitedVertices=new HashSet<>();//创建一个栈临时存放Stack<Vertex<V,E>> stack=new Stack<>();//先访问起点stack.push(beginVertex);visitedVertices.add(beginVertex);//如果该节点已经访问过，则不再放入if (visitor.visit(begin)) return;while (!stack.isEmpty()){ //如果栈不为空Vertex<V,E> vertex=stack.pop();for (Edge<V,E> edge :vertex.outEdges){ //访问出发点的每一条边if (visitedVertices.contains(edge.to)) continue; //表示这条边已经访问过//找了一条适合且未遍历过的边stack.push(edge.from);//将出发点加入栈中stack.push(edge.to);//将出度点加入栈中//将加入栈中的节点加入已经访问过发范围中visitedVertices.add(edge.to);if (visitor.visit(edge.to.value)) return;break;}}}

五、AOV网（Activity On Vertex Network）

一项大的工程常被分为多个小的子工

子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始。
在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）

以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网。【有很强的依赖关系】
标准的AOV网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）

六、拓扑排序（Topological Sort） 

1.简介

前驱活动：有向边起点的活动称为终点的前驱活动

• 只有当一个活动的前驱全部都完成后，这个活动才能进行

后继活动：有向边终点的活动称为起点的后继活动

 2.思路

可以使用卡恩算法（Kahn于1962年提出）完成拓扑排序。

假设 L 是存放拓扑排序结果的列表：

• ① 把所有入度为 0 的顶点放入 queue 中，然后把这些顶点从图中去掉，放入list中
• ② 然后找到已经从queue中移除的入度为0的节点的下一个节点，将下一个节点的入度-1，如果-1后，入度为0，则直接加入queue
• ③ 重复操作 ①，直到找不到入度为 0 的顶点
• 如果此时 L 中的元素个数和顶点总数相同，说明拓扑排序完成
• 如果此时 L 中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序

3.代码实现

    /*** 拓扑排序* @return*/@Overridepublic List<V> topologicalSort() {List<V> list = new ArrayList<>();Queue<Vertex<V, E>> queue = new LinkedList<>();Map<Vertex<V, E>, Integer> ins = new HashMap<>();// 初始化（将度为0的节点放入队列）vertices.forEach((V v, Vertex<V, E> vertex) -> {int indegree = vertex.inEdges.size(); // 入度if(indegree == 0) { // 入度为0，放入队列queue.offer(vertex);} else { // 入度不为0，用map记录它的入度ins.put(vertex, indegree);}});while(!queue.isEmpty()){ // 从队列中取节点//取出队列中的第一个元素Vertex<V, E> vertex = queue.poll();list.add(vertex.value); // 放入返回结果中//遍历取出的节点的出度边for (Edge<V, E> edge : vertex.outEdges){// 队列中取出节点所通向节点的入度int toIndegree = ins.get(edge.to) - 1;if(toIndegree == 0) { // 入度为0，放入队列queue.offer(edge.to);} else { // 入度不为0，用map记录它的入度ins.put(edge.to, toIndegree);}}}return list;}