數據結構圖的存儲

『壹』 圖的定義與存儲

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

圖（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）。

『貳』 圖的存儲結構是什麼

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

『叄』 圖的存儲結構有哪些

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

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

『肆』 什麼是數據結構的存儲方式

1. 集合結構：在這種結構中，數據元素之間沒有任何關系，除了它們都屬於同一個集合。
2. 線性結構：線性結構的特點是數據元素之間存在一對一的關系，即每個元素只有一個直接前驅和一個直接後繼。
3. 樹形結構：樹形結構中的數據元素之間存在一對多的關系。這種結構類似於家族樹，其中每個節點（除了根節點）只有一個父節點，但可以有多個子節點。
4. 圖狀結構或網狀結構：在這種結構中，數據元素之間存在多對多的關系。圖可以用來表示網路、路徑或其他任何類型的復雜關系。
(4)數據結構圖的存儲擴展閱讀：數據不僅限於數字，它可以包括文字、字母、數字元號的組合、圖形、圖像、視頻、音頻等，是用來表示客觀事物屬性、數量、位置及其相互關系的抽象表示。例如，「0、1、2…」、「陰、雨、下降、氣溫」、「學生的檔案記錄、貨物的運輸情況」等都是數據。數據經過處理後變成信息。在計算機科學中，數據是指所有能輸入計算機並被計算機程序處理的符號的總稱，這些符號可以是數字、字母、符號和模擬量等。隨著計算機科學的發展，數據的類型和復雜性也在不斷增加。

『伍』 有關圖的存儲結構

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