数据结构与算法--符号图
为了计算简单，传统的图中，都是使用整数来表示顶点，这样难免会有点抽象，不能直接反映各个顶点代表的信息。在实际生活中，使用图时一般会建立一个一一对应的关系表，如下
| 顶点 | 0 | 1 | 2 |
|---|---|---|---|
| 信息 | 北京 | 上海 | 深圳 |
图的处理过程中，比如说到处理顶点2，可能要去查看上表，才能知道说的是“深圳”。在典型的应用中，图都是通过文件或者网页定义的，更多的是用字符串而非整数，使用字符串能更加直观地反映各个顶点的信息。为了使得通过字符串能快速找到对应的顶点，会用到符号表进行查找，与图结合起来，这种数据结构被称为符号图。
对于符号图的定义，有如下约定：
- 顶点名是字符串
- 输入中的每一行表示一组边的集合，每一行的第一个顶点和该行之后的所有顶点都相连。比如下面这个二维数组，里面每一个一维数组都是一组边的集合，一维数组中第一个顶点（如“产品D”），和其后的每一个顶点都相连（如与“产品D”对应的"经销商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[0]);
for (int i = 1; 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，下图清晰得剖析了符号图的数据结构
image
符号图当然可以处理有向图，只需将图的数据类型换成有向图即可，其余代码都不改变！
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[0]);
for (int i = 1; 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
