有向无环图路==路径规划

有向无环图路==路径规划

一道面试题 

我们有⼀一个有向⽆无环图，权重在节点上。
需求：从⼀一个起点开始，找到⼀一条节点权重之和最⼤大的最优路路径。
输⼊入: n个节点，m个路路径，起点
输出: 最优路路径的权重值之和
举例例:
3个节点与权重: A=1, B=2, C=2
3条路路径: A->B, B->C, A->C
起点: A
输出: 5 (最优路路径是 A->B->C ， 权重之和是 1+2+2=5)
请考虑算法效率优化，考虑异常情况（⽐比如输⼊入的图有环路路）要避免死循环或者崩溃。

实现如下：

背包实现 

import java.util.Iterator;// 定义一个背包集合，支持泛型，支持迭代
@SuppressWarnings("all")
public class Bag<Item> implements Iterable<Item> {private class BagNode<Item> {Item item;BagNode next;}BagNode head;int size;@Overridepublic Iterator<Item> iterator() {return new Iterator<Item>() {BagNode node = head;@Overridepublic boolean hasNext() { != null;}@Overridepublic Item next() {Item item = (Item) node.item;node = ;return item;}};}public Bag() {head = new BagNode();size = 0;}// 往前插入public void add(Item item) {BagNode temp = new BagNode();// 以下两行代码一定要声明，不可直接使用temp = head，那样temp赋值的是head的引用，对head的所有修改会直接同步到temp，temp就不具备缓存的功能，引发bug。。 = ;temp.item = head.item;head.item =  = temp;size++;}public boolean isEmpty() {return size == 0;}public int size() {return this.size;}}

节点数据封装类 

public class BagData {private Integer index;private String nodeName;private Integer nodeValue;public BagData(){}public BagData(Integer index,String nodeName, Integer nodeValue) {super();this.index = deName = deValue = nodeValue;}public String getNodeName() {return nodeName;}public void setNodeName(String nodeName) {deName = nodeName;}public Integer getNodeValue() {return nodeValue;}public void setNodeValue(Integer nodeValue) {deValue = nodeValue;}public Integer getIndex() {return index;}public void setIndex(Integer index) {this.index = index;}@Overridepublic String toString() {return "BagData [index=" + index + ", nodeName=" + nodeName + ", nodeValue=" + nodeValue + "]";}}

图的实现 

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;public class DigraphV2 {private final int V;// 顶点总数，定义final，第一次初始化以后不可更改。private int E;// 边总数private Bag<BagData>[] adj;// {邻接表}顶点为数组下标，值为当前下标为顶点值所连通的顶点个数。private Map<Integer,BagData> points;// = new HashMap<>(); public DigraphV2(int v) {points = new HashMap<>(); this.V = v;this.E = 0;adj = new Bag[V];for (int i = 0; i < V; i++) {adj[i] = new Bag<BagData>();}}public int V() {return this.V;}public int E() {return this.E;}public Map<Integer, BagData> getPoints() {return points;}/*** v和w是两个顶点，中间加一条边，增加稠密度。** @param v 大V是顶点总数，v是顶点值，所以并v不存在大小限制* @param w 同上。*/public void addEdge(BagData v, BagData w) {if(!Index()))points.Index(), v);if(!Index()))points.Index(), w);Index()].add(w);E++;}/*** 返回一个顶点的连通顶点集合的迭代器** @param v* @return Bag本身就是迭代器，所以返回该顶点的连通顶点集合Bag即可。*/public Iterable<BagData> adj(int v) {return adj[v];}/*** 将图中所有方向反转** @return 返回一个图将所有方向反转后的副本*/public DigraphV2 reverse() {DigraphV2 R = new DigraphV2(V);for (int v = 0; v < V; v++) {for (BagData w : adj[v]) {// 遍历原图中跟v顶点连通的顶点w。R.addEdge(w, (v));}}return R;}/*** 按照邻接表数组结构输出有向图内容** @return*/public String toString() {String s = points.size() + " vertices, " + E + " edgesn";for (int v = 0; v < points.size(); v++) {s += (v).toString() + ": ";for (BagData w : this.adj(v)) {s += w.toString();}s += "n";}return s;}public String getWeightPath() {Map<Integer,String> weightPaths = new HashMap<>();for (int v = 0; v < points.size(); v++) {int weights = 0;String path = "";weights += (v).getNodeValue();path += (v).getNodeName();path += "->";Stack<BagData> temp = new Stack<>();for (BagData w : this.adj(v)) {temp.push(w);}for(;;){if(temp.isEmpty())break;BagData w = temp.pop();weights += w.getNodeValue();path += w.getNodeName();path += "->";}path = path.substring(0, path.length()-2);weightPaths.put(weights, path);}Map.Entry<Integer, String> result = Set().stream().max((e1,e2)-&Key()Key())).get();return "path = "&#Value()+"  weight = "&#Key();}
}

有环无向图的实现 以及路径权重计算 

import java.util.Stack;public class DirectedCycleV2 {private boolean[] marked;// 以顶点为索引，值代表了该顶点是否标记过（是否可达）private Stack<Integer> cycle; // 用来存储有向环顶点。// *****重点理解这里start****private int[] edgeTo;// edgeTo[0]=1代表顶点1->0, to 0的顶点为1。// *****重点理解这里end****private boolean[] onStack;// 顶点为索引，值为该顶点是否参与dfs递归，参与为truepublic DirectedCycleV2(DigraphV2 digraph) {// 初始化成员变量marked = new boolean[digraph.V()];onStack = new boolean[digraph.V()];edgeTo = new int[digraph.V()];cycle = null;// 检查是否有环for (int v = 0; v < digraph.V(); v++) {dfs(digraph, v);}}public String getWeightPath(DigraphV2 d){String result = "";if (this.hasCycle()) {System.out.println("输入错误，图是有环路的！");} else {result = d.getWeightPath();}return result;}private void dfs(DigraphV2 digraph, int v) {onStack[v] = true;// 递归开始，顶点上栈marked[v] = true;for (BagData w : digraph.adj(v)) {// 遍历一条边，v-> w// 终止条件：找到有向环if (hasCycle()) return;// 使用onStack标志位来记录有效路径上的点，如果w在栈上，说明w在前面当了出发点，if (!Index()]) {Index()] = v;// to w的顶点为vdfs(digraph, w.getIndex());} else if (Index()]) {// 如果指到了已标记的顶点，且该顶点递归栈上。（栈上都是出发点，而找到了已标记的顶点是终点，说明出发点和终点相同了。）cycle = new Stack<Integer>();for (int x = v; x != w.getIndex(); x = edgeTo[x]) {//起点在第一次循环中已经push了，不要重复cycle.push(x);// 将由v出发，w结束的环上中间的结点遍历push到cycle中。}cycle.Index());// push终点}}onStack[v] = false;// 当递归开始结算退出时，顶点下栈。}public boolean hasCycle() {return cycle != null;}public Iterable<Integer> cycle() {return cycle;}public static void main(String[] args) {DigraphV2 d = new DigraphV2(3);BagData A = new BagData(0 , "A" , 1);BagData B = new BagData(1 , "B" , 2);BagData C = new BagData(2 , "C" , 2);d.addEdge(A, B);d.addEdge(B, C);d.addEdge(A, C);d.addEdge(C, A);DirectedCycleV2 directedCycle = new DirectedCycleV2(d);String result = WeightPath(d);System.out.println(result);}
}