圖的鄰接矩陣存儲

Ⅰ 圖的存儲結構——所存儲的信息有哪些

一、鄰接矩陣存儲方法

鄰接矩陣是表示頂點之間相鄰關系的矩陣。

設G=(V，E)是具有n（n＞0）個頂點的圖，頂點的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：

（1）如果G是無向圖，則：

A[i][j]=1：若(i,j)∈E(G) 0:其他

（2）如果G是有向圖，則：

A[i][j]=1：若<i,j>∈E(G) 0:其他

（3）如果G是帶權無向圖，則：

A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他

（4）如果G是帶權有向圖，則：

A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他

注意：帶權圖和不帶權圖表示的元素類型不同。

帶權圖（不論有向還是無向圖）A[i][j]用double表示，不帶權圖（不論有向還是無向圖）A[i][j]用int表示。

用一維數組G[ ]存儲有4個頂點的無向圖如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

則頂點2和頂點0之間是有邊的。

如：

鄰接矩陣的特點如下：

（1）圖的鄰接矩陣表示是唯一的。

（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。

（3）不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣。因此，當圖的頂點較多時，可以採用三元組表的方法存儲鄰接矩陣。

（4）對於無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度。

（5）對於有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度（或入度）。

（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

鄰接矩陣的數據類型定義如下：

#define MAXV <最大頂點個數>

typedef struct

{ int no; //頂點編號

InfoType info; //頂點其他信息

} VertexType; //頂點類型

typedef struct //圖的定義

{ int edges[MAXV][MAXV]; //鄰接矩陣

int n，e; //頂點數，弧數

VertexType vexs[MAXV]; //存放頂點信息

} MGraph; //圖的鄰接矩陣表示類型

二、 鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。

在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的節點表示依附於頂點i的邊（對有向圖是以頂點i為尾的邊）。每個單鏈表上附設一個表頭節點。

其中，表節點由三個域組成，adjvex指示與頂點i鄰接的點在圖中的位置，nextarc指示下一條邊或弧的節點，info存儲與邊或弧相關的信息，如權值等。

表頭節點由兩個域組成，data存儲頂點i的名稱或其他信息，firstarc指向鏈表中第一個節點。

typedef struct ANode

{ int adjvex; //該邊的終點編號

struct ANode *nextarc; //指向下一條邊的指針

InfoType info; //該邊的相關信息

} ArcNode; //邊表節點類型

typedef struct Vnode

{ Vertex data; //頂點信息

ArcNode *firstarc; //指向第一條邊

} VNode; //鄰接表頭節點類型

typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型

typedef struct

{ AdjList adjlist; //鄰接表

int n,e; //圖中頂點數n和邊數e

} ALGraph; //完整的圖鄰接表類型

鄰接表的特點如下：

（1）鄰接表表示不唯一。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的演算法以及邊的輸入次序。

（2）對於有n個頂點和e條邊的無向圖，其鄰接表有n個頂點節點和2e個邊節點。顯然，在總的邊數小於n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。

（3）對於無向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目正好是頂點i的度。

（4）對於有向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目僅僅是頂點i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點數目。

例， 給定一個具有n個節點的無向圖的鄰接矩陣和鄰接表。

（1）設計一個將鄰接矩陣轉換為鄰接表的演算法；

（2）設計一個將鄰接表轉換為鄰接矩陣的演算法；

（3）分析上述兩個演算法的時間復雜度。

解：

（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素後創建一個表節點並在鄰接表對應的單鏈表中採用前插法插入該節點。

void MatToList(MGraph g，ALGraph *&G)

//將鄰接矩陣g轉換成鄰接表G

{ int i，j，n=g.n; ArcNode *p; //n為頂點數

G=(ALGraph *)malloc(sizeof(ALGraph));

for (i=0;i<n;i++) //給所有頭節點的指針域置初值

G->adjlist[i].firstarc=NULL;

for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0)

{ p=(ArcNode *)malloc(sizeof(ArcNode));

//創建節點*p

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

//將*p鏈到鏈表頭

G->adjlist[i].firstarc=p;

}

G->n=n;G->e=g.e;

}

（2）在鄰接表上查找相鄰節點，找到後修改相應鄰接矩陣元素的值。

void ListToMat(ALGraph *G，MGraph &g)

{ int i，j，n=G->n;ArcNode *p;

for (i=0;i<n;i++)

{ p=G->adjlist[i].firstarc;

while (p!=NULL)

{ g.edges[i][p->adjvex]=1;

p=p->nextarc;

}

}

g.n=n;g.e=G->e;

}

（3）演算法1的時間復雜度均為O(n2)。演算法2的時間復雜度為O(n+e)，其中e為圖的邊數。

Ⅱ 有向圖的鄰接表存儲如圖所示，請畫出其鄰接矩陣存儲結構

有向圖的鄰接表存儲如圖所示，其鄰接矩陣存儲如圖：

Ⅲ 若具有n個頂點的無向圖採用鄰接矩陣存儲方法，該鄰接矩陣一定為一個什麼矩陣

原則上的確是n的平方，不過由於無向圖的鄰接矩陣是一個對稱矩陣，只需要存儲下三角或者上三角的元素，個數就是從1加到n，就是n（n+1）/ 2，這是壓縮存儲，是用一維數組存放，一般好像不叫矩陣。

其實更精確地說，上面的數字個數是普通對稱矩陣的，這個鄰接矩陣的對角線一定為0，所以，只需要存儲1加到n-1，也就是n(n-1)/2就可以了。

用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關系（邊或弧）的數據，這個二維數組稱為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣。

(3)圖的鄰接矩陣存儲擴展閱讀：

對無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，有向圖則不一定如此。

在無向圖中，任一頂點i的度為第i列（或第i行）所有非零元素的個數，在有向圖中頂點i的出度為第i行所有非零元素的個數，而入度為第i列所有非零元素的個數。

用鄰接矩陣法表示圖共需要n^2個空間，由於無向圖的鄰接矩陣一定具有對稱關系，所以扣除對角線為零外，僅需要存儲上三角形或下三角形的數據即可，因此僅需要n（n-1）/2個空間。

Ⅳ 圖的圖的存儲表示

數組（鄰接矩陣）存儲表示（有向或無向）
鄰接表存儲表示
有向圖的十字鏈表存儲表示
無向圖的鄰接多重表存儲表示
一個不帶權圖中若兩點不相鄰，鄰接矩陣相應位置為0，對帶權圖(網)，相應位置為∞。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一。在鄰接表中，對圖中每個頂點建立一個單鏈表（並按建立的次序編號），第i個單鏈表中的結點表示依附於頂點vi的邊（對於有向圖是以頂點vi為尾的弧）。每個結點由兩個域組成：鄰接點域(adjvex)，用以指示與vi鄰接的點在圖中的位置，鏈域(nextarc)用以指向依附於頂點vi的下一條邊所對應的結點。如果用鄰接表存放網（帶權圖）的信息，則還需要在結點中增加一個存放權值的域（info）。每個頂點的單鏈表中結點的個數即為該頂點的出度(與該頂點連接的邊的總數)。無論是存儲圖或網，都需要在每個單鏈表前設一表頭結點，這些表頭結點的第一個域data用於存放結點vi的編號i，第二個域firstarc用於指向鏈表中第一個結點。
在上面兩個圖結構中，一個是有向圖，即每條邊都有方向，另一個是無向圖，即每條邊都沒有方向。
在有向圖中，通常將邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾，記作<vi,vj>，它表示從頂點vi到頂點vj有一條邊。
若有向圖中有n個頂點，則最多有n(n-1)條弧，我們又將具有n(n-1)條弧的有向圖稱作有向完全圖。以頂點v為弧尾的弧的數目稱作頂點v的出度，以頂點v為弧頭的弧的數目稱作頂點v的入度。在無向圖中，邊記作(vi,vj)，它蘊涵著存在< vi,vj>和<vj,vi>兩條弧。若無向圖中有n個頂點，則最多有n(n-1)/2條弧，我們又將具有n(n-1)/2條弧的無向圖稱作無向完全圖。與頂點v相關的邊的條數稱作頂點v的度。
路徑長度是指路徑上邊或弧的數目。
若第一個頂點和最後一個頂點相同，則這條路徑是一條迴路。
若路徑中頂點沒有重復出現，則稱這條路徑為簡單路徑。
在無向圖中，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點之間都連通，則稱該圖為連通圖，否則，將其中的極大連通子圖稱為連通分量。
在有向圖中，如果對於每一對頂點vi和vj，從vi到vj和從vj到vi都有路徑，則稱該圖為強連通圖；否則，將其中的極大連通子圖稱為強連通分量。