《算法》学习笔记（4）—— 图的算法
一：图的连通性（一）：一个点1：点的连通问题：判断点A与点B之间是否连通，以及与点A连通的顶点个数APISearch(Graph g,int s)：确定点sboolean match(int v)：判断点v和点s是否连通int count()：与s的连通顶点个数实现1：union-found算法2：图的DFS深度遍历算法//DFSpublic void ...
·
一：图的连通性
（一）：一个点
1：点的连通问题：
判断点A与点B之间是否连通，以及与点A连通的顶点个数
API
- Search(Graph g,int s)：确定点s
- boolean match(int v)：判断点v和点s是否连通
- int count()：与s的连通顶点个数
实现
1：union-found算法
2：图的DFS深度遍历算法
//DFS
public void dfs(T vertex){
mark.put(vertex,true); //标记已经到达的顶点
System.out.printf("%s ",vertex);
count++;
for (T ver:
graph.adjoinVertexs(vertex)) {
if (mark.get(ver) == null || !mark.get(ver)) //不断遍历顶点的邻接顶点，直到标记则返回继续寻找
dfs(ver);
}
}
//判断是否连接
public boolean match(T vertex){
if (mark.get(vertex) == null)
return false;
return mark.get(vertex);
}
//连接个数
public int getCount() {
return count;
}
2：连通的两个点的路径问题
判断顶点A和顶点B之间是否存在路径，（也就是第一个的连通性问题）并获取路径。
API
- Paths(Graph g,int s)：寻找图中起点为s的路径
- boolean hasPath(int v)：判断顶点s到顶点v是否存在路径
- Iterable pathTo(int v)：获取s到v的路径
实现：图的深度遍历算法
//DFS
public void dfs(T vertex){
mark.put(vertex,true); //标记已经到达的顶点
count++;
for (T ver: graph.adjoinVertexs(vertex)) { //递归，从顶点开始直到终点，不断加入递归栈
if (mark.get(ver) == null || !mark.get(ver)) //不断遍历顶点的邻接顶点，直到标记则返回继续寻找
{
paths.put(vertex,ver); //记录路径
dfs(ver);
}
}
}
public boolean hasPath(T vertex){
return match(vertex);
}
//已知顶点到另一顶点的路径
public Iterable<T> getPath(T vertex){
if(!hasPath(vertex))
return null;
LinkedQueue<T> queue = new LinkedQueue<>();
T temp = origin;
while (temp != vertex && paths.get(temp) != null) //从起点开始找终点
{
queue.enQueue(temp);
temp = paths.get(temp);
}
queue.enQueue(vertex);
return queue;
}
3：连通的两个点的最短路径
判断顶点A和顶点B之间是否存在路径，并获取最短的路径。
涉及最优解的问题使用广度遍历
//BFS
public void bfs(T vertex){
LinkedQueue<T> queue = new LinkedQueue<>();
queue.enQueue(vertex);
mark.put(vertex,true); //标记已经到达的顶点
while (!queue.isEmpty()){
vertex = queue.deQueue().getData(); //排除已经到达的顶点
count++;
for (T ver: graph.adjoinVertexs(vertex)) {
if (mark.get(ver) == null || !mark.get(ver)) //不断遍历顶点的邻接顶点，直到标记则返回继续寻找
{
queue.enQueue(ver);
paths.put(vertex,ver); //记录路径
mark.put(ver,true); //标记顶点
}
}
}
}
（二）：多个点
1：图的连通分量问题
找出图的所有连通分量
API
- boolean connected(int v,int w)：判断v和w是否连通
- int count()：连通分量数
实现
for (int i = 0; i < graph.getVertexSize(); i++) {
this.origin = graph.getVertex(i);
if (match(origin))
continue;
dfs(origin);
size++;
}
//两个顶点之间是否连通
public boolean isConnected(T from,T to){
if (id.get(from) == null || id.get(to) == null)
return false;
return id.get(from).equals(id.get(to));
}
//图的连通分量个数
public int getSize() {
return size;
}
2：图的是否成环
判断图是否是成环
API
- isCircle：是否是环
- circle：记录环
实现
//判断是否成环
public boolean isCircle(T vertex){
dfs(vertex,vertex);
return circle;
}
//DFS
public void findCircle(T from,T to){
mark.put(from,true); //标记已经到达的顶点
count++; //记录某一个顶点的连通顶点个数
circleSize++; //用于记录无向图的遍历顶点个数
id.put(from,size);
for (T ver: graph.adjoinVertexs(from)) { //递归，从顶点开始直到终点，不断加入递归栈
if (mark.get(ver) == null || !mark.get(ver)) //不断遍历顶点的邻接顶点，直到标记则返回继续寻找
{
paths.put(from,ver); //记录路径
findCircle(ver,to);
circleSize --;
}
else if (!ver.equals(from) && ver.equals(to))
if (graph.isDirection() || circleSize != 2) //跳过无向图的第二个顶点
{
circle = true;
T temp = to;
while (temp != from && paths.get(temp) != null) //从起点开始找终点
{
queue.enQueue(temp);
temp = paths.get(temp);
}
queue.enQueue(from);
queue.enQueue(to);
return;
}
}
}
3：是否是二分图
使用两种颜色标记结点，但是任一边的两个顶点的颜色都不同
API
- isTwoColor：是否是二分图
- color：记录颜色
实现
//二分图
public boolean isTowCircle(){
for (int i = 0; i < graph.getVertexSize(); i++) {
this.origin = graph.getVertex(i);
if (match(origin))
continue;
setColor(origin);
size++;
}
this.origin = graph.getVertex(0);
return twoColor;
}
//DFS
public void setColor(T vertex){
mark.put(vertex,true);
count++;
id.put(vertex,size);
for (T ver: graph.adjoinVertexs(vertex)) {
if (mark.get(ver) == null || !mark.get(ver))
{
boolean color = colors.get(vertex);
colors.put(ver,!color); //与另一个顶点不同颜色
paths.put(vertex,ver); //记录路径
dfs(ver);
}
//如果另一个顶点已经染过颜色，看看两个顶点颜色是否相同
else if (colors.get(ver) == colors.get(vertex))
twoColor = false;
}
}
（三）：强连通性
- 对有向图逆向处理，进行拓扑排序。
由于拓扑排序可以让图从优先级高到优先级低排序，而图是反向的，这样就保证了在原图中优先级低的节点会在优先级高的之前先访问，从而可以保证同一个强连通分量会一起访问 - 根据顺序进行深度遍历
//有向图的强连通性
public void superUnion(){
//对反向图进行拓扑排序
DeathFirstSearch<T> search = new DeathFirstSearch<>(graph.reverse());
search.order();
//对排序后的顶点进行深度遍历
for (T key: search.reverse()) {
if (mark.get(key) == null || !mark.get(key))
{
dfs(key);
size++;
}
}
}
二：拓扑排序
将有向图的顶点排序，使得所有有向边均从前面的元素指向后面的元素
API：
- order：获取排序
- isDAG：判断是否是有向无环图
实现：
1：使用逆后序的栈进行排序
- 先判断是否成环
- 进行逆后序并输出
/**
* 拓扑排序
*/
public class ToPoLogical<T> {
//顺序
private Iterable<T> order;
//工具
private DeathFirstSearch<T> search;
public ToPoLogical(LinkedGraph<T> graph){
search = new DeathFirstSearch<>(graph);
//先判断是否是有向成环图
if (graph.isDirection() && !search.isCircle())
{
//获取逆向后序
search = new DeathFirstSearch<>(graph);
search.order();
order = search.reverse();
}
}
//获取排序
public Iterable<T> getOrder() {
return order;
}
//判断是否是有向无环图
public boolean isDAG(){
return order != null;
}
}
（1）：判断有向图是否成环
//判断是否成环
public boolean isCircle(){
for (int i = 0; i < graph.getVertexSize(); i++) {
if (circle)
break;
this.origin = graph.getVertex(i);
if (match(origin))
continue;
findCircle(origin,origin);
size++;
circleSize = 0;
}
this.origin = graph.getVertex(0);
return circle;
}
（2）：排序
//拓扑排序
public void order(){
for (int i = 0; i < graph.getVertexSize(); i++) {
this.origin = graph.getVertex(i);
if (match(origin))
continue;
getOrder(origin);
size++;
}
this.origin = graph.getVertex(0);
}
//遍历顺序
public void getOrder(T vertex){
preQueue.enQueue(vertex);
mark.put(vertex,true); //标记已经到达的顶点
for (T ver: graph.adjoinVertexs(vertex)) { //递归，从顶点开始直到终点，不断加入递归栈
if (mark.get(ver) == null || !mark.get(ver)) //不断遍历顶点的邻接顶点，直到标记则返回继续寻找
getOrder(ver);
}
postQueue.enQueue(vertex);
reversepostStack.push(vertex);
}
2：使用顶点队列进行拓扑排序
- 选择一个入度为0的顶点输出
- 删去此顶点，并删除以此顶点为头的弧
- 继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
/**
* 用队列实现拓扑排序
* @param <T>
*/
public class QueueTopoLogical<T> {
//记录顶点的入度
private ChainAddressST<T,Integer> inDegrees;
//顺序
private LinkedQueue<T> order;
public QueueTopoLogical(LinkedGraph<T> graph){
inDegrees = new ChainAddressST<>(graph.getVertexSize());
LinkedQueue<T> queue = new LinkedQueue<>();
order = new LinkedQueue<>();
//初始化各个顶点的入度
for (int i = 0; i < graph.getVertexSize(); i++) {
T vertex = graph.getVertex(i);
inDegrees.put(vertex,graph.inDegree(vertex));
}
//初始化起点队列
for (T key : graph.sources())
queue.enQueue(key);
while (!queue.isEmpty())
{
T vertex = queue.deQueue().getData();
order.enQueue(vertex);
//删除起点和以它为头的弧，如果有顶点入度为0，则加入队列
for (T key:
graph.adjoinVertexs(vertex)) {
if (key.equals(vertex))
continue;
int degree = inDegrees.get(key);
inDegrees.put(key,degree--);
if (degree == 0)
queue.enQueue(key);
}
}
//成环
if (order.getSize() != graph.getVertexSize())
order = null;
}
//获取排序
public Iterable<T> getOrder() {
return order;
}
//判断是否是有向无环图
public boolean isDAG(){
return order != null;
}
三：图的可达性
对于无向图，等价于图的连通性
对于有向图，如果两个顶点不是强连通的，可能从一个顶点可以到达另一个顶点。
- 先确定一个顶点的连通性
- 确定顶点是否连通
//有向图某两个顶点的可达性
public boolean reachable(T from,T to){
this.union(from);
return this.match(to);
}
//某一个顶点的连通性
public void union(T vertex){
this.origin = vertex;
dfs(vertex);
}
//已知一个顶点与其他顶点判断是否连接
public boolean match(T vertex){
if (mark.get(vertex) == null)
return false;
return mark.get(vertex);
}
四：图的最优解
1：最小生成树
API
- int power()：生成树的权值
- Iterable<> edges()：生成树的边集合
实现
1. Prim算法
一开始树只有一个顶点，检查顶点的所有邻接边，然后根据贪心算法，将一条横切边加入树中：
- 连接树中的顶点与不在树中的顶点
- 权值最小
每当加入一条边时，也就是加入一个新的顶点。同时新加入的顶点和原来顶点之间的边已经失效，否则会成环。然后继续检查新顶点。
（1）：延迟算法
每次都会加入顶点的全部邻接边，等到需要时再检查是不是无效边
/**
* 构造最小生成树
* @param <T>
*/
public class MinSearchTree_Prim<T> {
//最小生成树的权值
private double power;
//标记最小生成树的顶点是否访问
private ChainAddressST<T,Boolean> marked;
//记录最小生成树的边
private LinkedQueue<LinkNode<T>> edges;
//根据权值比较横切边
private HeapPQ<LinkNode<T>> pq;
public MinSearchTree_Prim(LinkedGraph<T> graph){
marked = new ChainAddressST<>(graph.getVertexSize());
edges = new LinkedQueue<>();
lazy(graph);
}
//延迟算法
public void lazy(LinkedGraph<T> graph){
//首先把第一个顶点加入优先队列，开始访问
T vertex = graph.getVertex(0);
pq = new HeapPQ<>(graph.outDegree(vertex),false);
visit(graph,vertex);
//开始构建树
while (!pq.isEmpty()) {
LinkNode<T> node = pq.delMaximum();
T to = node.getData();
T from = (T) node.getPrev().getData();
//如果边的两个顶点已经访问过，则这条边是无效边（会形成环），延迟算法先将他们跳过不处理
if (marked.get(to) != null && marked.get(from) != null && marked.get(from) && marked.get(to))
continue;
//如果不是无效边，就把权值最小的横切边加入树
edges.enQueue(node);
//继续找其他横切边
if (marked.get(to) == null || !marked.get(to))
visit(graph,to);
if (marked.get(from) == null || !marked.get(from))
visit(graph,from);
}
//计算权值
for (LinkNode<T> node:
edges) {
// System.out.println(node.getData());
power+=node.getPower();
}
}
//访问顶点，把连接这个 树中的顶点 和 其他不在树中的顶点 的边 作为横切边加入优先队列
private void visit(LinkedGraph<T> graph,T from){
//标记顶点，表示把它加入树
marked.put(from,true);
for (T to: graph.adjoinVertexs(graph.getVertex(graph.locateVertex(from)))) {
//如果顶点没有被访问过，也就是没有在树中，则加入
if (marked.get(to) == null || !marked.get(to))
pq.insert(graph.getEdge(from,to));
}
}
public Iterable<LinkNode<T>> getEdges() {
return edges;
}
public String getPower() {
return new DecimalFormat("#.00").format(power);
}
}
（2）：即时算法
每次只会加入顶点的所有邻接边中比原来的已知权值更小的边，不会加入无效边
/**
* 构造最小生成树
* @param <T>
*/
public class MinSearchTree_Prim_Quick<T extends Comparable<T>> {
//标记顶点是否被访问
private ChainAddressST<T,Boolean> marked;
//记录距离树最近的每条边，也就是连接索引的顶点A和对应值的顶点B的边
private ChainAddressST<T,T> edges;
//记录距离树最近边edges对应的权值
private ChainAddressST<T,Double> powers;
//记录横切边
private IndexPQ<LinkNode<Integer>> pq;
//最小生成树的权值
private double power;
//记录最小生成树的边
private LinkedQueue<LinkNode<T>> tree;
public MinSearchTree_Prim_Quick(STGraph<T> graph){
marked = new ChainAddressST<>(graph.graph().getVertexSize());
edges = new ChainAddressST<>(graph.graph().getVertexSize());
powers = new ChainAddressST<>(graph.graph().getVertexSize());
tree = new LinkedQueue<>();
for (int i = 0; i < graph.graph().getVertexSize(); i++) {
edges.put((T) graph.get(i),null);
}
for (int i = 0; i < graph.graph().getVertexSize(); i++) {
powers.put((T) graph.get(i),Double.MAX_VALUE);
}
pq = new IndexPQ<>(graph.graph().getVertexSize(),false);
quick(graph);
}
private void quick(STGraph<T> graph){
//添加第一个顶点
T vertex = graph.get(0);
int index = graph.index(vertex);
edges.put(vertex,vertex);
powers.put(vertex,0.0);
LinkNode<Integer> node = new LinkNode<>(index,0.0);
node.setPrev(new LinkNode(index));
pq.insert(index,node);
visit(graph,vertex);
//将最近的顶点加入树
while (!pq.isEmpty()){
//计算权值
if (pq.maximum().getPower() != 0)
{
power += pq.maximum().getPower();
LinkNode<T> min = new LinkNode<>(graph.get(pq.maximum().getData()));
min.setPrev(new LinkNode<>(graph.get((Integer) pq.maximum().getPrev().getData())));
tree.enQueue(min);
}
index = pq.delMaximum();
visit(graph,graph.get(index));
}
}
private void visit(STGraph<T> graph,T from){
int fromIndex = graph.index(from);
//标记顶点，表示把它加入树
marked.put(from,true);
for (int toIndex: graph.graph().adjoinVertexs(fromIndex)) {
//如果顶点没有被访问过，也就是没有在树中，则准备更新
T to = graph.get(toIndex);
if (marked.get(to) == null || !marked.get(to))
{
LinkNode<Integer> edge = graph.graph().getEdge(fromIndex,toIndex);
//边的权值比较小，需要更新边
if (powers.get(to) > edge.getPower())
{
edges.put(to,from);
powers.put(to,edge.getPower());
if (pq.contains(toIndex))
pq.change(toIndex,edge);
else
pq.insert(toIndex,edge);
}
}
}
}
public Iterable<LinkNode<T>> getEdges() {
return tree;
}
public String getPower() {
return new DecimalFormat("#.00").format(power);
}
public void printTree(){
for (LinkNode<T> edge: tree) {
System.out.printf("%s-%s ",edge.getPrev().getData(),edge.getData());
}
System.out.println();
}
}
2. Kruskal算法
一开始树没有边，检查图的所有边，然后根据贪心算法，将权值最小的边加入树中，
并且加入的边不会形成环，然后继续检查边。
/**
* 最小生成树
* @param <T>
*/
public class MinSearchTree_Kruskal<T extends Comparable> {
//最小生成树的权值
private double power;
//记录最小生成树的边
private LinkedQueue<LinkNode<T>> edges;
//根据权值比较横切边
private HeapPQ<LinkNode<Integer>> pq;
//检查是否是环
private UnionFound uf;
public MinSearchTree_Kruskal(STGraph graph){
edges = new LinkedQueue<>();
pq = new HeapPQ<>(graph.edgeSize(),false);
uf = new UnionFound(graph.vertexSize());
//将所有边加入队列
for (int fromIndex = 0; fromIndex < graph.vertexSize(); fromIndex++) {
for (int toIndex: graph.graph().adjoinVertexs(fromIndex)) {
if (toIndex == fromIndex)
continue;
pq.insert(graph.graph().getEdge(fromIndex,toIndex));
//避免同一条边加入两次
graph.graph().deleteEdge(toIndex,fromIndex);
}
}
//开始构建树
while (!pq.isEmpty() && edges.getSize() < graph.vertexSize() - 1){
LinkNode<Integer> edge = pq.delMaximum();
int toIndex = edge.getData();
int fromIndex = (Integer) edge.getPrev().getData();
//如果成环则跳过
if (uf.connect(fromIndex,toIndex))
continue;
//加入树
LinkNode<T> min = new LinkNode<>((T) graph.get(edge.getData()));
min.setPrev(new LinkNode<>(graph.get((Integer) pq.maximum().getPrev().getData())));
edges.enQueue(min);
power += edge.getPower();
uf.union(fromIndex,toIndex);
}
}
public String getPower() {
return new DecimalFormat("#.00").format(power);
}
public Iterable<LinkNode<T>> getEdges() {
return edges;
}
public void printTree(){
for (LinkNode<T> edge: edges) {
System.out.printf("%s-%s ",edge.getPrev().getData(),edge.getData());
}
System.out.println();
}
2：最短路径树（最长路径树，只需将权值取反即可）
通用算法：不断对顶点到每个顶点的边进行放松（找到距离该顶点更近的边，释放无效边），直到不存在有效边为止。
Dijkstra算法（Prim算法的有向定点版）：不断放松 最小权值路径 的边
- Prim：寻找离无向图的生成树更近的顶点
- Dijkstra：寻找离有向图的起点更近的顶点
特点：适用于正权值的无环情况
/**
* 最短路径
* @param <T>
*/
public class ShortPathTree_Dijkstra<T extends Comparable<T>> {
//记录距离树最近的每条边，也就是连接索引的顶点A和对应值的顶点B的边
private ChainAddressST<T,T> edges;
//记录距离树最近边edges对应的权值
private ChainAddressST<T,Double> powers;
//记录横切边
private IndexPQ<LinkNode<Integer>> pq;
//记录顶点
private T origin;
public ShortPathTree_Dijkstra(STGraph<T> graph,T origin){
this.origin = origin;
edges = new ChainAddressST<>(graph.graph().getVertexSize());
powers = new ChainAddressST<>(graph.graph().getVertexSize());
pq = new IndexPQ<>(graph.graph().getVertexSize(),false);
for (int i = 0; i < graph.graph().getVertexSize(); i++) {
edges.put((T) graph.get(i),null);
}
for (int i = 0; i < graph.graph().getVertexSize(); i++) {
powers.put((T) graph.get(i),Double.POSITIVE_INFINITY);
}
find(graph);
}
private void find(STGraph<T> graph){
//从起点开始
powers.put(origin,0.0);
edges.put(origin,origin);
int index = graph.index(origin);
LinkNode<Integer> node = new LinkNode<>(index,0.0);
node.setPrev(new LinkNode(index));
pq.insert(index,node);
relax(graph,origin);
//不断放松权值最小的边
while (!pq.isEmpty()) {
index = pq.delMaximum();
relax(graph,graph.get(index));
}
}
//对顶点的所有邻接边检查，松弛权值比较大的顶点，修正无效边
private void relax(STGraph graph, T from){
int fromIndex = graph.index(from);
for (int toIndex: graph.graph().adjoinVertexs(fromIndex)) {
if (fromIndex == toIndex)
continue;
T to = (T) graph.get(toIndex);
LinkNode<Integer> edge = graph.graph().getEdge(fromIndex,toIndex);
double newPower = powers.get(from) + edge.getPower();
//经过顶点from的边的路径权值比原来更小，把to的边的起点修改为from，把到to的权值修改为更小的
if (powers.get(to) > newPower)
{
powers.put(to,newPower);
edges.put(to,from);
edge.setPower(newPower);
if (pq.contains(toIndex))
pq.change(toIndex,edge);
else
pq.insert(toIndex,edge);
}
}
}
//获取到某一顶点的权值
public double getPower(T vertex){
return powers.get(vertex);
}
//能否到达某一顶点
public boolean havePathTo(T vertex){
return powers.get(vertex) != Double.POSITIVE_INFINITY;
}
//获取到某一顶点的路径
public Iterable<T> pathTo(T vertex){
if(!havePathTo(vertex))
return null;
LinkedStack<T> stack = new LinkedStack<>();
T temp = vertex;
while (temp != origin && edges.get(temp) != null) //从终点开始找起点
{
stack.push(temp);
temp = edges.get(temp);
}
stack.push(origin);
return stack;
}
public void print(T vertex){
if (!havePathTo(vertex))
{
System.out.println("DON'T HAVE PATH!");
return;
}
for (T key: pathTo(vertex)) {
if (key.equals(vertex))
System.out.printf("%s",key);
else
System.out.printf("%s->",key);
}
System.out.println();
}
}
拓扑排序算法：按照拓扑排序的顺序不断放松顶点
由于优先性高的顶点先释放，所以优先性高的顶点的最小权值不会再改变（不可能会有其他顶点指向优先性高的顶点），而优先性低的顶点的最小权值会不断减小。
特点：适用于负权值的无环情况
/**
* 最短路径
* @param <T>
*/
public class ShortPathTree_TopoLogical<T> {
//记录距离树最近的每条边，也就是连接索引的顶点A和对应值的顶点B的边
private ChainAddressST<T,T> edges;
//记录距离树最近边edges对应的权值
private ChainAddressST<T,Double> powers;
//记录顶点
private T origin;
private ToPoLogical_Stack<T> logical;
private LinkedGraph<T> graph;
public ShortPathTree_TopoLogical(LinkedGraph<T> graph,T origin){
this.origin = origin;
this.graph = graph;
logical = new ToPoLogical_Stack<>(graph);
edges = new ChainAddressST<>(graph.getVertexSize());
powers = new ChainAddressST<>(graph.getVertexSize());
for (int i = 0; i < graph.getVertexSize(); i++) {
edges.put(graph.getVertex(i),null);
}
for (int i = 0; i < graph.getVertexSize(); i++) {
powers.put((T) graph.getVertex(i),Double.POSITIVE_INFINITY);
}
if (!logical.isDAG())
return;
find();
}
private void find(){
//从起点开始
powers.put(origin,0.0);
edges.put(origin,origin);
//按照拓扑排序释放顶点
for (T vertex: logical.getOrder()) {
relax(vertex);
}
}
//对顶点的所有邻接边检查，松弛权值比较大的顶点，修正无效边
private void relax(T from){
for (T to: graph.adjoinVertexs(from)) {
if (to.equals(from))
continue;
LinkNode<T> edge = graph.getEdge(from,to);
double newPower = powers.get(from) + edge.getPower();
//经过顶点from的边的路径权值比原来更小，把to的边的起点修改为from，把到to的权值修改为更小的
if (powers.get(to) > newPower)
{
powers.put(to,newPower);
edges.put(to,from);
}
}
}
//获取到某一顶点的权值
public double getPower(T vertex){
return powers.get(vertex);
}
//能否到达某一顶点
public boolean havePathTo(T vertex){
return powers.get(vertex) != Double.POSITIVE_INFINITY;
}
//获取到某一顶点的路径
public Iterable<T> pathTo(T vertex){
if(!havePathTo(vertex))
return null;
LinkedStack<T> stack = new LinkedStack<>();
T temp = vertex;
while (temp != origin && edges.get(temp) != null) //从终点开始找起点
{
stack.push(temp);
temp = edges.get(temp);
}
stack.push(origin);
return stack;
}
public void print(T vertex){
if (!havePathTo(vertex))
{
System.out.println("DON'T HAVE PATH!");
return;
}
for (T key: pathTo(vertex)) {
if (key.equals(vertex))
System.out.printf("%s",key);
else
System.out.printf("%s->",key);
}
System.out.println();
}
}
Bellman-Ford算法：以任意顺序放松所有边，重复N次
把待放松顶点加入一个队列，从队列放松顶点的同时，将放松成功的另一个顶点加入队列，避免无效顶点被放松，也避免重复放松顶点。在遇到负权重边时相关的顶点会重新放松。
特点：适用于所有情况
- 对于无法到达的顶点：最短路径为正无穷（没有路径）
- 对于可以到达的顶点，如果位于负权重环上（环的总权重为负值），则最短路径为负无穷（只要绕着环永远可以得到更短的路径）
- 其他顶点，则具有最短路径
/**
* 最短路径
* @param <T>
*/
public class ShortPathTree_BellmanFold<T> {
//记录距离树最近的每条边，也就是连接索引的顶点A和对应值的顶点B的边
private ChainAddressST<T,T> edges;
//记录距离树最近边edges对应的权值
private ChainAddressST<T,Double> powers;
//起点
private T origin;
//待放松的顶点
private LinkedQueue<T> vertexs;
//判断顶点是否准备放松
private ChainAddressST<T,Boolean> inQueue;
//记录放松次数
private int count;
//是否有负权重环
private Iterable<T> cycle;
private LinkedGraph<T> graph;
public ShortPathTree_BellmanFold(LinkedGraph<T> graph,T origin){
this.graph = graph;
this.origin = origin;
edges = new ChainAddressST<>(graph.getVertexSize());
powers = new ChainAddressST<>(graph.getVertexSize());
inQueue = new ChainAddressST<>(graph.getVertexSize());
vertexs = new LinkedQueue<>();
for (int i = 0; i < graph.getVertexSize(); i++) {
edges.put(graph.getVertex(i),null);
}
for (int i = 0; i < graph.getVertexSize(); i++) {
powers.put((T) graph.getVertex(i),Double.POSITIVE_INFINITY);
}
find();
}
private void find(){
//从起点开始准备放松
powers.put(origin,0.0);
edges.put(origin,origin);
inQueue.put(origin,true);
vertexs.enQueue(origin);
//放松其他顶点，如果出现负权重环则结束
while (!vertexs.isEmpty() && !hasNegativeCycle())
{
T vertex = (T) vertexs.deQueue().getData();
//已经出队列了
inQueue.put(vertex,false);
relax(vertex);
}
}
//对顶点的所有邻接边检查，松弛权值比较大的顶点，修正无效边
private void relax(T from){
for (T to: graph.adjoinVertexs(from)) {
if (to.equals(from))
continue;
LinkNode<T> edge = graph.getEdge(from,to);
double newPower = powers.get(from) + edge.getPower();
//经过顶点from的边的路径权值比原来更小，把to的边的起点修改为from，把到to的权值修改为更小的
if (powers.get(to) > newPower)
{
powers.put(to,newPower);
edges.put(to,from);
//同时把还未准备放松的顶点加入队列
if (inQueue.get(to) == null || !inQueue.get(to))
{
vertexs.enQueue(to);
inQueue.put(to,true);
}
}
}
//看看是否放松V轮
if (count++ % graph.getVertexSize() == 0)
findNegativeCycle();
}
//负权重环，用当前生成树的路径构造新的图
private void findNegativeCycle(){
int vertexSize = graph.getVertexSize();
LinkedGraph<T> linkedGraph = new LinkedGraph<>(vertexSize,true,true);
for (int i = 0; i < vertexSize; i++) {
T to = graph.getVertex(i);
T from = edges.get(to);
if (from != null)
{
linkedGraph.insertVertex(from);
linkedGraph.insertVertex(to);
linkedGraph.putEdge(from,to,powers.get(to));
}
}
// linkedGraph.print();
DeathFirstSearch<T> search = new DeathFirstSearch<>(linkedGraph);
search.isCircle();
cycle = search.getCircle();
}
//是否有负权重环
public boolean hasNegativeCycle(){
return cycle != null;
}
public Iterable<T> getNegativeCycle() {
return cycle;
}
//获取到某一顶点的权值
public double getPower(T vertex){
return powers.get(vertex);
}
//能否到达某一顶点
public boolean havePathTo(T vertex){
return powers.get(vertex) != Double.POSITIVE_INFINITY;
}
//获取到某一顶点的路径
public Iterable<T> pathTo(T vertex){
if(!havePathTo(vertex))
return null;
LinkedStack<T> stack = new LinkedStack<>();
T temp = vertex;
while (temp != origin && edges.get(temp) != null) //从终点开始找起点
{
stack.push(temp);
temp = edges.get(temp);
}
stack.push(origin);
return stack;
}
public void print(T vertex){
if (!havePathTo(vertex))
{
System.out.println("DON'T HAVE PATH!");
return;
}
for (T key: pathTo(vertex)) {
if (key.equals(vertex))
System.out.printf("%s",key);
else
System.out.printf("%s->",key);
}
System.out.println();
}
}
3：最长路径树（关键路径树）：
解决并行调度问题
- 创建一副有向无环加权图，加入一个起点start和一个终点end和每个顶点的扩展顶点。每个任务（顶点）对应着一个任务起点和任务终点。
- 对于所有任务，任务进行的过程也就是边。添加一条从任务起点到任务终点的边，权值为任务所需时间。
- 对于所有任务，添加一条从起点start到任务起点的边和从任务终点到终点end的边，启动任务和结束任务无需花费时间所以权值为0
- 对于每个优先级限制，添加一条从任务终点指向下一任务起点的边，启动任务无需花费时间所以权值为0
/**
* 关键路径
*/
public class CriticalPath {
//图
private LinkedGraph graph;
//最长路径
private ShortPathTree_TopoLogical<Integer> logical;
//起点
private int start;
//终点
private int end;
//顶点个数
private int vertexSize;
public CriticalPath(int vertexSize,double[] times,int[][] conditions) {
//构造图
this.vertexSize = vertexSize;
graph = new LinkedGraph<>(2 * vertexSize + 2,true,true);
createGraph(times, conditions);
//找路径
logical = new ShortPathTree_TopoLogical(graph,start,false);
}
public void createGraph(double[] times,int[][] conditions){
//起点和终点
start = vertexSize * 2;
end = start + 1;
graph.insertVertex(start);
graph.insertVertex(end);
for (int i = 0; i < times.length; i++) {
//任务起点和任务终点
int vertex_start = i;
int vertex_end = vertex_start + vertexSize;
graph.insertVertex(vertex_start);
graph.insertVertex(vertex_end);
//完成任务所需时间
graph.putEdge(vertex_start,vertex_end,times[i]);
graph.putEdge(start,vertex_start,0);
graph.putEdge(vertex_end,end,0);
}
//优先限制级
for (int i = 0; i < conditions.length; i++) {
//上一个任务起点和任务终点
int from_start = i;
int from_end = from_start + vertexSize;
for (int j = 0; j < conditions[i].length; j++) {
//下一个任务起点
int to_start = conditions[i][j];
graph.putEdge(from_end,to_start,0);
}
}
}
public void find(){
System.out.println("Start Time:");
for (int i = 0; i < vertexSize; i++) {
System.out.printf("%4d: %5.2f\n",i,logical.getPower(i));
}
System.out.println("Finish Time:");
System.out.printf("%5.2f\n",logical.getPower(end));
}
}
- 起点到各个顶点的路径长度，就是任务开始 / 结束的下限（只能推迟不能提前，因为当前任务必须等前面的任务完成后才可以进行）。
- 起点到终点的最长路径长度就是整个任务的上限（任务最早完成的期限）
解决存在最后期限的并行调度问题
限制某个任务A必须在指定时间内开始，即指定和另一个任务B的开始时间的相对时间。
换句话说，任务B的开始时间不能太早，最好是在A指定时间前就开始。
- 与上面一样构造图
- 对于每个最后限制，添加一条从下一任务起点指向上一任务终点的负权值（指定时间）的边
- 对所有边的权重取反，求最长路径——也就是图的最短路径
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)