数据结构与算法--符号图

为了计算简单，传统的图中，都是使用整数来表示顶点，这样难免会有点抽象，不能直接反映各个顶点代表的信息。在实际生活中，使用图时一般会建立一个一一对应的关系表，如下

图的处理过程中，比如说到处理到顶点2，可能要去查看上表，才能知道说的是“深圳”。在典型的应用中，图都是通过文件或者网页定义的，更多的是用字符串而非整数，使用字符串能更加直观地反映各个顶点的信息。为了使得通过字符串能快速找到对应的顶点，会用到符号表进行查找，与图结合起来，这种数据结构被称为符号图。

对于符号图的定义，有如下约定：

• 顶点名是字符串
• 输入中的每一行表示一组边的集合，每一行的第一个顶点和该行之后的所有顶点都相连。比如下面这个二维数组，里面每一个一维数组都是一组边的集合，一维数组中第一个顶点（如“产品D”），和其后的每一个顶点都相连（如与“产品A”对应的"经销商1",和"经销商6"）

String[][] edges = {{"产品A", "经销商1", "经销商3", "经销商4", "经销商6"},
        {"产品B", "经销商1", "经销商2", "经销商3", "经销商5", "经销商6"},
        {"产品C", "经销商1", "经销商3", "经销商4", "经销商5", "经销商6"},
        {"产品D, "经销商1", "经销商6"}};

符号图的核心还是图，内部数据结构中顶点还是用整数表示。只不过里面加入了符号表的功能，使得整数顶点和字符串形成映射，可以方便地：

• 通过整数索引，查找对应的字符串
• 通过字符串，查找对应的顶点（整数表示）

基于此，实现符号图如下。

package Chap7;

import Chap8.BST;

public class SymbolUnDiGraph {
    // 键是顶点字符串，值是顶点
    private BST<String, Integer> st; // 符号名 -> 顶点索引
    private String[] keys; // 顶点索引 -> 符号名
    private UndiGraph<String> graph;

    public SymbolUnDiGraph(String[][] edges) {
        // 第一次遍历边集，建立符号表
        st = new BST<>();
        for (String[] infos : edges) {
            for (String info : infos) {
                // 重复的字符串不再分配顶点
                if (!st.contains(info)) {
                    st.put(info, st.size());
                }
            }
        }

        keys = new String[st.size()];
        for (String name : st.keys()) {
            keys[st.get(name)] = name;
        }

        // 第二次遍历边集
        // 构造图, 每一行的第一个顶点和该行的其他顶点相连
        graph = new UndiGraph<>(st.size());
        for (String[] infos : edges) {
            int v = st.get(infos[]);
            for (int i = ; i < infos.length; i++) {
                graph.addEdge(v, st.get(infos[i]));
            }
        }

    }

    public boolean contains(String name) {
        return st.contains(name);
    }

    public int indexOf(String name) {
        return st.get(name);
    }

    public String nameOf(int v) {
        return keys[v];
    }

    public UndiGraph<String> graph() {
        return graph;
    }

    public static void main(String[] args) {
        String[][] edges = {{"产品A", "经销商1", "经销商3", "经销商4", "经销商6"},
                {"产品B", "经销商1", "经销商2", "经销商3", "经销商5", "经销商6"},
                {"产品C", "经销商1", "经销商3", "经销商4", "经销商5", "经销商6"},
                {"产品D", "经销商1", "经销商6"}};

        SymbolUnDiGraph sg = new SymbolUnDiGraph(edges);
        UndiGraph<String> graph = sg.graph();
        System.out.println("经销商4有经营下面几种产品");
        for (int w : graph.adj(sg.indexOf("经销商4"))) {
            System.out.print(sg.nameOf(w) + " ");
        }
        System.out.println();

        System.out.println("产品C在下面几个经销商有售");
        for (int w : graph.adj(sg.indexOf("产品C"))) {
            System.out.print(sg.nameOf(w) + " ");
        }
        System.out.println();
    }
}

上面的代码会打印如下信息

经销商4有经营下面几种产品
产品A 产品C 
产品C在下面几个经销商有售
经销商1 经销商3 经销商4 经销商5 经销商6

符号表的实现采用基于二分查找的有序数组。即上面的BST<String, Integer> st，可以通过字符串快速找到与之对应的顶点，这通过indexOf(String name)实现；

另外建立了一个String[]数组，可以通过整数表示的顶点获取该顶点的信息，这通过nameOf(int v)实现。contains方法可以直接用字符串判断某个顶点是否在图中。graph方法返回边集合定义的无向图。

从上面的代码可以看出，我们全程没有和整数打交道，实际上这些工作内部的数据结构已经帮我们做好了。代码中总共两次遍历边集，第一次是构造符号表，建立了顶点和字符串的关系。核心是下面这句，他将每一个不重复的字符串都放入符号表，与之对应的整数顶点直接使用符号表的长度这个值。（比如第一个被放入符号表的顶点为0，以此类推。）

// 重复的字符串不再分配顶点
if (!st.contains(info)) {
  st.put(info, st.size());
}

之后通过反向索引得到String[] keys，下图清晰得剖析了符号图的数据结构

符号图当然可以处理有向图，只需将图的数据类型换成有向图即可，其余代码都不改变！

package Chap7;

import Chap8.BST;

/**
 * 针对有向图的符号图，使用字符串表示顶点
 */
public class SymbolDiGraph {
    // 键是顶点字符串，值是顶点
    private BST<String, Integer> st; // 符号名 -> 顶点索引
    private String[] keys; // 顶点索引 -> 符号名
    private DiGraph<String> graph;

    public SymbolDiGraph(String[][] edges) {
        st = new BST<>();
        for (String[] infos : edges) {
            for (String info : infos) {
                // 重复的字符串不再分配顶点
                if (!st.contains(info)) {
                    st.put(info, st.size());
                }
            }
        }

        keys = new String[st.size()];
        for (String name : st.keys()) {
            keys[st.get(name)] = name;
        }

        // 构造图, 每一行的第一个顶点和该行的其他顶点相连
        graph = new DiGraph<>(st.size());
        for (String[] infos : edges) {
            int v = st.get(infos[]);
            for (int i = ; i < infos.length; i++) {
                graph.addEdge(v, st.get(infos[i]));
            }
        }

    }

    public boolean contains(String name) {
        return st.contains(name);
    }

    public int indexOf(String name) {
        return st.get(name);
    }

    public String nameOf(int v) {
        return keys[v];
    }

    public DiGraph<String> graph() {
        return graph;
    }

    public static void main(String[] args) {
        String[][] edges = {{"郑州", "上海", "北京", "西安", "成都"},
                {"成都", "郑州", "北京", "西安"},
                {"上海", "北京"},
                {"西安", "成都", "郑州"}};

        SymbolDiGraph sg = new SymbolDiGraph(edges);
        DiGraph<String> graph = sg.graph();
        for (int w : graph.adj(sg.indexOf("西安"))) {
            System.out.print(sg.nameOf(w) + " ");
        }
        System.out.println();
    }
}

by @sunhaiyu

2017.11.12