临接矩阵描述的图
图\(G = (V, E)\)的临接矩阵形式使用一个\(|V| \times |V|\)的矩阵来描述节点之间的链接关系，我们用符号\(M\)来标记图\(G\)的临界矩阵。 矩阵的第\(i\)行第\(j\)列的元素\(M_{i,j}\)描述了第\(i\)个节点与第\(j\)个节点之间的链接关系，可以形式化表示为: $$ M_{i,j} = \begin{cases} 1 & if (i,j) \in E \\ 0 & else \end{cases} $$ 如右图所示，是一个有向图的临接矩阵示例。图中矩阵的1表示对应行的节点有一条边指向了对应列的节点，0则表示不存在相应的边。 对于有向图而言，当\((i,j) \in E, i \neq j\)并且\((j,i) \notin E\)时，其临接矩阵就不是对称的。而无向图，\((i,j)\)与\((j,i)\)实际上是同一条边， 所以其临接矩阵是对称的。
本文中，我们以C++模板的形式实现图的临接矩阵表示。
1. 临接矩阵的定义
下面的代码片段是临接矩阵的主要成员变量定义。因为对于临接矩阵而言，其行和列索引分别对应着不同的节点，而矩阵的元素描述了边。所以，我们需要一个存储节点信息的线性表， 和一个存储边的二维数组。下面的代码片段中的成员变量nodes和matrix分别用于存储节点和边。
template <class NodeType, class EdgeType>
class GMatrix {
protected:
DataArray<NodeType> nodes;
Array2D<EdgeType*> matrix;
};
在上述代码片段中，成员matrix的元素是指针类型。如果两个节点之间存在连边关系，我们就构建一个EdgeType的对象来记录边的权重，并把对象的地址记录在临接矩阵中对应的位置上。 如果两个节点之间不存在连边关系，我们就将临接矩阵中对应的元素赋为空指针(NULL)。
目前我们为GMatrix提供了两个构造函数。其默认构造函数是什么也没有做。另一个构造需要一个输入参数指定图的节点数量，在成员变量的初始化列表中，我们指定了节点数组和临接矩阵的尺寸， 并在其函数体中，依次将matrix中的每个元素都赋为空指针。
GMatrix() {}
GMatrix(int n) : nodes(n), matrix(n, n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
matrix(i, j) = NULL;
}
此外，我们还重载了运算符"()"，提供临接矩阵的下角标访问形式。分别为节点和边提供了一个下角标操作，只需要一个节点索引就可以获得对应节点的权重对象的引用。 如果提供了两个节点索引，那么将返回连接这两个节点的边对象的指针。如果得到的是空指针则说明对应节点之间不存在连边关系，这正是函数IsConnected的功能。 需要注意的是，这三个函数并没有检查输入数据的合理性，在使用过程中应当格外注意。
NodeType & operator () (int i) { return nodes(i); }
EdgeType * operator () (int i, int j) { return matrix(i, j); }
bool IsConnected(int i, int j) const { return NULL != matrix(i, j); }
2. 临接矩阵的增删改
临接矩阵的增删改操作是指，向图中新增节点或者边、删除原图中的节点或边、修改节点的索引顺序或者节点和边的键值。 相比于临接表而言， 临接矩阵的增删操作比较繁琐。因为矩阵的行列索引分别对应着不同的节点，改变图的节点表述，往往需要大量的数据搬运操作。 用于存储节点和连边信息的数据结构DataArray和Array2D， 完成了这些数据搬运操作的封装。
2.1 增
bool add_node(int i, NodeType const key) {
int nv = nodes.size();
if (i > nv || 0 != nodes.insert(i, key))
return false;
if (!matrix.insert_row(i, 1) || matrix.insert_column(i, 1))
return false;
nv = nodes.size();
for (int idx = 0; idx < nv; idx++) {
matrix(idx, i) = NULL;
matrix(i, idx) = NULL;
}
return true;
}
bool add_edge(int i, int j, EdgeType const key) {
int nv = nodes.size();
if (i >= nv || j >= nv || IsConnected(i, j))
return false;
matrix(i, j) = new EdgeType(key);
return true;
}
右边是向临接矩阵描述的图中增加一个节点的函数，它有两个参数，其中i表示插入的节点索引，key则是节点的权重。该函数返回一个bool类型的数据，用于告知用户操作是否成功。
首先在第2行中，获取当前节点的数量。在第3行的if条件中先检查输入的索引，确保不会超出存储界限。 然后通过节点的数组容器接口，在第i个索引上插入新增节点的键值。 如果成功插入键值，nodes对象的成员函数insert将返回0，出错将返回错误编号。 紧接着，我们在第5行的条件中，先后对二维数组matrix插入新行和新列。
至此，我们已经完成了新增节点后的内存扩充。看起来，我们只是简单的在4个if语句中完成了这一过程，实际上进行了大量的数据搬运操作，只是容器的封装隐藏了很多细节。
接下来，我们还需要对矩阵的新增元素赋予初值。第7行获取扩容后的节点数量，之后在一个for循环中依次将各个新增元素赋为空指针。
新增边的操作就相对简单很多，因为矩阵中的每个元素都对应着一条边，我们只要保证节点索引不要越界，并且原来不存在连边关系即可。如右边的代码所示，在通过了第16行的if条件判定之后， 我们就直接构建了一个边对象并将地址赋给了矩阵中的对应元素。
2.2 删
如下面的代码所示，对于临接矩阵的删操作还是比较简单的。删除边时，我们确认节点索引没有越界后，就可以释放对应边的内存并将之赋为空指针。 删除节点时，我们只需要先检查节点索引不要越界，然后释放相关连边的对象，最后从数组nodes中移除节点的键值， 并依次删除矩阵的行和列。
|
|
2.3 改
修改节点或者边的键值很简单，我们只需要通过重载的运算符"()"获取待修改的对象，然后赋值即可。类似如下的代码片段，修改对象gmatrix的元素。
GMatrix<double, double> gmatrix(3);
gmatrix(0) = 3.1415926:
*gmatrix(1,2) = 1.41421;
有时因为计算的需要，我们会交换图的两个节点。此时，除了要交换节点数组nodes的相关元素外，还需要交换临接矩阵matrix对应的行和列，如下面的函数所示。
bool swap_nodes(int i, int j) {
int nv = nodes.size();
if (i >= nv || j >= nv || 0 != nodes.swap(i, j) || !matrix.swap_row(i, j) || !matrix.swap_column(i, j))
return false;
return true;
}
3. 完
本文中，我们用C++模板提供了临接矩阵形式的图。矩阵的行索引和列索引分别对应着图的节点。