圖的存儲(chǔ)結(jié)構(gòu)

1、第7章 圖7.2 圖的存儲(chǔ)結(jié)構(gòu)17.2.1 鄰接矩陣 int ann1.無(wú)向圖的鄰接矩陣 1 如果(vi，vj)E A(i,j)= 0 其它 2.有向圖的鄰接矩陣 1 如果E A(i,j)= 0 其它27.2.1 鄰接矩陣 A1= A2=3鄰接矩陣的特點(diǎn)（1） A(i,i)=0 1in；（2） 無(wú)向圖的鄰接矩陣是對(duì)稱的 A(i,j)=A(j,i) 1in, 1jn； 存入上(下)三角形，需n(n+1)/2個(gè)單元；（3） 無(wú)向圖的鄰接矩陣的第i行(或第i列)非零元素的 個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度 TD(vi )；（4） 有向圖的鄰接矩陣一般不對(duì)稱。 有向圖需要n2個(gè)單元；（5） 有向圖的鄰接矩陣的

2、 第i行非零元素的個(gè)數(shù)是第i個(gè)頂點(diǎn)的出度 OD(vi)； 第j列非零元素的個(gè)數(shù)是第j個(gè)頂點(diǎn)的入度ID(vi)；47.2.1 鄰接矩陣 int ann3. 網(wǎng)（帶權(quán)值的圖）的鄰接矩陣 wij i!=j 且 (vi，vj)E或E A(i,j)= i!=j ，無(wú)邊或弧 0 i=j , 對(duì)角線元素 53. 網(wǎng)（帶權(quán)值的圖）的鄰接矩陣 0 20 30 20 0 40 30 0 50 40 50 0 70 80 70 0 80 0 4562132030405070806const int MaxVertices=10;const int MaxWeight=32767;class AdjMWGraph p

3、rivate:int Vertices10; /頂點(diǎn)信息的數(shù)組int EdgeMaxVerticesMaxVertices; /邊的權(quán)值信息的矩陣int numE; /當(dāng)前的邊數(shù) int numV; /當(dāng)前的頂點(diǎn)數(shù) public: ; /公有函數(shù) private: ; /私有函數(shù) 7.2.2 鄰接矩陣表示的圖類 7class AdjMWGraph private:.；/ 數(shù)據(jù)成員 public:AdjMWGraph(); /構(gòu)造函數(shù)void CreatG(int n,int e); /建立一個(gè)圖的鄰接矩陣void PrintOut(); /輸出圖的鄰接矩陣void Depth(); /對(duì)連通圖

4、深度優(yōu)先遍歷的調(diào)用void DepthF(); /對(duì)非連通圖深度優(yōu)先遍歷 void Broad(); /對(duì)連通圖廣度優(yōu)先遍歷的調(diào)用void BroadF(); /對(duì)非連通圖深度優(yōu)先遍歷private: void Depth(int v, int visited); void Broad(int v,int visited); ;8class AdjMWGraph private: ； / 數(shù)據(jù)成員 public: .； /公有函數(shù) private: /對(duì)連通圖的深度優(yōu)先遍歷，visit為訪問(wèn)標(biāo)記void Depth(int v, int visited); /對(duì)連通圖的廣度優(yōu)先遍歷，visit

5、為訪問(wèn)標(biāo)記void Broad(int v,int visited); ;9/（1）構(gòu)造函數(shù)AdjMWGraph:AdjMWGraph() for( int i=0; i iMaxVertices; i+ ) Verticesi=0; for ( int i=0; iMaxVertices; i+ ) for ( int j=0; jMaxVertices; j+ ) if( i=j ) Edgeij=0;else Edgeij=MaxWeight; /MaxWeight表示無(wú)窮 numE=0; /當(dāng)前邊個(gè)數(shù)初始為0 numV=0; /當(dāng)前頂點(diǎn)個(gè)數(shù)初始為010/（2）建立一個(gè)圖的鄰接矩陣voi

6、d AdjMWGraph:CreatG(int n,int e) int i,vi,vj,w; /w為邊的權(quán)值numE=e; numV=n; coutendl 輸入頂點(diǎn)的信息（整型）： ;for ( i=0; inumV; i+ ) coutn i+1Verticesi; for ( i=0; inumE; i+ ) coutendlvivjw; Edgevi-1vj-1=w; Edgevj-1vi-1=w; /對(duì)于無(wú)向圖 11/（3）輸出圖的鄰接矩陣void AdjMWGraph:PrintOut() int i;coutn 輸出頂點(diǎn)的信息（整型）： endl; for ( i=0; inu

7、mV; i+ ) coutVerticesi ; coutendln 輸出鄰接矩陣 ： ; for ( i=0; inumV; i+ ) coutendli+1: ; for ( int j=0; jnumV ;j+ ) coutEdgeij ; coutendl; 12在主函數(shù)中應(yīng)用int main() AdjMWGraph G0; G0.CreatG(4,5); G0.PrintOut(); _getch(); return 0; /聲明創(chuàng)建一個(gè)對(duì)象G0/調(diào)用建立函數(shù)，4個(gè)頂點(diǎn)5條邊/輸出鄰接矩陣的信息137.2.3 鄰接鏈表 1. 頂點(diǎn)的結(jié)構(gòu)const int MaxVertices=1

8、00;typedef int VerT; /頂點(diǎn)數(shù)據(jù)類型typedef int DistT; /邊的數(shù)據(jù)類型struct item VerT data; /頂點(diǎn)數(shù)據(jù) Edge *adj; /鄰接邊的指針 ;2.數(shù)組（向量） item VerticesMaxVertices; /頂點(diǎn)的數(shù)組 dataadjItem 頂點(diǎn)結(jié)構(gòu)147.2.3 鄰接鏈表 3. 邊的結(jié)構(gòu)struct Edge int dest; /鄰接頂點(diǎn)下標(biāo) DistT weight; /邊的權(quán)值，或更多 Edge *next; /指針;Edge 邊結(jié)構(gòu)destweightnext15167.2.3 鄰接鏈表const int Max

9、Vertices=100;typedef int VerT;typedef int DistT; struct item VerT data; /頂點(diǎn)數(shù)據(jù) Edge *adj; /鄰接邊的指針 ; item VerticesMaxVertices; /頂點(diǎn)的數(shù)組 17const int MaxVertices=10;class AdjTWGraph /鄰接表圖類定義 private: item VerticesMaxVertices; /頂點(diǎn)信息數(shù)組，表頭向量 int numV; /頂點(diǎn)數(shù)組的當(dāng)前元素個(gè)數(shù) int numE; /當(dāng)前邊的條數(shù) public: AdjTWGraph(); /構(gòu)造函

10、數(shù) AdjTWGraph(); /析構(gòu)函數(shù) .； private: /私有函數(shù)7.2.4 鄰接鏈表的圖類 18const int MaxVertices=10;class AdjTWGraph /鄰接表圖類定義 private: .；/ public: AdjTWGraph(); /構(gòu)造函數(shù) AdjTWGraph(); /析構(gòu)函數(shù) void CreatG(int n,int e); /輸入建立鄰接表 void PrintOut(); /輸出數(shù)據(jù)信息 void DepthFirst()； /調(diào)用深度優(yōu)先遍歷 void BroadFirst()； /調(diào)用廣度優(yōu)先遍歷 Private: /私有函數(shù)

11、.； 19class AdjTWGraph /鄰接表圖類定義 private: .；/ public: void DepthFirst() ； /調(diào)用深度優(yōu)先遍歷 void BroadFirst()； /調(diào)用廣度優(yōu)先遍歷 private: /對(duì)連通圖深度優(yōu)先遍歷，visit為訪問(wèn)標(biāo)記 void DepthFirst(int v, int visited); /對(duì)連通圖廣度優(yōu)先遍歷，visit為訪問(wèn)標(biāo)記 void BroadFirst(int v, int visited); ;20/（1）構(gòu)造函數(shù)AdjTWGraph:AdjTWGraph() for ( int i=0; iMaxVertic

12、es; i+ ) Verticesi.data=0; Verticesi.adj=NULL; numV=0;numE=0;012310 0 0 0 Verticesi21（2）析構(gòu)函數(shù)AdjTWGraph:AdjTWGraph(void) for ( int i=1; inext; delete p; p=q; Verticesi.adj=NULL; 1234112342111323344pq22/（3）建立一個(gè)圖的鄰接鏈表void AdjTWGraph:CreatG(int n,int e) int vi,vj; DistT w; numE=e; numV=n; coutn 輸入頂點(diǎn)的信息（

13、整型）： ; for (int i=1; i=numV; i+ ) coutn iVerticesi.data; for ( int i=1; i=numE; i+ ) coutvivjw; 23 /- 在第vi條鏈表上，鏈入邊（vi,vj）的結(jié)點(diǎn) Edge *q=new Edge; q-dest=vj; q-weight=w; q-next=NULL; /vj是vi的鄰接頂點(diǎn)，w是權(quán)值if(Verticesvi.adj=NULL) Verticesvi.adj=q; /第一次插入 else /非第一次插入 Edge *curr=Verticesvi.adj, *pre=NULL; while

14、 (curr!=NULL & curr-destnext; if ( pre=NULL ) /在第一個(gè)結(jié)點(diǎn)前插入 q-next=Verticesvi.adj; Verticesvi.adj=q; else q-next=pre-next; /在其他位置插入 pre-next=q; 24 /-在第vj條鏈表上，鏈入邊（vj,vi）的結(jié)點(diǎn) Edge *p=new Edge; p-dest=vi; p-weight=w; p-next=NULL; if(Verticesvj.adj=NULL) Verticesvj.adj=p; /第一次插入 else /非第一次插入 Edge *curr=Verticesvj.adj,*pre=NULL; while (curr!=NULL & curr-destnext; if ( pre=NULL ) /在第一個(gè)結(jié)點(diǎn)前插入 p-next=Verticesvj.adj; Verticesvj.adj=p; else p-next=pre-next; /在其他位置插入 pre-next=p; /for /函數(shù)結(jié)束25/（4）輸出圖的鄰接表信息函數(shù)void AdjTWGraph:PrintOut() Edge *pre,*curr; for ( int i=1; i=numV; i+ ) coutn 輸