A 定義
圖是有頂點集合(Vertex)及頂點間的關(guān)系集合(Edge)組成的一種數(shù)據(jù)結(jié)構(gòu)
Graph=(V,E)
無向邊
1.頂點x和y之間的邊沒有方向,則稱該邊為 無向邊
2.(x,y)與(y,x)意義相同，表示x和y之間有連接
無向圖
圖中任意兩個頂點之間的邊均是無向邊，則稱該圖為無向圖
有向邊
1.頂點x和y之間的邊有方向，則稱該邊為有向邊
2.
有向圖
圖中任意兩個頂點之間的邊鈞是有向邊，則稱該圖為有向圖
頂點鄰接的定義
1.無向圖--如果(x,y)屬于E,則稱x和y互為鄰接
2.有向圖--如果
度(Degree)的定義
1.頂點v的度是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)
a.入度:以v為頭的邊的數(shù)目，記為ID(v)
b.出度:以v為尾的邊的數(shù)目，記為OD(v)
權(quán)(Weight)的定義
1.與圖的邊相關(guān)的數(shù)據(jù)元素叫權(quán)
2.權(quán)常用來表示圖中頂點間的距離或者耗費
圖的一些常用操作
1.設(shè)置頂點的值 2.獲取頂點的值 3.獲取鄰接頂點 4.設(shè)置邊的值
5.刪除邊 6.獲取頂點數(shù) 等等
重慶分公司
重慶分公司
template
class Graph:public Object
{
public:
virtual V getVertex(int x)=0;
virtual bool getVertex(int x,V& value)=0;
virtual bool setVertex(int i,const V& value)=0;
virtual SharedPointer>getAdjacent(int i)=0;
virtual E getEdge(int i,int j)=0;
virtual bool getEdge(int i, int j,E& value)=0;
virtual bool setEdge(int i, int j,const E& value)=0;
virtual bool removeEdge(int i,int j)=0;
virtual int vCount()=0;
virtual int eCount()=0;
virtual int OD(int i)=0;
virtual int ID(int i)=0;
virtual int TD(int i);
}； 基本思想
1.用一維數(shù)組存儲頂點:描述頂點相關(guān)的數(shù)據(jù)
2.用二維數(shù)組存儲邊:描述頂點間的關(guān)系和權(quán)
鄰接矩陣法
-設(shè)圖A=(V,E)是一個有n個頂點的圖，圖的鄰接矩陣為Edge[n][n],則
實現(xiàn)方法一：直接使用數(shù)組表示頂點集和邊集
template
class MatrixGraph:public Graph
{
protected:
V m_vertexes[N];
E m_edges[N][N];
int m_eCount;
public:
//......
}; 問題：
1.構(gòu)造效率低下--圖對象初始化時，頻繁調(diào)用頂點類型和邊類型的構(gòu)造函數(shù)
2.空間使用率低下--圖對象占用大量空間，而大多數(shù)空間處于閑置狀態(tài)
3.無法表示空值--無法用統(tǒng)一的方式表示為空的情形
實現(xiàn)方式二：使用指針數(shù)組表示頂點集和邊集
template
class MatrixGraph:public Graph
{
protected:
V* m_vertexes[N];
E* m_edges[N][N];
int m_eCount;
public:
//......
}; 問題的解決：
1.構(gòu)造效率--初始化圖像時，只需要將數(shù)組元素賦值為空
2.空間使用率--頂點數(shù)據(jù)元素和邊數(shù)據(jù)元素在需要時動態(tài)創(chuàng)建
3.空值的表示--任意的頂點類型和邊類型都使用NULL表示空值
圖的遍歷
1.廣度優(yōu)先--以二叉樹層次遍歷的思想對圖進行遍歷
2.深度優(yōu)先--以二叉樹先序遍歷的思想對圖進行遍歷
A.廣度優(yōu)先算法
-原料：隊列 LinkQueue
-步驟
1.將起始頂點壓入隊列中
2.隊頭頂點v彈出，判斷是否已經(jīng)標記
3.標記頂點v，并將頂點v的鄰接頂點壓入隊列中
4.判斷隊列是否為空
B.深度優(yōu)先算法
-原料：class LinkStack
-步驟：
1.將起始點壓入棧中
2.彈出棧頂頂點v，判斷是否已經(jīng)標記
3.標記頂點v，并將頂點v的鄰接頂點壓入棧中
4.判斷棧是否為空
代碼實現(xiàn)
SharedPointer>BFS(int i)
{
DynamicArray* ret=NULL;
if((0<=i)&&(iq;
LinkQueuer;
DynamicArrayvisited(vCount());
for(int i=0;i0)
{
int v=q.front();
q.remove();
if(!visited[v])
{
SharedPointer< Array >aj=getAdjacent(v);
for(int j=0;jlength();j++)
{
q.add((*aj)[j]);
}
r.add(v);
visited[v]=true;
}
}
ret=toArray(r);
}
else
{
THROW_EXCEPTION(InvalidParameterException,"0.0");
}
return ret;
}
SharedPointer>DFS(int i)
{
DynamicArray* ret=NULL;
if((0<=i)&&(is;
LinkQueuer;
DynamicArrayvisited(vCount());
for(int j=0;j0)
{
int v=s.top();
s.pop();
if(!visited[v])
{
SharedPointer>aj=getAdjacent(v);
for(int j=aj->length()-1;j>=0;j--)
{
s.push((*aj)[j]);
}
r.add(v);
visited[v]=true;
}
}
ret=toArray(r);
}
else
{
THROW_EXCEPTION(InvalidParameterException,"...");
}
return ret;
} 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
