图的表示与算法

图有两种表示方法：邻接矩阵与邻接表。对于无权图 G$\left(\vphantom{V,E}\right.$V, E$\left.\vphantom{V,E}\right)$邻接矩阵是N x N的矩阵，行号与列号代表顶点，如果顶点i与顶 点j相连，则相应矩阵元为1，否则为零。也就是矩阵 $\left(\vphantom{\delta^{uv}}\right.$$\delta^{{uv}}_{}$$\left.\vphantom{\delta^{uv}}\right)_{{N\times N}}^{}$。加权网络的邻接矩阵为 $\left(\vphantom{\delta^{uv}W_{uv}}\right.$$\delta^{{uv}}_{}$W_uv$\left.\vphantom{\delta^{uv}W_{uv}}\right)_{{N\times N}}^{}$。 邻接表是N个元素构成的数组，每一个元素代表相应顶点的近邻。也就是把邻接矩阵分为一行一行表示，对于第i行，列出所有 $\delta^{{iv}}_{}$ $\neq$ 0的顶点。对于加权网络，列出顶点编号之后，还要带上权重。对于稀疏图，利用邻接表的方式可以节约大量的存储空间。

对于实际网络，只要把顶点与边的信息利用邻接矩阵或邻接表存储起来就可以供下一步研究使用了。对于模型网络，例如Scale Free网络，就 必须先按照网络模型来生成了。生成Scale Free网络的方法有两种：机制演化与Monte Carlo模拟。机制演化就是按照偏好依附模型以m₀ 个顶点的完全图为初始值，按照偏好的方式进行加边加点，在足够长时间以后形成稳定度值分布的网络；Monte Carlo模拟的方法是按照幂率分 布选取N个随机数，并给每个顶点赋以度值，然后按照某种方式在各自度值的约束下连接这些顶点，也可以得到度值符合幂率分布的网络。例如， 度值大的顶点优先选择度值小的顶点来连接，直到用掉所有的度值，然后第二大的顶点重复这一过程；也可以让度值大的顶点优先选择度值大的顶点来 连结；也可以在所有顶点之间随机连接，如果出现联接数大于所要求的度值的情况就断开重新连接。不管这种连结优先方式如何，生成的网络 其度分布都是幂律形式的，只有顶点之间匹配模式的不同。关于匹配模式的研究表明，偏好依附模型生成的网络其顶点的度值之间基本上没有 关联，也就是与随机连结方式类似。

在网络的静态几何量之中，度值、集聚程度都是局域性质，可以在网络表示中简单地求得。而最短距离、边与顶点的介数都与网络中任意两点 的最短路径相关。因此，解决最短路径问题是网络上几何量算法的关键。在无向网络中，这可以通过广度优先搜索实现。广度优先搜索图的周 游的一种算法，给每一个顶点指定一个标记，开始全为零，从某一个顶点开始，访问其所有的近邻，访问过之后，改变其标记值为1；对于被 访问到的近邻，同样先访问各自的近邻，并改变未被访问过的顶点（其标记值为0）的标记值，直到所有的顶点都被访问。利用这一算法就 可以研究从某一个顶点出发的所有最短距离。至于所有顶点之间的最短距离可以简单地重复上述单源最短距离的算法，也可以在此基础上 略加修改[74]。但是对于稀疏网络改进不大。