# 图算法系列之计算图中最短路径

05/10 08:00

## 广度优先搜索

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

1. 使用队列来保存已经被标记过但是邻接表还未被遍历过的顶点
2. 取出队列中的下一个顶点v并标记它
3. 将v相邻的所有未被标记的顶点加入到队列

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;    }}

@Testpublic 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);}

## 符号图

public interface SymbolGraph {    boolean contains(String key); //判断是否存在顶点    int index(String key); //通过名称返回对应的数字顶点    String name(int v); //通过数字顶点返回对应的字符名称    Graph graph();}

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

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")));    }}

0
0 收藏

0 评论
0 收藏
0