算法-图论
标签:算法

图论(Graph Theory)

1. 基础知识

无向图:节点之间没有方向的

无向图:节点之间有方向

无权图:边上没有权值

有全图:每个边有相应的权值

连通性

简单图:

2. 图的表示

邻接矩阵:左边表示为有向图,右边为无向图

package com.liuyao.graph;

/**
 * Created By liuyao on 2018/4/30 11:27.
 */
//稠密图 - 邻接矩阵
public class DenseGraph {
    private int n; // 节点数
    private int m; // 边数
    private boolean directed; // 是否为有向图
    private boolean[][] g;    // 图的具体数据

    public DenseGraph(int n, boolean directed) {
        assert n > 0;
        this.n = n;
        this.m = 0;  //初始化的时候没有任何边
        this.directed = directed;
        // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
        // false为boolean型变量的默认值
        g = new boolean[n][n];
    }

    // 返回节点个数
    public int V() {
        return n;
    }

    // 返回边的个数
    public int E() {
        return m;
    }

    // 验证图中是否有从v到w的边
    private boolean hasEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >= 0 && w < n;
        return g[v][w];
    }

    // 向图中添加一个边
    public void addEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >= 0 && w < n;
        if (hasEdge(v, w)) {
            return;
        }
        g[v][w] = true;
        if (!directed) {
            g[w][v] = true;
        }
        m++;
    }
}

邻接表:左边表示为有向图,右边为无向图

package com.liuyao.graph;

import java.util.Vector;

/**
 * Created By liuyao on 2018/4/30 11:56.
 */
public class SparseGraph {
    private int n;
    private int m;
    private boolean directed;
    private Vector<Integer>[] g;

    public SparseGraph(int n, boolean directed) {
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = (Vector<Integer>[]) new Vector[n];
        for (int i = 0; i < n; i++) {
            g[i] = new Vector<Integer>();
        }
    }

    public int V() {
        return n;
    } // 返回节点个数

    public int E() {
        return m;
    } // 返回边的个数

    // 验证图中是否有从v到w的边
    private boolean hasEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >= 0 && w < n;

        for (int i = 0; i < g[v].size(); i++) {
            if (g[v].elementAt(i) == w) {
                return true;
            }
        }
        return false;
    }

    // 向图中添加一个边
    public void addEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >= 0 && w < n;
        g[v].add(w);
        if (v != w && !directed) {
            g[w].add(v);
        }
        m++;
    }
}

3. 图的构造

声明一个公共的接口

package com.liuyao.graph;

/**
 * Created By liuyao on 2018/4/30 15:36.
 */
public interface Graph {
    public int V();

    public int E();

    public void addEdge(int v, int w);

    public boolean hasEdge(int v, int w);

    void show();

    public Iterable<Integer> adj(int v);
}

给邻接矩阵构造的图添加迭代和显示方法:

 // 返回图中一个顶点的所有邻边
    // 由于java使用引用机制,返回一个Vector不会带来额外开销,
    @Override
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> adjV = new Vector<>();
        for (int i = 0; i < n; i++) {
            if (g[v][i]) {
                adjV.add(i);
            }
        }
        return adjV;
    }

    // 显示邻接矩阵构造的图
    @Override
    public void show() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print((g[i][j] ? 1 : 0) + "\t");
            }
            System.out.println();
        }
    }

给邻接表构造的图添加迭代和显示方法:

// 返回图中一个顶点的所有邻边
    // 由于java使用引用机制,返回一个Vector不会带来额外开销,
    @Override
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
    
    @Override
    public void show() {
        for (int i = 0; i < n; i++) {
            System.out.print("vertex" + i + ":\t");
            for (int j = 0; j < g[i].size(); j++) {
                System.out.print(g[i].elementAt(j) + "\t");
            }
            System.out.println();
        }
    }

从文件读入图并构造:

package com.liuyao.graph;

import java.io.*;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.Scanner;

/**
 * Created By liuyao on 2018/4/30 15:44.
 */
public class ReadGraph {
    private Scanner scanner;

    public ReadGraph(Graph graph, String filename) {

        readFile(filename);

        try {
            int V = scanner.nextInt();
            if (V < 0) {
                throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
            }
            assert V == graph.V();

            int E = scanner.nextInt();
            if (E < 0) {
                throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
            }

            for (int i = 0; i < E; i++) {
                int v = scanner.nextInt();
                int w = scanner.nextInt();
                assert v >= 0 && v < V;
                assert w >= 0 && w < V;
                graph.addEdge(v, w);
            }
        } catch (InputMismatchException e) {
            String token = scanner.next();
            throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\"");
        } catch (NoSuchElementException e) {
            throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available");
        }
    }

    private void readFile(String filename) {
        assert filename != null;
        try {
            File file = new File(filename);
            if (file.exists()) {
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            } else {
                throw new IllegalArgumentException(filename + "doesn't exist.");
            }
        } catch (IOException ioe) {
            throw new IllegalArgumentException("Could not open " + filename, ioe);
        }
    }

    public static void main(String[] args) {

        // 使用两种图的存储方式读取testG1.txt文件
        String filename = "testG1.txt";
        SparseGraph g1 = new SparseGraph(13, false);
        ReadGraph readGraph1 = new ReadGraph(g1, filename);
        System.out.println("test G1 in Sparse Graph:");
        g1.show();

        System.out.println();

        DenseGraph g2 = new DenseGraph(13, false);
        ReadGraph readGraph2 = new ReadGraph(g2, filename);
        System.out.println("test G1 in Dense Graph:");
        g2.show();

        System.out.println();

        // 使用两种图的存储方式读取testG2.txt文件
        filename = "testG2.txt";
        SparseGraph g3 = new SparseGraph(6, false);
        ReadGraph readGraph3 = new ReadGraph(g3, filename);
        System.out.println("test G2 in Sparse Graph:");
        g3.show();

        System.out.println();

        DenseGraph g4 = new DenseGraph(6, false);
        ReadGraph readGraph4 = new ReadGraph(g4, filename);
        System.out.println("test G2 in Dense Graph:");
        g4.show();
    }

}

4. 深度优先遍历

以下代码包括了深度优先遍历和求联通分量个数以及判断两个节点是否联通:

package com.liuyao.graph;

/**
 * Created By liuyao on 2018/4/30 16:33.
 */
// 求无权图的联通分量
public class Components {
    Graph G;   //图的引用
    private boolean[] visited;  //记录dfs的过程中节点是否被访问过
    private int ccount;  //记录联通分量个数
    private int[] id;  //每个节点所对应的联通分量标记

    public Components(Graph graph) {
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];

        //初始化联通非分量个数为0个
        ccount = 0;

        for (int i = 0; i < G.V(); i++) {
            //初始化每个节点的都没被访问过
            visited[i] = false;

            //初始化每个节点的联通分量标记为-1
            id[i] = -1;
        }

        //求图的联通分量
        for (int i = 0; i < G.V(); i++) {
            //如果当前节点没有被遍历
            if (!visited[i]) {
                //执行深度优先搜索
                dfs(i);

                //设置当前的联通分量个数
                ccount++;
            }
        }
    }

    //    图的深度优先遍历
    private void dfs(int v) {
        //设置当前节点已经被访问
        visited[v] = true;

        //标记当前节点所属的联通分量
        id[v] = ccount;

        //迭代遍历
        for (int i : G.adj(v)) {
            if (!visited[i]) {
                //递归查询
                dfs(i);
            }
        }
    }

    // 返回图的联通分量个数
    int count() {
        return ccount;
    }

    // 查询两个节点是否联通
    public boolean isConnected(int v, int w) {
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        //比较两个节点的联通分量是否相同
        return id[v] == id[w];
    }

    public static void main(String[] args) {
        // TestG1.txt
        String filename1 = "testG1.txt";
        SparseGraph g1 = new SparseGraph(13, false);
        ReadGraph readGraph1 = new ReadGraph(g1, filename1);
        Components component1 = new Components(g1);
        System.out.println("TestG1.txt, Component Count: " + component1.count());
        System.out.println();

        // TestG2.txt
        String filename2 = "testG2.txt";
        SparseGraph g2 = new SparseGraph(6, false);
        ReadGraph readGraph2 = new ReadGraph(g2, filename2);
        Components component2 = new Components(g2);
        System.out.println("TestG2.txt, Component Count: " + component2.count());
    }
}

5. 寻径算法

通过数组from记录路径

package com.liuyao.graph;

import java.util.Stack;
import java.util.Vector;

/**
 * Created By liuyao on 2018/4/30 17:33.
 */
public class Path {
    private Graph G;  //图的引用
    private int s;  //起始点
    private boolean[] visited;  //记录dfs的过程中节点是否被访问
    private int[] from; //记录路径,from[i]表示查找的路径上i的上一个节点

    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public Path(Graph graph, int s) {
        G = graph;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1; // 初始化时全部初始化为-1
        }
        this.s = s;

//        寻路算法 根据起点s开始,只深搜一次
        dfs(s);
    }

    // 图的深度优先遍历
    private void dfs(int v) {
        //设置当前节点已被访问
        visited[v] = true;
        for (int i : G.adj(v)) {
            if (!visited[i]) {
//                设置当前节点由上一个节点v来的
                from[i] = v;
                dfs(i);
            }
        }
    }

    // 查询从s点到w点是否有路径
    public boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
//        如果从s到w有路径则会返回返回true
        return visited[w];
    }

    Vector<Integer> path(int w) {
        assert hasPath(w);
        Stack<Integer> stack = new Stack<Integer>();

        int p = w;
//        其实节点的from标记为-1
        while (p != -1) {
//            依次将p的前面节点压栈
            stack.push(p);
            p = from[p];
        }

//        从尾到头依次构建路径
        Vector<Integer> res = new Vector<Integer>();
        while (!stack.empty()) {
            res.add(stack.pop());
        }
//        返回最后的路径
        return res;
    }

    public void showPath(int w) {
        assert hasPath(w);

        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
//            最后一个直接输出换行
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    // 测试寻路算法
    public static void main(String[] args) {

        String filename = "testG.txt";
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();
        System.out.println();

        Path path = new Path(g, 0);
        System.out.println("Path from 0 to 6 : ");
        path.showPath(6);
    }
}

6. 广度优先遍历

package com.liuyao.graph;

import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;

/**
 * Created By liuyao on 2018/4/30 21:40.
 */
public class ShortestPath {
    private Graph G;
    private int s;
    private boolean[] visited;
    private int[] from;
    private int[] ord;

    public ShortestPath(Graph g, int s) {
        G = g;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];
        ord = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this.s = s;

        // 无向图最短路径算法, 从s开始广度优先遍历整张图
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.addLast(s);
        visited[s] = true;
        ord[s] = 0;
        while (!list.isEmpty()) {
            int v = list.removeFirst();
            for (int i : G.adj(v)) {
                if (!visited[i]) {
                    list.addLast(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + i;
                }
            }
        }

    }

    // 查询从s点到w点是否有路径
    public boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
//        如果从s到w有路径则会返回返回true
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    Vector<Integer> path(int w) {
        assert hasPath(w);
        Stack<Integer> stack = new Stack<Integer>();

        int p = w;
//        其实节点的from标记为-1
        while (p != -1) {
//            依次将p的前面节点压栈
            stack.push(p);
            p = from[p];
        }

//        从尾到头依次构建路径
        Vector<Integer> res = new Vector<Integer>();
        while (!stack.empty()) {
            res.add(stack.pop());
        }
//        返回最后的路径
        return res;
    }

    // 打印出从s点到w点的路径
    public void showPath(int w) {
        assert hasPath(w);

        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
//            最后一个直接输出换行
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    // 查看从s点到w点的最短路径长度
    // 若从s到w不可达,返回-1
    public int length(int w) {
        assert w >= 0 && w < G.V();
        return ord[w];
    }

    public static void main(String[] args) {
        String filename = "testG.txt";
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();
        System.out.println();

        ShortestPath bfs = new ShortestPath(g, 0);
        System.out.print("BFS : ");
        bfs.showPath(6);
    }
}

  • 11 min read

CONTRIBUTORS


  • 11 min read