▶ 书中第四章部分程序，包括在加上自己补充的代码，图的几种补充数据结构，包括无向 / 有向符号图，有权边结构，有边权有向图
● 无向符号图
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.ST; public class class01
{
private ST<String, Integer> st; // 字符串转索引
private String[] keys; // 索引转字符串
private Graph graph; public class01(String filename, String delimiter)
{
st = new ST<String, Integer>();
for (In in = new In(filename); !in.isEmpty();) // 收集符号，存入集合，编号
{
String[] a = in.readLine().split(delimiter);
for (int i = 0; i < a.length; i++)
{
if (!st.contains(a[i]))
st.put(a[i], st.size());
}
}
keys = new String[st.size()];
for (String name : st.keys())
keys[st.get(name)] = name;
graph = new Graph(st.size());
for (In in = new In(filename); in.hasNextLine();) // 再读一次，建图
{
String[] a = in.readLine().split(delimiter);
int v = st.get(a[0]);
for (int i = 1; i < a.length; i++)
{
int w = st.get(a[i]);
graph.addEdge(v, w);
}
}
} public boolean contains(String s)
{
return st.contains(s);
} public int indexOf(String s)
{
return st.get(s);
} public String nameOf(int v)
{
return keys[v];
} public Graph graph()
{
return graph;
} public static void main(String[] args)
{
String filename = args[0]; // 输入符号图（邻接表）的文件名和分隔符
String delimiter = args[1];
class01 sg = new class01(filename, delimiter);
for (Graph graph = sg.graph(); StdIn.hasNextLine();)
{
String source = StdIn.readLine(); // 再输入需要查询的顶点
if (sg.contains(source))
{
int s = sg.indexOf(source);
for (int v : graph.adj(s))
StdOut.println(" " + sg.nameOf(v));
}
else
StdOut.println("input not contain '" + source + "'");
}
}
}
● 有向符号图，与无向情形仅有方法名不同
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.ST; public class class01
{
private ST<String, Integer> st;
private String[] keys;
private Digraph graph; public class01(String filename, String delimiter)
{
st = new ST<String, Integer>();
for (In in = new In(filename); !in.isEmpty();)
{
String[] a = in.readLine().split(delimiter);
for (int i = 0; i < a.length; i++)
{
if (!st.contains(a[i]))
st.put(a[i], st.size());
}
}
keys = new String[st.size()];
for (String name : st.keys())
keys[st.get(name)] = name;
graph = new Graph(st.size());
for (In in = new In(filename); in.hasNextLine();) // 再读一次，建图
{
String[] a = in.readLine().split(delimiter);
int v = st.get(a[0]);
for (int i = 1; i < a.length; i++)
{
int w = st.get(a[i]);
graph.addEdge(v, w);
}
}
} public boolean contains(String s)
{
return st.contains(s);
} public int indexOf(String s)
{
return st.get(s);
} public String nameOf(int v)
{
return keys[v];
} public Digraph digraph()
{
return graph;
} public static void main(String[] args)
{
String filename = args[0];
String delimiter = args[1];
class01 sg = new class01(filename, delimiter);
for (Digraph graph = sg.digraph(); StdIn.hasNextLine();)
{
String t = StdIn.readLine();
for (int v : graph.adj(sg.indexOf(t)))
StdOut.println(" " + sg.nameOf(v));
}
}
}
● 有权边结构
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Edge; public class class01 implements Comparable<Edge>
{
private final int v;
private final int w;
private final double weight; public class01(int inputV, int inputW, double inputWeight)
{
if (inputV < 0 || inputW < 0 || Double.isNaN(inputWeight))
throw new IllegalArgumentException("\n<Construtor> v < 0 || w < 0 || weight == NaN.\n");
v = inputV;
w = inputW;
weight = inputWeight;
} public double weight()
{
return weight;
} public int either()
{
return v;
} public int other(int vertex)
{
if (vertex == v)
return w;
if (vertex == w)
return v;
throw new IllegalArgumentException("\n<other> No such point.\n");
} @Override
public int compareTo(class01 that)
{
return Double.compare(weight, that.weight);
} public String toString()
{
return String.format("%d-%d %.5f", v, w, weight);
} public static void main(String[] args)
{
class01 e = new class01(12, 34, 5.67);
StdOut.println(e);
}
}
● 有边权有向图
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Edge; public class class01
{
private static final String NEWLINE = System.getProperty("line.separator");// 换行，按操作系统适配 private final int V;
private int E;
private Bag<Edge>[] adj; public class01(int inputV)
{
if (inputV < 0)
throw new IllegalArgumentException("\n<Constructor> V < 0.\n");
V = inputV;
E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<Edge>();
} public class01(int inputV, int inputE)
{
this(inputV);
if (inputE < 0)
throw new IllegalArgumentException("\n<Constructor> E < 0.\n");
for (int i = 0; i < E; i++) // 添加 E 条边，随机权重
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
Edge e = new Edge(v, w, Math.round(100 * StdRandom.uniform()) / 100.0);
addEdge(e);
}
} public class01(In in)
{
this(in.readInt());
E = in.readInt();
if (E < 0)
throw new IllegalArgumentException("\n<Constructor> E < 0.\n");
for (int i = 0; i < E; i++)
{
int v = in.readInt();
int w = in.readInt();
Edge e = new Edge(v, w, in.readDouble());
addEdge(e);
}
} public class01(class01 G)
{
this(G.V());
E = G.E();
for (int v = 0; v < G.V(); v++)
{
Stack<Edge> reverse = new Stack<Edge>();// 用栈保存原图遍历得到的边，吐栈是回复顺序
for (Edge e : G.adj[v])
reverse.push(e);
for (Edge e : reverse)
adj[v].add(e);
}
} public int V()
{
return V;
} public int E()
{
return E;
} public void addEdge(Edge e)
{
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
} public Iterable<Edge> adj(int v)
{
return adj[v];
} public int degree(int v)
{
return adj[v].size();
} public Iterable<Edge> edges()
{
Bag<Edge> list = new Bag<Edge>();
for (int v = 0; v < V; v++)
{
boolean selfLoop = false; // 注意两条自边只算一个自环
for (Edge e : adj(v))
{
if (e.other(v) == v)
{
if (!selfLoop)
list.add(e);
selfLoop = !selfLoop;
}
if (e.other(v) > v) // 索引控制，防止反复添加同一条边
list.add(e);
}
}
return list;
} public String toString()
{
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++)
{
s.append(v + ": ");
for (Edge e : adj[v])
s.append(e + " ");
s.append(NEWLINE);
}
return s.toString();
} public static void main(String[] args)
{
In in = new In(args[0]);
class01 G = new class01(in);
StdOut.println(G);
}
}