圖的逆鄰接表存儲結構

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

一、鄰接矩陣存儲方法

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

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

⑵ 請教變成數據結構大神題目。 演算法設計:以鄰接表為儲存結構，編寫一個演算法求有向圖中每個頂點的入度。

鄰接表還是逆鄰接表？如果是逆鄰接表，每個頂點出發鄰接表的鏈表中的結點個數就是入度
如果是鄰接表過程如下：
有一個輔助數組，大小就是頂點數量，所有元素初值都為0
從頭到尾遍歷每個頂點出發的鄰接表的結點，只要當前結點的數據是幾（也就是第幾個結點被有向弧進入了），這個下標的輔助數組元素加1，等所有的鄰接表的小鏈表遍歷完了，這個輔助數組中各個下標的數字就是該頂點的入度

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

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

⑷ 如何用鄰接表存儲圖結構

我看不太懂這個程序，不過我有些過圖的鄰接表表示，看對你有沒有幫助吧。
#include <iostream>
#include <fstream>
#include <vector>

typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //圖的最大頂點數
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局變數--訪問標志數組

typedef struct ArcNode{
//弧結點
int adjvex; //該弧所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條弧的指針
InfoType *info; //保存邊的信息，可以簡單的改為 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

class Graph{
public: AdjList vertices; //記錄頂點信息，指向第一條依附該頂點的弧的指針
int vexnum,arcnum; //圖的當前頂點和弧數
int GraphKind; //圖的種類，0---無向圖，1---有向圖
Graph(int vexnum,int arcnum,int kind)
{
this->vexnum=vexnum;
this->arcnum=arcnum;
this->GraphKind=kind;
}
};
void CreateGraph(Graph &G,VertexType *V,ArcType *VR){
//構造鄰接表結構的圖G

int i;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) //初始化指針數組
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
s->nextarc=G.vertices[VR[i].start].firstarc; //插入到鄰接表中
s->adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;

if(G.GraphKind==0) {
//若是無向圖，再插入到終點的弧鏈中
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.vertices[VR[i].end].firstarc;
s->adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}

⑸ 面試准備之【數據結構】1——圖

共有：鄰接表，鄰接矩陣

有向圖獨有：十字鏈表，邊集數組  

無向圖獨有：鄰接多重表  

一個一維數組存儲圖中頂點信息，一個二維數組（稱為鄰接矩陣）存儲圖中的邊或弧的信息。

設圖G有n個頂點，則鄰接矩陣是一個nxn的方陣，定義為：Arc[i][j]=1,若<vi,vj>∈E或<vi,vj>∈E,反之等於0。

可以看出，無向圖的鄰接矩陣是對稱矩陣，要想知道某個頂點的度，其實就是這個頂點vi在鄰接矩陣中第i行（或第i列）的元素之和。

在有向圖的鄰接矩陣中，某個頂點的出（入）度是這個頂點vi在鄰接矩陣中第i 行（列）的元素之和；

        我們發現，當圖中的邊數相對於頂點較少時，鄰接矩陣是對存儲空間的極大浪費。我們可以考慮對邊或弧使用鏈式存儲的方式來避免空間浪費的問題。回憶樹結構的孩子表示法，將結點存入數組，並對結點的孩子進行鏈式存儲，不管有多少孩子，也不會存在空間浪費問題。

鄰接表的創建過程如下：

1）  圖中頂點用一個一維數組存儲，當然也可以用單鏈表來存儲，不過用數組可以較容易的讀取頂點信息，更加方便。另外，對於頂點數組中，每個數據元素還需要存儲指向第一個鄰接點的指針，以便於查找該頂點的邊信息。

2）  圖中每個頂點vi的所有鄰接點構成一個線性表，由於鄰接點的個數不定，所以用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為以vi為弧尾的出邊表。

從圖中我們知道，頂點表的各個結點由data和firstedge兩個域表示，data是數據域，存儲頂點的信息。

firstedge是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。

邊表結點由adjvex和next兩個域組成。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標，next則存儲指

向邊表中下一個結點的指針，比如v1頂點與v0、v2互為鄰接點，則在v1的邊表中，adjvex分別為v0的0和v2的2.

如果想知道某個頂點的度，就去查找這個頂點的邊表中結點的各數。

若要判斷頂點vi和vj是否存在邊，只需要測試頂點vi的邊表adjvex中是否存在結點vj的下標就行了。

若求頂點的所有鄰接點，其實就是對此頂點的邊表進行遍歷，得到的adjvex域對應的頂點就是鄰接點。

有向圖的鄰接表中頂點vi的邊表是指以vi 為弧尾 的弧來存儲的，這樣很容易就可以得到每個頂點的出度。

有時為了便於確定頂點的入度或以頂點為弧頭的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點vi都建立

一個鏈接為vi為弧頭的表。如下圖所示：

此時我們很容易就可以算出某個頂點的入度或出度是多少，判斷兩頂點是否存在弧也很容易實現。

對於帶權值的網圖，可以在邊表結點定義中再增加一個weight的數據域，存儲權值信息即可

對於有向圖來說，鄰接表是有缺陷的。關心了出度問題，想了解入度就必須要遍歷整個圖才能知道。反之，逆鄰接表解決了入度

卻不了解出度的情況。有沒有可能把鄰接表和逆鄰接表結合起來呢？

答案是肯定的，就是把它們整合在一起。這種存儲有向圖的方法是：十字鏈表（Orthogonal List）.

我們重新定義頂點表結點結構為：   

|    data    |     firstin   |    firstout    |

其中firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結點，firstout表示出邊表頭指針，指向該頂點的出邊表中的第一個結點。

重新定義的 邊表 結點結構如下表：

|    tailvex    |    headvex    |    headlink    |    taillink    |

其中tailvex是指弧起點在頂點表的下標，headvex是指弧終點在頂點表中的下標，headlink是指入邊表指針域，指向終點（弧頭）相同的

下一條邊，taillink是指出邊表指針域，指向起點（弧尾）相同的下一條邊。如果是帶權值的網，還可以再增加一個weight域來存儲權值。

如下圖表示的十字鏈表：

頂點表依然是存入一個一維數組{v0,v1,v2,v3},以頂點v0來說，firstout指向的是出邊表中的第一個結點v3。所以v0邊表結點的headvex=3,

而tailvex其實就是當前頂點v0的下標0，由於v0隻有一個出邊頂點，所以headlink和taillink都是空。

這里虛線箭頭的含義，其實就是逆鄰接表的表示。對於v0來說，它有兩條入邊，分別來自頂點v1和v2。因此v0的firstin指向頂點v1的邊表

結點中headvex為0的結點，虛線（1），接著由入邊結點的headlink指向下一個入邊頂點v2，虛線（2）。

對於頂點v1,它有一個入邊頂點v2，2個出邊頂點v0和v2，所以它的firstin指向頂點v2的邊表結點中headvex為1的結點，虛線（3）.

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在了一起，這樣既容易找到以vi為尾的弧，也容易找到以vi為頭的弧，因而容易求得

頂點的出度和入度。除了結構復雜一點外，其實創建圖演算法的時間復雜度和鄰接表是相同的，因此很好的應用在有向圖中。

十字鏈表主要是針對有向圖的存儲結構進行了優化，那麼對於無向圖的鄰接表，有沒有問題呢？如果我們在無向圖的應用中，關注的重點是頂點，那麼鄰接表是不錯的選擇，但如果我們更關注邊的操作，比如對已訪問過的邊做標記，刪除某一條邊等操作，那就意味著需要找到這條邊的兩個邊表結點進行操作。如下圖，若要刪除(v0,v2)這條邊，需要對鄰接表結構中右邊表的兩個結點進行刪除，顯然這是比較繁瑣的。

因此，我們也仿照十字鏈表的方式，對邊表結點的結構進行一些改造，重新定義的邊表結點結構如下表：

|    ivex    |     ilink    |     jvex    |     jlink    |

其中ivex和jvex是指某條邊依附的兩個頂點在頂點表中的下標。ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊。

這就是鄰接多重表結構。如上圖有4個頂點和5條邊，先將邊表結點畫出來。由於是無向圖，所以ivex，jvex正反過來都可以，為了繪圖

方便，都將ivex值設置的與一旁的頂點下標相同。

下面開始連線，首先連線的（1）（2）（3）（4）是將頂點的firstedge指向一條邊，頂點下標要與ivex的值相同。接著，由於頂點v0的(v0,v1)邊的

鄰邊有(v0,v3)和(v0,v2)。因此（5）（6）的連線就是滿足指向下一條依附於頂點v0的邊的目標，注意ilink指向的結點的jvex（ivex）一定要與它本身

的jvex（ivex）的值相同。同理，連線（7）就是指（v1,v0）這條邊，它是相當於頂點v1指向（v1,v2）邊後的下一條。v2有三條邊依附，所以（3）之後就有

了（8）（9）。連線（10）就是頂點v3在連線（4）之後的下一條邊。左圖一共有5條邊，所以右圖有10條連線，完全符合預期。

鄰接多重表與鄰接表的差別， 僅僅是在於同一條邊在鄰接表中用兩個邊表結點表示，而在鄰接多重表中只有一個結點 。這樣對邊的操作就方便

多了，若要刪除左圖的(v0,v2)這條邊，只需要將右圖的（6）（9）的鏈接指向改為^即可。

---- 邊集數組是由兩個一維數組構成。一個是存儲頂點的信息；另一個是存儲邊的信息，這個邊數組每個數據元素由一條邊的起點下標（begin）、終點下標（end）和權（weight）組成。

如上圖所示，邊集數組關注的是邊的集合，在邊集數組中要查找一個頂點的度需要掃描整個邊數組，效率並不高。因此它更適合對邊依次

進行處理的操作，而不適合對頂點相關的操作

路徑長度：路徑上各活動持續時間的總和（即路徑上所有權之和）。

完成工程的最短時間：從工程開始點（源點）到完成點（匯點）的最長路徑稱為完成工程的最短時間。

關鍵路徑：路徑長度最長的路徑稱為關鍵路徑。

二分圖是一類特殊的圖，又稱為雙分圖、二部圖、偶圖。二分圖的頂點可以分成兩個互斥的獨立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點。可以將 U 和 V 當做一個著色：U 中所有頂點為藍色，V 中所有頂點著綠色，每條邊的兩個端點的顏色不同，符合圖著色問題的要求。相反的，非二分圖無法被二著色

完全二分圖 是一種特殊的二分圖，可以把圖中的頂點分成兩個集合，使得第一個集合中的所有頂點都與第二個集合中的所有頂點相連。

歐拉圖是指通過圖（無向圖或有向圖）中所有邊且每邊僅通過一次通路，相應的迴路稱為歐拉迴路。具有歐拉迴路的圖稱為歐拉圖（Euler Graph），具有歐拉通路而無歐拉迴路的圖稱為半歐拉圖。歐拉證明了如下定理： 一個非空連通圖是歐拉圖當且僅當它的每個頂點的度數都是偶數。 由此可得如下結論：一個連通圖有歐拉跡當它至多有兩個度數是奇數的頂點。

AOE網Activity On Edge Network：在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在帶權有向圖中若以頂點表示事件，有向邊表示活動，邊上的權值表示該活動持續的時間，這樣的圖簡稱為AOE網。

圖的存儲結構-鄰接助陣和鄰接表  https://blog.csdn.net/dongyanxia1000/article/details/53582186

圖的存儲結構-十字鏈表和鄰接多重表 https://blog.csdn.net/dongyanxia1000/article/details/53584496

⑹ 鄰接表存儲時，空間復雜度O( n+e)，還是O(n)

O(n+e)，取n次最小權，每次取完會進行n次更新。如果能達到o（n+e），就不需要O(n)。

在有向圖中，描述每個點向別的節點連的邊（點a->點b這種情況）。在無向圖中，描述每個點所有的邊。與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。

對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。

(6)圖的逆鄰接表存儲結構擴展閱讀：

n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。（因為有向圖是單向的）

在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。

n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。

⑺ [數據結構]已知無向圖的鄰接表，求所有的連通分量

圖的鄰接表存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。如詞條概念圖所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。

鄰接表是圖的一種最主要存儲結構,用來描述圖上的每一個點。對圖的每個頂點建立一個容器(n個頂點建立n個容器)，第i個容器中的結點包含頂點Vi的所有鄰接頂點。實際上我們常用的鄰接矩陣就是一種未離散化每個點的邊集的鄰接表。

在有向圖中，描述每個點向別的節點連的邊(點a->點b這種情況)。

在無向圖中，描述每個點所有的邊(點a-點b這種情況)

與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。

工業上有很多非常好的圖庫的實現,例如C++的boost graph庫.如果可以，盡量用這些庫，這樣可以大大提高你的效率。

表示法
注意:

n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和2e個邊表結點。(換句話說，每條邊(i,j)在鄰接表 中出現兩次:一次在關於i的鄰接表中，另一次在關於j的鄰接表中)

有向圖
對於有向圖，vi的鄰接表中每個表結點都對應於以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。

【例】有向圖G6如下圖所示，其中頂點v1的鄰接表上兩個表結點中的頂點序號分別為0和4，它們分別表示從v1射出的兩條邊(簡稱為v1的出邊):<v1，v0>和<v1，v4>。

注意:

n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。(因為有向圖是單向的)

逆鄰接表
在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。

入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。

注意:

n個頂點e條邊的有向圖，它的逆鄰接表表示中有n個頂點表結點和e個邊表結點。