图——图的邻接链表存储结构
1，邻接矩阵法中的残留问题：
1，MatrixGraph 无法动态添加/删除顶点；
2，空间使用率低；
2，改进基本思想：
1，为了进一步提高空间效率，可以考虑使用链表替换数组，将邻接矩阵变换为邻接链表；
2，占用空间就是因为邻接矩阵的问题，没有连接也要占用四个字节的空间，可以考虑无连接不占用空间的情况；
3，数组在定义的时候要指明有多少个元素，这样可能导致浪费，可以用链表，需要的时候再增加，不需要预定义一共有多少个元素；
3，邻接链表法：
1，图中的所有顶点按照编号存储于同一个链表中；
1，原来存储在数组中，这里存储在链表中；
2，每一个顶点对应一个链表，用于存储始发于该顶点的边；
1，链表中包含的信息见 3；
2，将数组改成链表；
3，每一条边的信息包含：起点，终值，权值；
4，不管多高深的设计方法，都是从最基本的设计方法中演变而来的，最基本的设计方法中，都有一些原则性的东西，比如这里使用了将数组变换成链表来节省空间的原则；
5，邻接链表的示例：
1，链表的链表，垂直的是一个链表，而链表每一个数据元素当中还有另一个链表作为成员而存在；
6，设计与实现：
7，边数据类型的设计：
1，因为邻接链表里面存储的就是与边相关的类型的对象了；
2，定义一个邻接链表，链表里面存储的类型为 Edge；
8，顶点数据类型的设计：
9，动态增加/删除顶点：
1，int addVertex()；
1，增加新的顶点，返回顶点编号；
2，增加新的顶点只能在末尾，因为不能打乱之前已经存在的顶点编号顺序；
2，int addVertex(const V& value)；
1，增加新顶点的同时附加数据元素；
3，void removeVertex()；
1，删除最近增加的顶点；
2，只能从末尾删除，将最近添加的顶点删除，不能说删除一个顶点，其它顶点就乱套了；
10，图的邻接链表结构：
1 #ifndef LISTGRAPH_H 2 #define LISTGRAPH_H 3 4 #include "Graph.h" 5 #include "LinkList.h" 6 #include "Exception.h" 7 #include "DynamicArray.h" 8 9 namespace DTLib 10 { 11 12 /* 适用于内存资源受限场合 */ 13 template < typename V, typename E > 14 class ListGraph : public Graph<V, E> 15 { 16 protected: 17 /* 定义顶点 */ 18 struct Vertex : public Object 19 { 20 V* data; // 顶点的数据成员 21 LinkList< Edge<E> > edge; // 邻接链表保存边对象 22 Vertex() 23 { 24 data = NULL; 25 } 26 }; 27 28 /* 定义实际邻接链表 */ 29 LinkList<Vertex*> m_list; // 实际的邻接链表 30 public: 31 /* 构造一个新的有 n 个顶点的 ListGraph 对象 */ 32 ListGraph(unsigned int n = 0) 33 { 34 for(unsigned int i=0; i<n; i++) // 根据参数添加顶点 35 { 36 addVertex(); // 根据参数动态的增加顶点 37 } 38 } 39 40 /* 动态的增加一个新的顶点 */ 41 int addVertex() // O(n) 42 { 43 int ret = -1; 44 Vertex* v = new Vertex(); // 创建堆空间对象 45 46 if( v != NULL ) 47 { 48 m_list.insert(v); // 将顶点加入这个链表 O(n) 49 ret = m_list.length() - 1; // 返回新加结点在链表里面的编号，在最后一个位置 50 } 51 else 52 { 53 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new vertex object ..."); 54 } 55 56 return ret; 57 } 58 59 /*动态的增加一个新的顶点的同时，将值设入 */ 60 int addVertex(const V& value) // O(n) 61 { 62 int ret = addVertex(); // 添加结点 63 64 if( ret >= 0 ) // 增加成功 65 { 66 setVertex(ret, value); // 顶点所在 ret 处值为 value 67 } 68 69 return ret; 70 } 71 72 /* 设置顶点 i 处的值为 value */ 73 bool setVertex(int i, const V& value) // O(n) 74 { 75 int ret = ( (0 <= i) && (i < vCount()) ); // 判断 i 的合法性 76 77 if( ret ) 78 { 79 Vertex* vertex = m_list.get(i); // 将链表中 i 位置处元素取出来, O(n) 80 V* data = vertex->data; // data 指向具体的顶点数据元素 81 82 if( data == NULL ) // 没有指向成功 83 { 84 data = new V(); // 动态的创建一个指向顶点相关的数据元素出来 85 } 86 87 if( data != NULL ) // 创建成功 88 { 89 *data = value; // 创建成功就将参数值 value 传递过去 90 vertex->data = data; // 将 data 保存下来 91 } 92 else 93 { 94 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new vertex value ..."); 95 } 96 } 97 98 return ret; 99 } 100 101 /* 将 i 位置处相关联的顶点数据元素值返回 */ 102 V getVertex(int i) // O(n) 103 { 104 V ret; 105 106 if( !getVertex(i, ret) ) 107 { 108 THROW_EXCEPTION(InvalidParameterException, "Index i is invalid ..."); 109 } 110 111 return ret; 112 } 113 114 /* 将 i 位置处相关联的顶点数据元素值赋值给引用 value */ 115 bool getVertex(int i, V& value) // O(n) 116 { 117 int ret = ( (0 <= i) && (i < vCount()) ); // 判断 i 的合法性 118 119 if( ret ) 120 { 121 Vertex* v = m_list.get(i); // 得到顶点相关数据 O(n) 122 123 if( v->data != NULL ) // 顶点关联数据元素值 124 { 125 value = *(v->data); // 关联就将数据值返回 126 } 127 else // 顶点没有关联数据 128 { 129 THROW_EXCEPTION(InvalidOperationException, "No value assigned to this vertex ..."); 130 } 131 } 132 133 return ret; 134 } 135 136 /* 删除最近添加的顶点 */ 137 void removeVertex() // O(n*n) 138 { 139 if( m_list.length() > 0 ) // 当前图中有顶点 140 { 141 int index = m_list.length() - 1; // 删除最近添加的顶点，免得破坏图的结构 142 Vertex* v = m_list.get(index); // 取出顶点相关的数据元素 O(n) 143 144 if( m_list.remove(index) ) // 首先删除最后一个顶点 145 { 146 /* 这里循环条件的前后分别利用了逗号表达式 */ 147 for(int i=(m_list.move(0), 0); !m_list.end(); i++, m_list.next() ) // 看其他顶点当中有没有和这个顶点相关联的边，有了要删除 148 { 149 /* 当前结点临界链表里，查找与之关联的边，边起点为 i，终点为 index，存在则 pos 非负*/ 150 int pos = m_list.current()->edge.find(Edge<E>(i, index)); // O(n)，返回存在的下标 151 152 if( pos >= 0 ) 153 { 154 m_list.current()->edge.remove(pos); // 删除当前顶点的元素，即相关联的边 155 } 156 } 157 158 delete v->data; // 释放对应顶点数据元素值空间 159 160 delete v; // 顶点自身占用的空间释放掉 161 } 162 } 163 else 164 { 165 THROW_EXCEPTION(InvalidOperationException, "No vertex in current graph ..."); 166 } 167 } 168 169 /* 获取从顶点 i 出发可以抵达的顶点编号，以一个数组的方式返回；遍历顶点 i 就可以得到与之相关的顶点了 */ 171 SharedPointer< Array<int> > getAdgacent(int i) // O(n) 172 { 173 DynamicArray<int>* ret = NULL; 174 175 if( (0 <= i) && (i < vCount()) ) 176 { 177 Vertex* vertex = m_list.get(i); // 从链表中获取与顶点相关的数据元素 O(n) 178 179 ret = new DynamicArray<int>(vertex->edge.length()); // 创建返回值数组，个数是邻接链表中边的个数 180 181 if( ret != NULL ) 182 { 183 /* 这里用了两个逗号表达式 */ 184 for(int k=(vertex->edge.move(0), 0); !vertex->edge.end(); k++, vertex->edge.next()) // O(n) 185 { 186 ret->set(k, vertex->edge.current().e); // 获取邻接顶点边的第二个元素，并将标号设置到要返回的数组中 O(1) 187 } 188 } 189 else 190 { 191 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create ret object ..."); 192 } 193 } 194 else 195 { 196 THROW_EXCEPTION(InvalidParameterException, "Index i is invalid ..."); 197 } 198 199 return ret; 200 } 201 202 /* 判断 i 到 j 顶点边是否连接，能找到就是连接的 */ 203 bool isAdjacent(int i, int j) 204 { 205 return (0 <= i) && (i < vCount()) && (0 <= j) && (j < vCount()) && (m_list.get(i)->edge.find(Edge<E>(i, j)) >= 0); 206 } 207 208 E getEdge(int i, int j) // O(n) 209 { 210 E ret; 211 212 if( !getEdge(i, j, ret) ) 213 { 214 THROW_EXCEPTION(InvalidParameterException, "Edge <i, j> is invalid ..."); 215 } 216 217 return ret; 218 } 219 220 /* 获取从 i 到 j 的边的权值，放在 value 中 */ 221 bool getEdge(int i, int j, E& value) 222 { 223 int ret = ( (0 <= i) && (i < vCount()) && 224 (0 <= j) && (j < vCount()) ); 225 226 if( ret ) // O(n) 227 { 228 Vertex* vertex = m_list.get(i); // 得到顶点 O(n) 229 int pos = vertex->edge.find(Edge<E>(i, j)); // 在顶点的邻接链表中找找是否存在从 i 到 j 的边，存在则 pos 非 O(n) 230 231 if( pos >= 0 ) 232 { 233 value = vertex->edge.get(pos).data; // 取出值O(n) 234 } 235 else 236 { 237 THROW_EXCEPTION(InvalidOperationException, "No valid assigned to this edge ..."); 238 } 239 } 240 241 return ret; 242 } 243 244 /* 设置从 i 到 j 的邻接链表的值，存储在 value 中 */ 245 bool setEdge(int i, int j, const E& value) // O(n) 246 { 247 int ret = ( (0 <= i) && (i < vCount()) && 248 (0 <= j) && (j < vCount()) ); 249 250 if( ret ) 251 { 252 Vertex* vertex = m_list.get(i); // 获得顶点 O(n) 253 int pos = vertex->edge.find(Edge<E>(i, j)); // 查找边是否存在，存在则 pos 非零 O(n) 254 255 if( pos >= 0 ) 256 { 257 ret = vertex->edge.set(pos, Edge<E>(i, j, value)); // 设置邻接链表当中对应位置处的值，用边的构造函数直接赋值 258 } 259 else 260 { 261 ret = vertex->edge.insert(0, Edge<E>(i, j, value)); // 没有边时，插入一条边和边的权值，至于插入到那个位置，无所谓 262 } 263 } 264 265 return ret; 266 } 267 268 /* 删除从 i 开始抵达 j 的边；查找对应邻接链表并删除 */ 269 bool removeEdge(int i, int j) // O(n) 270 { 271 int ret = ( (0 <= j) && (i < vCount()) && 272 (0 <= j) && (j < vCount()) ); 273 274 if( ret ) 275 { 276 Vertex* vertex = m_list.get(i); // 取出感兴趣的边O(n) 277 278 int pos = vertex->edge.find(Edge<E>(i, j)); // 相应顶点中的边是否存在，存在则 pos 非负 O(n) 279 280 if( pos >= 0 ) 281 { 282 ret = vertex->edge.remove(pos); // 删除对应的点 O(n) 283 } 284 } 285 286 return ret; 287 } 288 289 /* 获取图中顶点个数，即链表中元素个数 */ 290 int vCount() // O(1) 291 { 292 return m_list.length(); // O(1) 293 } 294 295 /* 获取边的个数，获取所有顶点的邻边个数之和*/ 296 int eCount() // O(n) 297 { 298 int ret = 0; 299 300 for(m_list.move(0); !m_list.end(); m_list.next()) 301 { 302 ret += m_list.current()->edge.length(); // 累加当前顶点的邻边个数 303 } 304 305 return ret; 306 } 307 308 /* 实现顶点 i 的入度函数 */ 309 int ID(int i) // O(n*n) 310 { 311 int ret = 0; 312 313 if( (0 <= i) && (i < vCount()) ) 314 { 315 for(m_list.move(0); !m_list.end(); m_list.next()) 316 { 317 LinkList< Edge<E> >& edge = m_list.current()->edge; // 定义当前邻接链表别名，方便编程 318 for(edge.move(0); !edge.end(); edge.next()) 319 { 320 if( edge.current().e == i ) // 多少条终止顶点是顶点 i 321 { 322 ret++; 323 324 break; // 每个顶点到另一个顶点的边的个数一般的只有一个，除非两个顶点见有两个权值不一样的有向边 325 } 326 } 327 } 328 } 329 else 330 { 331 THROW_EXCEPTION(InvalidParameterException, "Index i is invalid ..."); 332 } 333 334 return ret; 335 } 336 337 /* 获取顶点 i 的出度 */ 338 int OD(int i) // O(n) 339 { 340 int ret = 0; 341 342 if( (0 <= i) && (i < vCount()) ) 343 { 344 ret = m_list.get(i)->edge.length(); // O(n) 345 } 346 else 347 { 348 THROW_EXCEPTION(InvalidParameterException, "Index i is invalid ..."); 349 } 350 351 return ret; 352 } 353 354 ~ListGraph() 355 { 356 while( m_list.length() > 0 ) 357 { 358 Vertex* toDel = m_list.get(0); 359 360 m_list.remove(0); 361 362 delete toDel->data; 363 364 delete toDel; 365 } 366 } 367 }; 368 369 } 370 371 #endif // LISTGRAPH_H
11，图的邻接链表法的测试代码：
1 #include <iostream> 2 #include "ListGraph.h" 3 4 using namespace std; 5 using namespace DTLib; 6 7 int main() 8 { 9 ListGraph<char, int> g(4); 10 11 g.setVertex(0, 'A'); 12 g.setVertex(1, 'B'); 13 g.setVertex(2, 'C'); 14 g.setVertex(3, 'D'); 15 16 for(int i=0; i<g.vCount(); i++) 17 { 18 cout << i << " : " << g.getVertex(i) << endl; 19 } 20 21 ListGraph<char, int> g1; 22 23 g1.addVertex('A'); 24 g1.addVertex('B'); 25 g1.addVertex('C'); 26 g1.addVertex('D'); 27 28 // g1.removeVertex(); 29 30 for(int i=0; i<g1.vCount(); i++) 31 { 32 cout << i << " : " << g1.getVertex(i) << endl; 33 } 34 35 g1.setEdge(0, 1, 5); 36 g1.setEdge(0, 3, 5); 37 g1.setEdge(1, 2, 8); 38 g1.setEdge(2, 3, 2); 39 g1.setEdge(3, 1, 9); 40 41 cout << "W(0, 1) : " << g1.getEdge(0, 1) << endl; 42 cout << "W(0, 3) : " << g1.getEdge(0, 3) << endl; 43 cout << "W(1, 2) : " << g1.getEdge(1, 2) << endl; 44 cout << "W(2, 3) : " << g1.getEdge(2, 3) << endl; 45 cout << "W(3, 1) : " << g1.getEdge(3, 1) << endl; 46 47 cout << "eCount : " << g1.eCount() << endl; 48 49 // g1.removeEdge(3, 1); 50 // cout << "W(3, 1) : " << g1.getEdge(3, 1) << endl; 51 52 cout << "eCount : " << g1.eCount() << endl; 53 54 SharedPointer< Array<int> > aj = g1.getAdgacent(0); 55 56 for(int i=0; i<aj->length(); i++) 57 { 58 cout << (*aj)[i] << endl; 59 } 60 61 cout << "ID(1) : " << g1.ID(1) << endl; 62 cout << "OD(1) : " << g1.OD(1) << endl; 63 cout << "TD(1) : " << g1.TD(1) << endl; 64 65 g1.removeVertex(); 66 67 cout << "eCount : " << g1.eCount() << endl; 68 69 cout << "W(0, 1) : " << g1.getEdge(0, 1) << endl; 70 cout << "W(1, 2) : " << g1.getEdge(1, 2) << endl; 71 72 return 0; 73 }
12，同链表一样，链表邻接法对结点的操作也有编号，这个是对图的结点操作的一个捷径；
13，小结：
1，邻接链表法使用链表对图相关的数据进行存储；
1，从邻接矩阵改进而来，将数组改进为链表；
2，每一个顶点关联一个链表，用于存储边相关的数据；
3，所有顶点按照编号被组织在同一个链表中；
4，邻接链表法实现的图能够支持动态添加和删除顶点；
优质内容筛选与推荐>>1、三级联动
2、OLTP和 OLAP区别
3、找出最大的数算法
4、Inno Setup info
5、米粉的构造方法和重载