乐趣区

关于java:图算法系列之计算图中最短路径

jiezi

吐血整顿程序员必读书单：https://github.com/silently9527/ProgrammerBooks

微信公众号：贝塔学 Java

前言

在后面两篇中咱们通过深度优先搜寻能够从图中找出一条通过顶点 v 到顶点 w 的门路，然而深度优先搜寻与顶点的输出有很大的关系，找进去的门路也不肯定是最短的，通常状况下咱们很多时候须要找出图中的最短门路，比方：地图功能。这里咱们就须要应用到广度优先搜索算法

广度优先搜寻

仍然应用之前定义的寻找门路的 API

public class Paths {Paths(Graph graph, int s);
    
    boolean hasPathTo(int v); // 判断出从 s ->v 是否存在门路
    
    Iterable<Integer> pathTo(int v); // 如果存在门路，返回门路
}

在广度优先搜寻中，为了找出最短门路，咱们须要依照终点的程序来遍历所有的顶点，而不在是应用递归来实现；算法的思路：

  1. 应用队列来保留曾经被标记过然而邻接表还未被遍历过的顶点
  2. 取出队列中的下一个顶点 v 并标记它
  3. 将 v 相邻的所有未被标记的顶点退出到队列

在该算法中，为了保留门路，咱们仍然须要应用一个边的数组 edgeTo[]，用一颗父链树来示意根节点到所有连通顶点的最短门路。

public class BreadthFirstPaths {private boolean marked[];
    private int[] edgeTo;
    private int s;
    private Queue<Integer> queue = new LinkedListQueue<>();

    public BreadthFirstPaths(Graph graph, int s) {
        this.s = s;
        this.marked = new boolean[graph.V()];
        this.edgeTo = new int[graph.V()];

        bfs(graph, s);
    }

    private void bfs(Graph graph, int s) {this.marked[s] = true;
        this.queue.enqueue(s);
        while (!this.queue.isEmpty()) {Integer v = this.queue.dequeue();
            for (int w : graph.adj(v)) {if (!this.marked[w]) {this.marked[w] = true;
                    this.edgeTo[w] = v;
                    this.queue.enqueue(w);
                }
            }
        }


    }

    public boolean hasPathTo(int v) {return this.marked[v];
    }

    public Iterable<Integer> pathTo(int v) {if (!hasPathTo(v)) {throw new IllegalStateException("s 不能到达 v");
        }
        Stack<Integer> stack = new LinkedListStack<>();
        stack.push(v);
        while (edgeTo[v] != s) {stack.push(edgeTo[v]);
            v = edgeTo[v];
        }
        stack.push(s);
        return stack;
    }
}

以下图为列，来看看广度优先搜寻的运行轨迹

单元测试的代码：

@Test
public void test() {Graph graph = new Graph(8);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 5);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(4, 3);
    graph.addEdge(5, 3);
    graph.addEdge(6, 7);

    BreadthFirstPaths paths = new BreadthFirstPaths(graph, 0);
    System.out.println(paths.hasPathTo(5));
    System.out.println(paths.hasPathTo(2));
    System.out.println(paths.hasPathTo(6));

    paths.pathTo(5).forEach(System.out::print);
    System.out.println();
    paths.pathTo(4).forEach(System.out::print);
    System.out.println();
    paths.pathTo(2).forEach(System.out::print);
    System.out.println();
    paths.pathTo(3).forEach(System.out::print);

}

执行的后果与咱们剖析的运行轨迹统一

符号图

最近几篇文章一起学习到的图算法都是以数字作为了顶点，是因为数字来实现这些算法会十分的简洁不便，然而在理论的场景中，通常都是应用的字符作为顶点而非数字，比方：地图上的地位、电影与演员的关系。

为了满足理论的场景，咱们只须要在数字与字符串的关系做一个映射，此时咱们会想到之前文章实现的 map(通过二叉树实现 map、红黑树实现 map、哈希表实现 map 等等，有趣味的同学能够去翻翻)，应用 Map 来保护字符串和数字的映射关系。

public interface SymbolGraph {boolean contains(String key); // 判断是否存在顶点

    int index(String key); // 通过名称返回对应的数字顶点

    String name(int v); // 通过数字顶点返回对应的字符名称

    Graph graph();}

实现的思路：

  1. 应用 Map 来保留字符串 - 数字的映射，key 为字符串，value 为数字
  2. 应用一个数组来反向映射数字 - 字符串，数组的下标对应数字顶点，值对应字符串名称

假如结构图的顶点与边是通过字符串来示意的，如：a,b,c,d\nb,a,h,l,p\ng,s,z 应用 \n 分隔的每段第一个字符串示意顶点 v，前面的示意与顶点 v 相连的相邻顶点；

理论的过程能够依据具体情况来确定，不肯定非得这种字符串，能够来源于数据库，也能够来源于网路的申请。

代码实现如下：

public class SymbolGraph {private Map<String, Integer> map = new RedBlack23RedBlackTreeMap<>();
    private String[] keys;
    private Graph graph;

    public SymbolGraph(String text) {Arrays.stream(text.split("\n")).forEach(line -> {String[] split = line.split(",");
            for (int i = 0; i < split.length; i++) {map.put(split[i], i);
            }
        });

        this.keys = new String[map.size()];
        map.keys().forEach(key -> {this.keys[this.map.get(key)] = key;
        });

        this.graph = new Graph(this.keys.length);
        Arrays.stream(text.split("\n")).forEach(line -> {String[] split = line.split(",");
            int v = this.map.get(split[0]);
            for (int i = 1; i < split.length; i++) {this.graph.addEdge(v, this.map.get(split[i]));
            }
        });
        
    }

    public boolean contains(String key) {return map.contains(key);
    }

    public int index(String key) {return map.get(key);
    }

    public String name(int index) {return this.keys[index];
    }

    public Graph graph() {return this.graph;}

    public static void main(String[] args) {System.out.println(Arrays.toString("323\n2323".split("\n")));
    }
}

文中所有源码已放入到了 github 仓库:
https://github.com/silently9527/JavaCore

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源🙏

退出移动版