A. 圖的存儲結構
索引結構和hash結構
B. 關於數據結構中圖的儲存方式的選擇
首先你要明白,鄰接鏈表存圖的空間復雜度與圖中邊的數量有關(O(N+E) E表示圖中邊的數目),而數組存圖空間復雜度與點數有關(O(N^2)N表示點數)
看點的數量,如果點的數量不是很大(比如幾百個左右或者更小)那麼二者都可以選擇。
如果點的數量過大的話,用數組存儲稀疏圖會造成大量的空間浪費,此時選擇使用鄰接表更好。
C. 圖的存儲結構是什麼
由於圖的結構比較復雜,任意兩個頂點之間都可能存在關系(邊),無法通過存儲位置表示這種任意的邏輯關系,所以,圖無法採用順序存儲結構。這一點同其他數據結構(如線性表、樹)不同。考慮圖的定義,圖是由頂點和邊組成的,所以,分別考慮如何存儲頂點和邊。圖常用的存儲結構有鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。
D. 圖的存儲結構——所存儲的信息有哪些
一、鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。
設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為圖的邊數。
E. 圖的存儲結構有多少種
主要的吧:
鄰接矩陣、鄰接表
無向圖的鄰接多重表
有向圖的十字鏈表
F. 圖像怎麼儲存在計算機中的
圖像文件存儲的都是每一個像素對應的顏色值。
G. 圖的存儲方式可以是順序存儲也可以是鏈式存儲嗎
是的。
線性表,樹,圖,都可以有順序和鏈式兩種存儲方法。
H. 圖片如何存儲在資料庫當中
頭條的文件就存在資料庫,可能他們取出來就是二進制吧,播放器可以解碼
I. 圖的圖的存儲表示
數組(鄰接矩陣)存儲表示(有向或無向)
鄰接表存儲表示
有向圖的十字鏈表存儲表示
無向圖的鄰接多重表存儲表示
一個不帶權圖中若兩點不相鄰,鄰接矩陣相應位置為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都有路徑,則稱該圖為強連通圖;否則,將其中的極大連通子圖稱為強連通分量。
J. 圖的存儲結構有哪些
最常見的:
順序查找:適合順序結構和鏈式結構
二分查找:適合順序結構
其他的二叉查找樹、B-樹之類有自己的數據結構