用鄰接矩陣存儲圖

1. 存儲圖時，哪些情況用鄰接矩陣方便

如果邊比較少的情況下，用鄰接矩陣節省存儲空間。邊比較多就可以選擇鄰接矩陣

2. 圖的定義與存儲

圖狀結構是一種比樹形結構更復雜的非線性結構。在樹形結構中，結點間具有分支層次關系，每一層上的結點只能和上一層的至多一個結點相關，但可能和下一層的多個結點相關。而在圖狀結構中，任意兩個結點之間都可能相關，即結點之間的鄰接關系可以是任意的。因此，圖是 比樹更一般、更復雜的非線性結構，常被用於描述各種復雜的數據對象，在自然科學、社會科學和人文科學等許多領域有著非常廣泛的應用。

圖（Graph）是由非空的頂點集合和一個描述頂點之間的關系——邊（或者弧）的集合組成的，其形式化定義為：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點vi和頂點vj之間有一條直接連線，即偶對(v1,vj）表示一條邊。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

1、無向圖：在一個圖中，如果任意兩個頂點構成的偶對(vi,vj）包含E是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。

2、有向圖：在一個圖中，如果任意兩個頂點構成的偶對<vj,vj>包含E是有序的（有序對常常用尖括弧「<>」表示），即頂點之間的連線是有方向的，則稱該圖為有向圖。

6、頂點的度、入度、出度：頂點的度（Degree）是指依附於某頂點v的邊數，通常記為TD(v)。頂點v的入度是指以頂點v為終點的弧的數目，記為ID(V)；出度是指以頂點v為始點的弧的數目，記為OD(V)。有TD(V)=ID(v)+OD(v)。

7、邊的權、網：與邊有關的數據信息稱為權(Weight)。在實際應用中，權值可以有某種含義。例如，在一個反映城市交通線路的圖中，邊上的權值可以表示該條線路的長度或等級；對於一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值；對於反映工程進度的圖而言，邊上的權值可以表示從前一個工程到後一個工程所需要的時間或其他代價等。邊上帶權的圖稱為網或網路（network）。

8、路徑、路徑長度：頂點vp到頂點vq之間的路徑（path）是指頂點序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分別為圖中的邊。路徑上邊的數目稱為路徑長度。

9、簡單路徑、迴路、簡單迴路：序列中頂點不重復出現的路徑稱為簡單路徑。路徑中第一個頂點與最後一個頂點相同的 路徑稱為迴路或環（Cycle）。除第一個頂點與最後一個頂點之外，其他頂點不重復出現的迴路稱為簡單迴路，或者簡單環。

10、子圖：對於圖G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，則稱圖 G'是G的的一個子圖。

11、連通、連通圖、連通分量：在無向圖中，如果從一個頂點vi到另一個頂點vj(i=!j)存在路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量，極大連通子圖是指在保證連通與子圖的條件下，包含原圖中所有的頂點與邊。 如下圖：

12、強連通圖、強連通分量：對於有向圖來說，若圖中任意一對頂點vi和vj（i=!j）均存在從一個頂點vi到另一個頂點vj和從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量，極大強連通子圖的含義同上。

13、生成樹：所謂連通圖G的生成樹，是G的包含其全部n個頂點的一個極小連通子圖，所謂極小連通子圖是指在包含所有頂點且保證連通的前提下盡可能少地包含原圖中的邊。生成樹必定包含且僅包含連通圖G的n-1條邊。在生成樹中添加任意一條屬於原圖中的邊必定會產生迴路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。

14、生成森林：在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。

將上圖存儲到計算機中，請設計一個數據結構並將其合理存儲起來？

所謂鄰接矩陣（Adjacency Matrix）的存儲結構，就是用一維數組存儲圖中的頂點信息，用矩陣表示圖中各頂點的信息，用矩陣表示圖中各頂點的信息，用矩陣表示圖中各頂點之間的鄰接關系。假設圖G=(V,E)有n個確定的頂點，即V ={v0,v1，···，vn-1}，則表示G中各頂點相鄰關系的矩陣為一個n×n的矩陣，矩陣的元素為：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的邊 ；2，若(vi,vj）或<vi,vj>不是E(G)中的邊。

若G是網，則鄰接矩陣可定義為：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的邊 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的邊。

（1）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上或下三角矩陣的元素即可。

（2）對於無向圖，鄰接矩陣的第i行或第i列非零元素或非&元素的個數正好是第i個頂點的度TD(vi)。

（3）對於有向圖，鄰接矩陣的第i行貨第i列非零元素或非&元素的個數正好是第i個頂點的出度OD(vi)或如度ID(vi)。

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

在實際應用鄰接矩陣存儲圖時，除了用一個二維數組存儲用於表示頂點間相鄰關系的鄰接矩陣外，還需用一個一維數組來存儲頂點信息，另外，還有圖的頂點樹和邊樹。故可將其形式描述如下：

鄰接表（Adjacency List）是圖的一種順序存儲於鏈式存儲結合的存儲方法。鄰接表表示法類似於樹的孩子鏈表表示法。就是對於圖G中的每個頂點vi，將所有鄰接於vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數組中，就構成了圖鄰接表。

在鄰接表表示中有兩種結點結構：一種是頂點表的結點結構，它由頂點域（vertex）和指向第一條鄰接邊的指針域（firstedge）構成。另一種是邊表即鄰接表結點，它由鄰接點域（adjvex）和指向下一條鄰接邊的指針域（next）構成。對於網的邊表需再增設一個存儲邊上的信息（如權值等）的域（info）。

3. 若具有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個空間。

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

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

5. 怎樣用鄰接矩陣為存儲結構創建一個無向圖

int CreateUDG(AdjMatrix *G){
int i,j,k,weight;
VertexData v1,v2;
printf("輸入圖的弧數和頂點數\n");
fflush(stdin);
scanf("%d,%d",&G->arcnum,&G->vexnum); /*輸入圖的頂點數和弧數*/
for(i=0;i<G->vexnum;i++) /*初始化鄰接矩陣*/
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
for(i=0;i<G->vexnum;i++)
{
printf("輸入圖的頂點\n");
fflush(stdin);
scanf("%c",&G->vexs[i]); /* 輸入圖的頂點*/
}
for(k=0;k<G->arcnum;k++)
{
printf("輸入一條弧的兩個頂點及權值\n");
fflush(stdin);
scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個頂點及權值*/
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; /*建立弧*/
}
return(Ok);
}

void main()
{
AdjMatrix G;
CreateDN(&G);
}

6. 有向圖的鄰接矩陣存儲

有向圖的鄰接矩陣，用類似於二維鏈表做過，下面是c++的代碼：

//頂點結構
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧結構
structArcNode
{//鄰接頂點的下標
intadjvex;
ArcNode*nextarc;
};

classAdjList
{
private:
VexNodedata[100];
intvn,an;//頂點數弧數
public:
//構造函數以及其他的一些函數
AdjList();
virtual~AdjList();
};