圖有等存儲結構

① 圖的存儲結構有哪些

最常見的：
順序查找：適合順序結構和鏈式結構
二分查找：適合順序結構

其他的二叉查找樹、B-樹之類有自己的數據結構

② 圖的五種存儲結構

圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。

假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：

鄰接矩陣法實現帶權值的無向圖的創建如下：

按照如圖輸入各邊（不重復）

測試程序如下：

結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。

鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。

在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲

鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。

鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：

從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。

假設現在有一有向圖G，如下圖：

無向圖的鄰接表創建示例如下：

假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：

鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。

十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：

現在有一有向圖如下圖：

則它的存儲結構示意圖為：

其定義如下：

十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。

在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：

它的鄰接多重表結構為：

多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。

邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：

邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。

③ 《數據結構》 常見的圖的存儲結構包括了哪些

矩陣，鏈表

④ 有關圖的存儲結構

(1)順序存儲方法
該方法把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。
由此得到的存儲表示稱為順序存儲結構 (Sequential Storage Structure)，通常藉助程序語言的數組描述。
該方法主要應用於線性的數據結構。非線性的數據結構也可通過某種線性化的方法實現順序存儲。 (2)鏈接存儲方法
該方法不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系由附加的指針欄位表示。由此得到的存儲表示稱為鏈式存儲結構(Linked Storage Structure),通常藉助於程序語言的指針類型描述。

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

一、鄰接矩陣存儲方法

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

設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為圖的邊數。

⑥ 計算機考研：數據結構常用演算法解析(7)

第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

⑦ 存儲結構有哪幾種

存儲結構有：

1、鏈接存儲：在計算機中用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。

例：鏈。

2、順序存儲：在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素，稱作線性表的順序存儲結構。

例：數組，鏈。

3、索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址，索引表由若干索引項組成。

例：線索樹。

4、散列存儲：散列存儲，又稱hash存儲，是一種力圖將數據元素的存儲位置與關鍵碼之間建立確定對應關系的查找技術。

例：棧（既可以通過順序存儲也可以同通過隨機存儲）。

順序存儲和鏈接存儲的基本原理：

在順序存儲中，每個存儲空間含有所存元素本身的信息，元素之間的邏輯關系是通過數組下標位置簡單計算出來的線性表的順序存儲，若一個元素存儲在對應數組中的下標位置為i，則它的前驅元素在對應數組中的下標位置為i-1，它的後繼元素在對應數組中的下標位置為i+1。

在鏈式存儲結構中，存儲結點不僅含有所存元素本身的信息，而且含有元素之間邏輯關系的信息。

在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同。

而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。

⑧ 圖的存儲結構是什麼

由於圖的結構比較復雜，任意兩個頂點之間都可能存在關系（邊），無法通過存儲位置表示這種任意的邏輯關系，所以，圖無法採用順序存儲結構。這一點同其他數據結構（如線性表、樹）不同。考慮圖的定義，圖是由頂點和邊組成的，所以，分別考慮如何存儲頂點和邊。圖常用的存儲結構有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。