圖的鄰接矩陣和鄰接表相互轉(zhuǎn)換.doc

圖的鄰接矩陣和鄰接表相互轉(zhuǎn)換圖的鄰接矩陣存儲(chǔ)方法具有如下幾個(gè)特征：1)無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。2）對(duì)于無向圖的鄰接矩陣的第i行非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度。3）對(duì)于有向圖，鄰接矩陣的第i行非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度（或入度）。4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所發(fā)費(fèi)得時(shí)間代價(jià)大。鄰接表是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，在邊稀疏的情況下，用鄰接表表示圖比鄰接矩陣存儲(chǔ)空間。在無向圖的鄰接表中，頂點(diǎn)的度恰好是第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)，而在有向圖中，第i個(gè)鏈表中結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)的出度。在建立鄰接表或鄰逆接表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)的編號(hào)，則建立臨接表的時(shí)間復(fù)雜度是；否則，需要通過查找才能得到頂點(diǎn)在圖中位置，則時(shí)間復(fù)雜度為。在鄰接表上容易找到任意一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧，則需要搜索第i個(gè)或第j個(gè)鏈表，因此，不及鄰接矩陣方便。鄰接矩陣和鄰接表相互轉(zhuǎn)換程序代碼如下：#include#define MAX 20/圖的鄰接表存儲(chǔ)表示typedef struct ArcNodeint adjvex; /弧的鄰接定點(diǎn)char info; /鄰接點(diǎn)值struct ArcNode *nextarc; /指向下一條弧的指針ArcNode;typedef struct Vnode /節(jié)點(diǎn)信息char data;ArcNode *link;Vnode,AdjListMAX;typedef struct AdjList vertices; int vexnum; /節(jié)點(diǎn)數(shù)int arcnum; /邊數(shù)ALGraph;/圖的鄰接矩陣存儲(chǔ)表示typedef struct int n; /頂點(diǎn)個(gè)數(shù)char vexsMAX; /定點(diǎn)信息int arcsMAXMAX; /邊信息矩陣AdjMatrix;/*_*/函數(shù)名：AdjListToMatrix(AdjList g1,AdjListMatrix &gm,int n)/參數(shù)：（傳入）AdjList g1圖的鄰接表,（傳入）int n頂點(diǎn)個(gè)數(shù)，（傳出）AdjMatrix gm圖的鄰接矩陣/功能：把圖的鄰接表表示轉(zhuǎn)換成圖的鄰接矩陣表示void AdjListToAdjMatrix(ALGraph gl,AdjMatrix &gm)int i,j,k;ArcNode *p;gm.n=gl.vexnum;for(k=0;kgl.vexnum;k+)gm.vexsk=gl.verticesk.data;for(i=0;iMAX;i+)for(j=0;jMAX;j+)gm.arcsij=0; for(i=0;iadjvex=1;p=p-nextarc; /*_*/函數(shù)名：AdjMatrixToAdjListvoid AdjMatrixToAdjList(AdjMatrix gm,ALGraph &gl)int i,j,k,choice;ArcNode *p;k=0;gl.vexnum=gm.n;coutchoice;for(i=0;igm.n;i+)gl.verticesi.data=gm.vexsi;gl.verticesi.link=NULL;for(i=0;igm.n;i+)for(j=0;jadjvex=j;p-info=gm.vexsj;p-nextarc=gl.verticesi.link;gl.verticesi.link=p; if(choice=1)k=k/2;gl.arcnum=k;void CreateAdjList(ALGraph &G)int i,s,d,choice;ArcNode *p;coutchoice;cout請(qǐng)輸入節(jié)點(diǎn)數(shù)和邊數(shù)：G.vexnumG.arcnum;for(i=0;iG.vexnum;i+)cout第iG.verticesi.data;G.verticesi.link=NULL;if(choice=1)for(i=0;i2*(G.vexnum);i+)coutsd;p=new ArcNode;p-adjvex=d;p-info=G.verticesd.data;p-nextarc=G.verticess.link;G.verticess.link=p;elsefor(i=0;iG.vexnum;i+)coutsd;p=new ArcNode;p-adjvex=d;p-info=G.verticesd.data;p-nextarc=G.verticess.link;G.verticess.link=p;void CreateAdjMatrix(AdjMatrix &M)int i,j,k,choice;coutM.n; cout請(qǐng)輸入如頂點(diǎn)信息:endl;for(k=0;kM.vexsk;coutchoice;cout請(qǐng)輸入邊信息：endl;for(i=0;iM.n;i+)for(j=0;jM.n;j+)M.arcsij=0;switch(choice)case 1:for(k=0;kij;M.arcsij=M.arcsji=1; ;break;case 2:for(k=0;kij;M.arcsij=1; ;break;void OutPutAdjList(ALGraph &G)int i;ArcNode *p;cout圖的鄰接表如下：endl;for(i=0;iG.vexnum;i+)coutG.verticesi.data;p=G.verticesi.link;while(p!=NULL)cout(adjvex infonextarc;coutendl;void OutPutAdjMatrix(AdjMatrix gm)cout圖的鄰接矩陣如下：endl;for(int i=0;igm.n;i+)for(int j=0;jgm.n;j+)coutgm.arcsij;coutendl;void main()ALGraph gl1,gl2;AdjMatrix gm1,gm2;CreateAdjList(gl1);AdjListToAdjMatrix(