首先简单说一下什么是行压缩图，其实严格意义上应该是行压缩矩阵。正常情况下，矩阵是用二维数组简单存储的，香港虚拟主机，但是如果是稀疏矩阵，也就是零很多的时候，这样比较浪费空间。所以就有各种节省空间的存储方式，三元组存储就是其中一种。
什么是三元组呢？一个三元组就是(row,col,value)，这样把所有不为零的值组成一个向量。这种存储方式比二维数组节省了不少空间，当然还可以进一步节省，因为三元组里面row或者col重复存储了，虚拟主机，一行或者一列存一次就行了，按这种思路走下去就是行压缩存储了。
那具体什么是行压缩存储呢？行压缩存储的思想就是，把所有不为零的值按行访问的顺序组成一个向量，然后再把每一行值不为0的列的下标存下来，这个两个向量的大小和稀疏矩阵中不为0的值得个数相同，当然要实现对行压缩矩阵的访问，还要把每一行的不为0的列的下标在第二个向量中开始的位置存下来，有人把这个叫做指针。有了这三个向量就可以实现对矩阵实现高效的按行访问了。行压缩存储比三元组优秀的不仅是空间的压缩，还有就是行访问时的高效。三元组如果是有序的，可以二分查找来访问一行，但是行压缩存储按行访问时的时间复杂度是常数级的。 大家可以参考下面这个行压缩矩阵示意图：
可能你会有疑问，你明明实现的行压缩图，怎么扯了这么多行压缩矩阵呢？其实图和矩阵是等价的，矩阵的一行可以看做是图一个节点的出边，矩阵的一列可以看做图一个节点的入边。当然这里需要满足两个条件：第一个就是图节点编号必须是从0或者1开始的连续数值（这个可以通过对图的节点做一次映射解决），第二个就是图必须至少是弱连通的（非连通图可以拆成连图片）。实现了稀疏矩阵的高效存储访问，也就实现了图的高效存储访问。
下面来说一下，我的实现。我的实现跟经典的行压缩矩阵有两个不同：第一个就是经典的行压缩矩阵没有考虑一行全为0的情况，我对这种情况做了处理（之所以处理当然不是因为我无聊，而是因为有这个需求）。第二个就是经典的行压缩图对按列访问比较慢（当然是相对于按行访问的速度而言），对行压缩图按列访问时，时间复杂度是线性的。我也对这种情况做了处理。
这里简单说一下我的思路：
第一个问题，我是通过将所有指针默认设为-1，即表示该行可能全为0，只有当有非零值时才设置为其正确的指针。当然访问时也要做相应的处理。
第二个问题，我是这样解决的。我按列压缩存储的方式，存了一份每一列不为0的行下标，以及每一列不为0的行下标开始的位置。这样我的实现中就多了两个向量，浪费了存储空间，但是提高了按列访问时的效率。
好了，talk is cheap，show me the code。下面是我的代码（可能有错，我只做了简单的测试）
利用边向量构造压缩图
/* * buildGraph 利用边向量 构造压缩图 * 对边分别按第一个顶点、第二个顶点排序 * 然后分别按行压缩图和列压缩图构造行、列索引和指针 * 全零行和全零列,指针置为-1 buildGraph(Vector<Edge> edges) {int edgeSize = edges.size();weight = new Vector<Float>(edgeSize);rowIndex = new Vector<Integer>(edgeSize);rowPtr = new Vector<Integer>(nodeCount + 1);colIndex = new Vector<Integer>(edgeSize);colPtr = new Vector<Integer>(nodeCount + 1);(int i = 0; i < nodeCount; ++i) {rowPtr.add(-1);colPtr.add(-1);}rowPtr.add(edges.size());colPtr.add(edges.size());// sort the edge based on first nodeEdgeBasedOnFirstNodeComparator cmp = new EdgeBasedOnFirstNodeComparator();Collections.sort(edges, cmp);curNode = edges.elementAt(0).getFirstNode();int curPtr = 0;for (int i = 0; i < edgeSize; ++i) {Edge e = edges.elementAt(i);// System.out.println(“curNode” + curNode + “firstNode: “// + e.getFirstNode());weight.add(e.getWeight());rowIndex.add(e.getSecondNode());if (curNode != e.getFirstNode()) {rowPtr.set(curNode, curPtr);curNode = e.getFirstNode();curPtr = i;}}rowPtr.set(curNode, curPtr);// sort the edge based on second nodeEdgeBasedOnSecondNodeComparator cmp2 = new EdgeBasedOnSecondNodeComparator();Collections.sort(edges, cmp2);// build column index and pointercurNode = edges.elementAt(0).getSecondNode();curPtr = 0;for (int i = 0; i < edgeSize; ++i) {Edge e = edges.elementAt(i);colIndex.add(e.getFirstNode());if (curNode != e.getSecondNode()) {colPtr.set(curNode, curPtr);curNode = e.getSecondNode();curPtr = i;}}colPtr.set(curNode, curPtr);}
获得一个节点的出边
/* * getOutEdges 返回结点所有的出边(即所有由结点指出的边) ** @param node 要查找的结点 ** @return 返回结点所有的出边组成的向量 */@Overridepublic Vector<Edge> getOutEdges(int node) {Vector<Edge> res = new Vector<Edge>();int startIndex = getStartIndex(node, true);if (startIndex == -1) {// 没有出边的点return null;}int endIndex = getEndIndex(node, true);float value;Edge e;int outNode;for (int index = startIndex; index < endIndex; ++index) {value = weight.elementAt(index);outNode = rowIndex.elementAt(index);e = new Edge(node, outNode, value);res.add(e);}return res;}
获得一个节点的入边
一个人行走，若是寂寞了，寻一座霓虹灯迷离闪烁，
