2. 图的实现¶
接下来我们讨论实现通用 图 类的问题。 有两种传统的图表示方法： 邻接矩阵 和 邻接表。 在本模块中，我们将展示每种方法的实际实现。 我们将首先定义图的 ADT 接口， 给定的实现必须满足此接口。
interface Graph { // Graph class ADT
// Initialize the graph with some number of vertices
void init(int n);
// Return the number of vertices
int nodeCount();
// Return the current number of edges
int edgeCount();
// Get the value of node with index v
int getValue(int v);
// Set the value of node with index v
void setValue(int v, int val);
// Adds a new edge from node v to node w with weight wgt
void addEdge(int v, int w, int wgt);
// Get the weight value for an edge
int weight(int v, int w);
// Removes the edge from the graph.
void removeEdge(int v, int w);
// Returns true iff the graph has the edge
boolean hasEdge(int v, int w);
// Returns an array containing the indicies of the neighbors of v
int[] neighbors(int v);
}
interface Graph { // Graph class ADT
// Initialize the graph with some number of vertices
void init(int n);
// Return the number of vertices
int nodeCount();
// Return the current number of edges
int edgeCount();
// Get the value of node with index v
Object getValue(int v);
// Set the value of node with index v
void setValue(int v, Object val);
// Adds a new edge from node v to node w with weight wgt
void addEdge(int v, int w, int wgt);
// Get the weight value for an edge
int weight(int v, int w);
// Removes the edge from the graph.
void removeEdge(int v, int w);
// Returns true iff the graph has the edge
boolean hasEdge(int v, int w);
// Returns an array containing the indicies of the neighbors of v
int[] neighbors(int v);
}
此 ADT 假定图创建时顶点数是固定的，
但可以添加和删除边。
init 方法设置（或重置）图中的节点数，
并为邻接矩阵或邻接表创建必要的空间。
顶点由整数索引值定义。
换句话说，有顶点 0、顶点 1，一直到顶点 \(n-1\)。
我们可以假设图的客户端应用程序将有关给定顶点的
任何其他感兴趣的信息存储在其他地方，
例如名称或依赖于应用程序的值。
请注意，在 Java 或 C++ 这样的语言中，
此 ADT 不会使用泛型或模板等语言特性来实现，
因为 Graph 类的用户负责维护与顶点本身相关的信息。
Graph 类不需要知道与顶点关联的信息的类型或内容，
只需要知道该顶点的索引号。
接口 Graph 具有返回顶点和边数量的方法
（分别为方法 n 和 e）。
函数 weight 返回给定边的权值，
该边由其两个关联顶点标识。
例如，在图 16.1.1 (c) 上调用
weight(0, 4) 将返回 4。
如果不存在这样的边，则权值定义为 0。
因此在图 16.1.1 (c) 上调用
weight(0, 2) 将返回 0。
函数 addEdge 和 removeEdge 分别向图中
添加边（设置其权值）和删除边。
同样，边由其两个关联顶点标识。
addEdge 不允许用户将权值设置为 0，
因为此值用于表示不存在的边，
也不允许负的边权值。
函数 getValue 和 setValue 分别
获取和设置顶点 \(v\) 的请求值。
在我们的示例应用中，这些方法最频繁的用途
是指示给定节点在算法过程中是否已被访问过。
本章中介绍的几乎每个图算法都需要
访问给定顶点的所有邻居。
neighbors 方法返回一个数组，
其中包含相邻顶点的索引（按升序排列）。
以下几行出现在许多图算法中。
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++) {
if (G.getValue(nList[i]) != VISITED) {
DoSomething();
}
}
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++) {
if (G.getValue(nList[i]) != VISITED) {
DoSomething();
}
}
首先，生成一个数组，包含可以从节点 v
直接到达的节点的索引。
然后 for 循环遍历此邻居数组，
对每个邻居执行某个函数。
使用邻接表或邻接矩阵实现我们的图 ADT
是相当直接的。
这里提供的示例实现没有解决
图实际如何创建的问题。
这些实现的用户必须为此目的添加功能，
也许从文件读取图描述。
图可以使用 ADT 提供的 addEdge 函数构建。
以下是邻接矩阵的实现。
class GraphM implements Graph {
private int[][] matrix;
private int[] nodeValues;
private int numEdge;
// No real constructor needed
GraphM() { }
// Initialize the graph with n vertices
public void init(int n) {
matrix = new int[n][n];
nodeValues = new int[n];
numEdge = 0;
}
// Return the number of vertices
public int nodeCount() { return nodeValues.length; }
// Return the current number of edges
public int edgeCount() { return numEdge; }
// Get the value of node with index v
public int getValue(int v) { return nodeValues[v]; }
// Set the value of node with index v
public void setValue(int v, int val) { nodeValues[v] = val; }
// Adds a new edge from node v to node w
// Returns the new edge
public void addEdge(int v, int w, int wgt) {
if (wgt == 0) { return; } // Can't store weight of 0
if (matrix[v][w] == 0) {
numEdge++;
}
matrix[v][w] = wgt;
}
// Get the weight value for an edge
public int weight(int v, int w) { return matrix[v][w]; }
// Removes the edge from the graph.
public void removeEdge(int v, int w) {
if (matrix[v][w] != 0) {
matrix[v][w] = 0;
numEdge--;
}
}
// Returns true iff the graph has the edge
public boolean hasEdge(int v, int w) { return matrix[v][w] != 0; }
// Returns an array containing the indicies of the neighbors of v
public int[] neighbors(int v) {
int i;
int count = 0;
int[] temp;
for (i=0; i<nodeValues.length; i++) {
if (matrix[v][i] != 0) { count++; }
}
temp = new int[count];
for (i=0, count=0; i<nodeValues.length; i++) {
if (matrix[v][i] != 0) { temp[count++] = i; }
}
return temp;
}
}
class GraphM implements Graph {
private int[][] matrix;
private Object[] nodeValues;
private int numEdge;
// No real constructor needed
GraphM() { }
// Initialize the graph with n vertices
public void init(int n) {
matrix = new int[n][n];
nodeValues = new Object[n];
numEdge = 0;
}
// Return the number of vertices
public int nodeCount() { return nodeValues.length; }
// Return the current number of edges
public int edgeCount() { return numEdge; }
// Get the value of node with index v
public Object getValue(int v) { return nodeValues[v]; }
// Set the value of node with index v
public void setValue(int v, Object val) { nodeValues[v] = val; }
// Adds a new edge from node v to node w
// Returns the new edge
public void addEdge(int v, int w, int wgt) {
if (wgt == 0) { return; } // Can't store weight of 0
if (matrix[v][w] == 0) {
numEdge++;
}
matrix[v][w] = wgt;
}
// Get the weight value for an edge
public int weight(int v, int w) { return matrix[v][w]; }
// Removes the edge from the graph.
public void removeEdge(int v, int w) {
if (matrix[v][w] != 0) {
matrix[v][w] = 0;
numEdge--;
}
}
// Returns true iff the graph has the edge
public boolean hasEdge(int v, int w) { return matrix[v][w] != 0; }
// Returns an array containing the indicies of the neighbors of v
public int[] neighbors(int v) {
int i;
int count = 0;
int[] temp;
for (i=0; i<nodeValues.length; i++) {
if (matrix[v][i] != 0) { count++; }
}
temp = new int[count];
for (i=0, count=0; i<nodeValues.length; i++) {
if (matrix[v][i] != 0) { temp[count++] = i; }
}
return temp;
}
}
数组 nodeValues 存储由
setValue 和 getValue 函数操作的信息。
边矩阵实现为大小为 \(n \times n\) 的整数数组，
其中 \(n\) 是图的顶点数。
矩阵中的位置 \((i, j)\) 存储边 \((i, j)\) 的权值
（如果存在）。
边 \((i, j)\) 的权值为零用于表示
没有边连接顶点 \(i\) 和 \(j\)。
给定顶点 \(v\)，neighbors 方法扫描
矩阵的第 v 行以定位各个邻居的位置。
如果 \(v\) 上没有边，
则返回的邻居数组长度为 0。
函数 addEdge 和 removeEdge 调整
数组中的相应值。
函数 weight 返回数组中
适当位置的值。
以下是图的邻接表表示的实现。
其主要数据结构是链表数组，
每个顶点一个链表。
这些链表存储 Edge 类型的对象，
该对象仅存储边指向的顶点的索引以及边的权值。
public class GraphL implements Graph {
private class Edge { // Doubly linked list node
int vertex, weight;
Edge prev, next;
Edge(int v, int w, Edge p, Edge n) {
vertex = v;
weight = w;
prev = p;
next = n;
}
}
private Edge[] nodeArray;
private int[] nodeValues;
private int numEdge;
// No real constructor needed
GraphL() {}
// Initialize the graph with n vertices
public void init(int n) {
nodeArray = new Edge[n];
// List headers;
for (int i=0; i<n; i++) { nodeArray[i] = new Edge(-1, -1, null, null); }
nodeValues = new int[n];
numEdge = 0;
}
// Return the number of vertices
public int nodeCount() { return nodeArray.length; }
// Return the current number of edges
public int edgeCount() { return numEdge; }
// Get the value of node with index v
public int getValue(int v) { return nodeValues[v]; }
// Set the value of node with index v
public void setValue(int v, int val) { nodeValues[v] = val; }
// Return the link in v's neighbor list that preceeds the
// one with w (or where it would be)
private Edge find (int v, int w) {
Edge curr = nodeArray[v];
while ((curr.next != null) && (curr.next.vertex < w)) {
curr = curr.next;
}
return curr;
}
// Adds a new edge from node v to node w with weight wgt
public void addEdge(int v, int w, int wgt) {
if (wgt == 0) { return; } // Can't store weight of 0
Edge curr = find(v, w);
if ((curr.next != null) && (curr.next.vertex == w)) {
curr.next.weight = wgt;
}
else {
curr.next = new Edge(w, wgt, curr, curr.next);
numEdge++;
if (curr.next.next != null) { curr.next.next.prev = curr.next; }
}
}
// Get the weight value for an edge
public int weight(int v, int w) {
Edge curr = find(v, w);
if ((curr.next == null) || (curr.next.vertex != w)) { return 0; }
else { return curr.next.weight; }
}
// Removes the edge from the graph.
public void removeEdge(int v, int w) {
Edge curr = find(v, w);
if ((curr.next == null) || curr.next.vertex != w) { return; }
else {
curr.next = curr.next.next;
if (curr.next != null) { curr.next.prev = curr; }
}
numEdge--;
}
// Returns true iff the graph has the edge
public boolean hasEdge(int v, int w) { return weight(v, w) != 0; }
// Returns an array containing the indicies of the neighbors of v
public int[] neighbors(int v) {
int cnt = 0;
Edge curr;
for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
cnt++;
}
int[] temp = new int[cnt];
cnt = 0;
for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
temp[cnt++] = curr.vertex;
}
return temp;
}
}
public class GraphL implements Graph {
private class Edge { // Doubly linked list node
int vertex, weight;
Edge prev, next;
Edge(int v, int w, Edge p, Edge n) {
vertex = v;
weight = w;
prev = p;
next = n;
}
}
private Edge[] nodeArray;
private Object[] nodeValues;
private int numEdge;
// No real constructor needed
GraphL() {}
// Initialize the graph with n vertices
public void init(int n) {
nodeArray = new Edge[n];
// List headers;
for (int i=0; i<n; i++) { nodeArray[i] = new Edge(-1, -1, null, null); }
nodeValues = new Object[n];
numEdge = 0;
}
// Return the number of vertices
public int nodeCount() { return nodeArray.length; }
// Return the current number of edges
public int edgeCount() { return numEdge; }
// Get the value of node with index v
public Object getValue(int v) { return nodeValues[v]; }
// Set the value of node with index v
public void setValue(int v, Object val) { nodeValues[v] = val; }
// Return the link in v's neighbor list that preceeds the
// one with w (or where it would be)
private Edge find (int v, int w) {
Edge curr = nodeArray[v];
while ((curr.next != null) && (curr.next.vertex < w)) {
curr = curr.next;
}
return curr;
}
// Adds a new edge from node v to node w with weight wgt
public void addEdge(int v, int w, int wgt) {
if (wgt == 0) { return; } // Can't store weight of 0
Edge curr = find(v, w);
if ((curr.next != null) && (curr.next.vertex == w)) {
curr.next.weight = wgt;
}
else {
curr.next = new Edge(w, wgt, curr, curr.next);
numEdge++;
if (curr.next.next != null) { curr.next.next.prev = curr.next; }
}
}
// Get the weight value for an edge
public int weight(int v, int w) {
Edge curr = find(v, w);
if ((curr.next == null) || (curr.next.vertex != w)) { return 0; }
else { return curr.next.weight; }
}
// Removes the edge from the graph.
public void removeEdge(int v, int w) {
Edge curr = find(v, w);
if ((curr.next == null) || curr.next.vertex != w) { return; }
else {
curr.next = curr.next.next;
if (curr.next != null) { curr.next.prev = curr; }
}
numEdge--;
}
// Returns true iff the graph has the edge
public boolean hasEdge(int v, int w) { return weight(v, w) != 0; }
// Returns an array containing the indicies of the neighbors of v
public int[] neighbors(int v) {
int cnt = 0;
Edge curr;
for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
cnt++;
}
int[] temp = new int[cnt];
cnt = 0;
for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
temp[cnt++] = curr.vertex;
}
return temp;
}
}
GraphL 成员函数的实现原则上很简单，
关键函数是 addEdge、removeEdge 和 weight。
它们只需从邻接表的开头开始，
沿表移动直到找到所需的顶点。
私有方法 find 是一个工具函数，
用于在存在时找到保存顶点 \(v\) 的边之前的最后一条边。
