日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

　　圖的應(yīng)用恐怕是C++所有數(shù)據(jù)結(jié)構(gòu)中最寬泛的了，但這也注定了在講“數(shù)據(jù)結(jié)構(gòu)的圖”的時候沒什么好講的——關(guān)于圖的最重要的是算法，而且相當(dāng)?shù)囊徊糠侄际呛軐I(yè)的，一般的人幾乎不會接觸到;相對而言，結(jié)構(gòu)就顯得分量很輕。你可以看到關(guān)于圖中元素的操作很少，遠沒有單鏈表那里列出的一大堆“接口”?！粋€結(jié)構(gòu)如果復(fù)雜，那么能確切定義的操作就很有限。

成都做網(wǎng)站、網(wǎng)站制作,成都做網(wǎng)站公司-創(chuàng)新互聯(lián)已向近1000家企業(yè)提供了,網(wǎng)站設(shè)計,網(wǎng)站制作,網(wǎng)絡(luò)營銷等服務(wù)!設(shè)計與技術(shù)結(jié)合,多年網(wǎng)站推廣經(jīng)驗,合理的價格為您打造企業(yè)品質(zhì)網(wǎng)站。

　　筆者從基本儲存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動網(wǎng)絡(luò)(AOV、AOE)六個方面詳細介紹圖的應(yīng)用。本文是這次系列文章的***篇，主要介紹圖的基本存儲方法。

　　基本儲存方法

　　不管怎么說，還是先得把圖存起來。不要看書上列出了好多方法，根本只有一個——鄰接矩陣。如果矩陣是稀疏的，那就可以用十字鏈表來儲存矩陣(見C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之稀疏矩陣)。如果我們只關(guān)系行的關(guān)系，那么就是鄰接表(出邊表);反之，只關(guān)心列的關(guān)系，就是逆鄰接表(入邊表)。

　　下面給出兩種儲存方法的實現(xiàn)。

 
 
 

  
  
  
#ifndef Graphmem_H  
  
  
  
#define Graphmem_H  
  
  
  
 
  
  
  
#include    
  
  
  
#include    
  
  
  
using namespace std;  
  
  
  
 
  
  
  
template  class Network;  
  
  
  
 
  
  
  
const int maxV = 20;//***節(jié)點數(shù)  
  
  
  
template   
  
  
  
class AdjMatrix  
  
  
  
{  
  
  
  
friend class Network  >;   
  
  
  
public:  
  
  
  
AdjMatrix() : vNum(0), eNum(0)  
  
  
  
{  
  
  
  
vertex = new name[maxV]; edge = new dist*[maxV];  
  
  
  
for (int i = 0; i < maxV; i++) edge[i] = new dist[maxV];  
  
  
  
}  
  
  
  
~AdjMatrix()  
  
  
  
{  
  
  
  
for (int i = 0; i < maxV; i++) delete []edge[i];  
  
  
  
delete []edge; delete []vertex;  
  
  
  
}  
  
  
  
bool insertV(name v)  
  
  
  
{  
  
  
  
if (find(v)) return false;  
  
  
  
vertex[vNum] = v;  
  
  
  
for (int i = 0; i < maxV; i++) edge[vNum][i] = NoEdge;  
  
  
  
vNum++; return true;  
  
  
  
}  
  
  
  
bool insertE(name v1, name v2, dist cost)  
  
  
  
{  
  
  
  
int i, j;  
  
  
  
if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;  
  
  
  
if (edge[i][j] != NoEdge) return false;  
  
  
  
edge[i][j] = cost; eNum++; return true;  
  
  
  
}  
  
  
  
name& getV(int n) { return vertex[n]; } //沒有越界檢查  
  
  
  
int nextV(int m, int n)//返回m號頂點的第n號頂點后***個鄰接頂點號，無返回-1  
  
  
  
{  
  
  
  
for (int i = n + 1; i < vNum; i++) if (edge[m][i] != NoEdge) return i;  
  
  
  
return -1;  
  
  
  
}  
  
  
  
private:  
  
  
  
int vNum, eNum;  
  
  
  
dist NoEdge, **edge; name *vertex;  
  
  
  
bool find(const name& v)  
  
  
  
{  
  
  
  
for (int i = 0; i < vNum; i++) if (v == vertex[i]) return true;  
  
  
  
return false;  
  
  
  
}  
  
  
  
bool find(const name& v, int& i)  
  
  
  
{  
  
  
  
for (i = 0; i < vNum; i++) if (v == vertex[i]) return true;  
  
  
  
return false;  
  
  
  
}  
  
  
  
};  
  
  
  
 
  
  
  
template   
  
  
  
class LinkedList  
  
  
  
{  
  
  
  
friend class Network  >;   
  
  
  
public:  
  
  
  
LinkedList() : vNum(0), eNum(0) {}  
  
  
  
~LinkedList()  
  
  
  
{  
  
  
  
for (int i = 0; i < vNum; i++) delete vertices[i].e;  
  
  
  
}  
  
  
  
bool insertV(name v)  
  
  
  
{  
  
  
  
if (find(v)) return false;  
  
  
  
vertices.push_back(vertex(v, new list ));   
  
  
  
vNum++; return true;  
  
  
  
}  
  
  
  
bool insertE(const name& v1, const name& v2, const dist& cost)  
  
  
  
{  
  
  
  
int i, j;  
  
  
  
if (v1 == v2 || !find(v1, i) || !find(v2, j)) return false;  
  
  
  
for (list ::iterator iter = vertices[i].e->begin();   
  
  
  
iter != vertices[i].e->end() && iter->vID < j; iter++);  
  
  
  
if (iter == vertices[i].e->end())  
  
  
  
{  
  
  
  
vertices[i].e->push_back(edge(j, cost)); eNum++; return true;  
  
  
  
}  
  
  
  
if (iter->vID == j) return false;  
  
  
  
vertices[i].e->insert(iter, edge(j, cost)); eNum++; return true;  
  
  
  
}  
  
  
  
name& getV(int n) { return vertices[n].v; } //沒有越界檢查  
  
  
  
int nextV(int m, int n)//返回m號頂點的第n號頂點后***個鄰接頂點號，無返回-1  
  
  
  
{  
  
  
  
for (list ::iterator iter = vertices[m].e->begin();   
  
  
  
iter != vertices[m].e->end(); iter++) if (iter->vID > n) return iter->vID;  
  
  
  
return -1;  
  
  
  
}  
  
  
  
 
  
  
  
private:  
  
  
  
bool find(const name& v)  
  
  
  
{  
  
  
  
for (int i = 0; i < vNum; i++) if (v == vertices[i].v) return true;  
  
  
  
return false;  
  
  
  
}  
  
  
  
bool find(const name& v, int& i)  
  
  
  
{  
  
  
  
for (i = 0; i < vNum; i++) if (v == vertices[i].v) return true;  
  
  
  
return false;  
  
  
  
}  
  
  
  
struct edge  
  
  
  
{  
  
  
  
edge() {}  
  
  
  
edge(int vID, dist cost) : vID(vID), cost(cost) {}  
  
  
  
int vID;  
  
  
  
dist cost;  
  
  
  
};  
  
  
  
struct vertex  
  
  
  
{  
  
  
  
vertex() {}  
  
  
  
vertex(name v, list * e) : v(v), e(e) {}   
  
  
  
name v;  
  
  
  
list * e;   
  
  
  
};  
  
  
  
int vNum, eNum;  
  
  
  
vector  vertices;   
  
  
  
};  
  
  
  
 
  
  
  
#endif 
 
 
 

　　這個實現(xiàn)是很簡陋的，但應(yīng)該能滿足后面的講解了?，F(xiàn)在這個還什么都不能做，不要急，在下篇將講述圖的DFS和BFS。

【編輯推薦】

1. 經(jīng)典四講貫通C++排序之一 插入排序
2. c++編程常用工具
3. 給C++初學(xué)者的50個忠告
4. c++最基礎(chǔ)的20條規(guī)則
5. 程序員必看 c++筆試題匯總

當(dāng)前文章：六講貫通C++圖的應(yīng)用之一基本儲存方法
轉(zhuǎn)載源于：http://www.5511xx.com/article/cdjoidh.html