5-3圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第五章圖圖的存儲(chǔ)結(jié)構(gòu)圖是否可以采用順序存儲(chǔ)結(jié)構(gòu)？在圖中，任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊）無(wú)法通過(guò)存儲(chǔ)位置表示這種任意的邏輯關(guān)系圖無(wú)法采用順序存儲(chǔ)結(jié)構(gòu)如何存儲(chǔ)圖呢？圖是由頂點(diǎn)和邊組成分別考慮如何存儲(chǔ)頂點(diǎn)如何存儲(chǔ)邊圖的鄰接表存儲(chǔ)及實(shí)現(xiàn)圖的鄰接矩陣存儲(chǔ)及實(shí)現(xiàn)學(xué)什么？5-3-1圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第五章圖存儲(chǔ)思想edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它鄰接矩陣也稱數(shù)組表示法，基本思想是：一維數(shù)組：存儲(chǔ)圖中頂點(diǎn)的信息二維數(shù)組（鄰接矩陣）：存儲(chǔ)圖中各頂點(diǎn)之間的鄰接關(guān)系設(shè)G＝(V,E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：存儲(chǔ)示意圖v0v3v2v1v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3無(wú)向圖的鄰接矩陣有什么特點(diǎn)？對(duì)稱矩陣如何求頂點(diǎn)v

的度？第v行（或第v列）非零元素的個(gè)數(shù)如何判斷頂點(diǎn)i和

j之間是否存在邊？if(edge[i][j]==1)0123v0v3v2v1如何求頂點(diǎn)i的所有鄰接點(diǎn)？掃描第

i

行for(j=0;j<n;j++)if(edge[i][j]==1)

頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn)v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v30123存儲(chǔ)示意圖有向圖的鄰接矩陣一定不對(duì)稱嗎？頂點(diǎn)間存在方向相反的弧如何求頂點(diǎn)v

的出度？第v行非零元素的個(gè)數(shù)v0v3v2v1如何求頂點(diǎn)v

的入度？第v列非零元素的個(gè)數(shù)v0v1v2v3vertex=01011010

1

0000

000edge=v0

v1

v2

v3v0v1v2v30123存儲(chǔ)示意圖v0v1v2v3vertex=05

∞

2

508

7

∞

80∞2

7

∞0edge=v0

v1

v2

v3v0v1v2v3v0v3v2v12785網(wǎng)圖的鄰接矩陣可定義為：edge[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他0123存儲(chǔ)示意圖存儲(chǔ)結(jié)構(gòu)定義constintMaxSize=10;template<typenameDataType>classMGraph{public:

MGraph(DataTypea[],intn,inte);

~MGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

DataTypevertex[MaxSize];

intedge[MaxSize][MaxSize];

intvertexNum,edgeNum;};圖的抽象數(shù)據(jù)類型定義？ADTGraphDataModel…Operation

CreateGraph：圖的建立DestroyGraph：圖的銷毀DFTraverse：深度優(yōu)先遍歷圖BFTraverse：廣度優(yōu)先遍歷圖endADTv0v3v2v1v0v1v2v3a=輸入v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3結(jié)果44vertexNumedgeNum圖的建立v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3算法：CreateGraph(a[n],n,e)輸入：頂點(diǎn)的數(shù)據(jù)a[n]，頂點(diǎn)個(gè)數(shù)n，邊的個(gè)數(shù)e輸出：圖的鄰接矩陣1.存儲(chǔ)圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.將頂點(diǎn)信息存儲(chǔ)在一維數(shù)組vertex中；3.初始化鄰接矩陣edge；4.依次輸入每條邊并存儲(chǔ)在鄰接矩陣edge中：4.1輸入邊依附的兩個(gè)頂點(diǎn)的編號(hào)i和j；4.2將edge[i][j]和edge[j][i]的值置為1；44vertexNumedgeNum圖的建立template<typenameDataType>MGraph<DataType>::MGraph(DataTypea[],intn,inte){

inti,j,k;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//存儲(chǔ)頂點(diǎn)

vertex[i]=a[i];

for(i=0;i<vertexNum;i++)//初始化鄰接矩陣

for(j=0;j<vertexNum;j++)

edge[i][j]=0;

for(k=0;k<edgeNum;k++)//依次輸入每一條邊

{

cin>>i>>j;//輸入邊依附的兩個(gè)頂點(diǎn)的編號(hào)

edge[i][j]=1;edge[j][i]=1;//置有邊標(biāo)志

}}圖的建立深度優(yōu)先遍歷v0v1v2v30101101101001100v0

v1

v2

v3v0v1v2v3算法：DFTraverse輸入：頂點(diǎn)的編號(hào)v輸出：圖的深度優(yōu)先遍歷序列1.訪問(wèn)頂點(diǎn)v;修改標(biāo)志visited[v]=1;2.j=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)；3.while(j存在)3.1if(j未被訪問(wèn))從頂點(diǎn)j出發(fā)遞歸執(zhí)行該算法;3.2j=頂點(diǎn)v的下一個(gè)鄰接點(diǎn);0123template<typenameDataType>voidMGraph<DataType>::DFTraverse(intv){

cout<<vertex[v];visited[v]=1;

for(intj=0;j<vertexNum;j++)

if(edge[v][j]==1&&visited[j]==0)

DFTraverse(j);}算法：BFTraverse輸入：頂點(diǎn)的編號(hào)v輸出：圖的廣度優(yōu)先遍歷序列1.隊(duì)列Q初始化;2.訪問(wèn)頂點(diǎn)v;修改標(biāo)志visited[v]=1;頂點(diǎn)v入隊(duì)列Q;3.while(隊(duì)列Q非空)3.1i=隊(duì)列Q的隊(duì)頭元素出隊(duì);3.2j=頂點(diǎn)v的第一個(gè)鄰接點(diǎn);3.3while(j存在)3.3.1如果j未被訪問(wèn)，則

訪問(wèn)頂點(diǎn)j;修改標(biāo)志visited[j]=1;頂點(diǎn)j入隊(duì)列Q；3.3.2j=頂點(diǎn)i的下一個(gè)鄰接點(diǎn)；v0v1v3v2v4廣度優(yōu)先遍歷template<typenameDataType>voidMGraph<DataType>::BFTraverse(intv){

intw,j,Q[MaxSize];

//采用順序隊(duì)列

intfront=-1,rear=-1;

//初始化隊(duì)列

cout<<vertex[v];visited[v]=1;Q[++rear]=v;

//被訪問(wèn)頂點(diǎn)入隊(duì)

while(front!=rear)

//當(dāng)隊(duì)列非空時(shí)

{

w=Q[++front];

//將隊(duì)頭元素出隊(duì)并送到v中

for(j=0;j<vertexNum;j++)

if(edge[w][j]==1&&visited[j]==0){

cout<<vertex[j];visited[j]=1;Q[++rear]=j;

}

}}

廣度優(yōu)先遍歷5-3-2圖的鄰接表存儲(chǔ)結(jié)構(gòu)v第五章圖存儲(chǔ)思想鄰接矩陣存儲(chǔ)結(jié)構(gòu)的空間復(fù)雜度是多少？O(n2)如果采用鄰接矩陣存儲(chǔ)稀疏圖，會(huì)出現(xiàn)什么情況？稀疏矩陣ACBGFEDH12∧345∧7∧68∧∧∧∧∧

01234567

ABCDEFGH

樹的孩子表示法？鄰接表存儲(chǔ)的基本思想是：v0v1v2v3邊表（鄰接表）：頂點(diǎn)v

的所有鄰接點(diǎn)鏈成的單鏈表頂點(diǎn)表：所有邊表的頭指針和存儲(chǔ)頂點(diǎn)信息的一維數(shù)組13∧03∧

0123

v0

v1

v2

v3

3∧102∧adjvexnextvertexfirstEdge存儲(chǔ)思想存儲(chǔ)結(jié)構(gòu)定義v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧structEdgeNode{

intadjvex;EdgeNode*next;};template<typenameDataType>structVertexNode{

DataTypevertex;

EdgeNode*firstEdge;};vertexfirstEdgeadjvexnext基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧邊表中的結(jié)點(diǎn)表示什么？對(duì)應(yīng)圖中的一條邊設(shè)圖有n個(gè)頂點(diǎn)e條邊，鄰接表的空間復(fù)雜度是多少？O(n+e)vertexadjvexnextfirstEdgev0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求頂點(diǎn)v的度？頂點(diǎn)v的邊表中結(jié)點(diǎn)的個(gè)數(shù)p=adjList[v].firstEdge;count=0;while(p!=nullptr){count++;p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求頂點(diǎn)v

的所有鄰接點(diǎn)?頂點(diǎn)i

的邊表中的所有結(jié)點(diǎn)p=adjList[v].firstEdge;while(p!=nullptr){j=p->adjvex;//j是v的鄰接點(diǎn)p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何判斷頂點(diǎn)i

和頂點(diǎn)j之間是否存在邊?測(cè)試頂點(diǎn)i

的邊表中是否存在數(shù)據(jù)域?yàn)閖

的結(jié)點(diǎn)vertexadjvexnextfirstEdge基本操作13∧

0123

v0

v1

v2

v3

0∧02∧v0v1v2v3∧如何求頂點(diǎn)v的出度？頂點(diǎn)v的出邊表中結(jié)點(diǎn)的個(gè)數(shù)如何求頂點(diǎn)v的入度？所有出邊表中數(shù)據(jù)域?yàn)関

的結(jié)點(diǎn)個(gè)數(shù)vertexadjvexnextfirstEdge基本操作存儲(chǔ)帶權(quán)圖鄰接表如何存儲(chǔ)帶權(quán)圖？權(quán)值存儲(chǔ)在邊表中v0v1v2v32785

0123

v0

v1

v2

v3

1235∧0

237∧38∧0

51

728∧adjvexweightnextvertexfirstEdgeconstintMaxSize=10;template<typenameDataType>classALGraph{public:

ALGraph(DataTypea[],intn,inte);

~ALGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

VertexNode<DataType>

adjList[MaxSize];

intvertexNum,edgeNum;};ADTGraphDataModel…Operation

CreateGraph：圖的建立DestroyGraph：圖的銷毀DFTraverse：深度優(yōu)先遍歷圖BFTraverse：廣度優(yōu)先遍歷圖endADT存儲(chǔ)結(jié)構(gòu)定義圖的抽象數(shù)據(jù)類型定義？圖的建立v0v1v2v3a=輸入v0v1v2v3結(jié)果13∧

0123

v0

v1

v2

v3

0∧02∧∧44vertexNumedgeNum算法：CreateGraph(a[n],n,e)輸入：頂點(diǎn)的數(shù)據(jù)信息a[n]，頂點(diǎn)個(gè)數(shù)n，邊的個(gè)數(shù)e輸出：圖的鄰接表1.存儲(chǔ)圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.將頂點(diǎn)信息存儲(chǔ)在頂點(diǎn)表中，將該頂點(diǎn)邊表的頭指針初始化為nullptr；3.依次輸入邊的信息并存儲(chǔ)在邊表中：3.1輸入邊所依附的兩個(gè)頂點(diǎn)的編號(hào)i和j；3.2生成邊表結(jié)點(diǎn)s，其鄰接點(diǎn)的編號(hào)為j； 3.3將結(jié)點(diǎn)s插入到第i個(gè)邊表的表頭；13∧

0123

v0

v1

v2

v3

0∧02∧∧圖的建立

v0

v1

v2

v3

∧∧∧∧template<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//初始化頂點(diǎn)表

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}圖的建立for(k=0;k<edgeNum;k++)//依次輸入每一條邊{cin>>i>>j;//輸入邊所依附的兩個(gè)頂點(diǎn)的編號(hào)s=newEdgeNode;s->adjvex=j;//生成一個(gè)邊表結(jié)點(diǎn)ss->next=adjList[i].firstEdge;//將結(jié)點(diǎn)s插入到第i個(gè)邊表的表頭adjList[i].firstEdge=s;}3∧

0

v0

1stemplate<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}圖的建立在鄰接表存儲(chǔ)中，須釋放所有在程序運(yùn)行過(guò)程中申請(qǐng)的的邊表結(jié)點(diǎn)template<typenameDataType>ALGraph<DataType>::~ALGraph(){EdgeNode*p=nullptr,*q=nullptr;for(inti=0;i<vertexNum;i++){p=q=adjList[i].firstEdge;while(p!=nullptr){p=p->next;deleteq;q=p;}}}13∧

0123

v0

v1

v2

v3

0∧02∧∧圖的銷毀深度優(yōu)先遍歷算法：DFTraverse輸入：頂點(diǎn)的編號(hào)v輸出：無(wú)1.訪問(wèn)頂點(diǎn)v;修改標(biāo)志visited[v]=1;2.j=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)；3.while(j存在)3.1if(j未被訪問(wèn))從頂點(diǎn)j出發(fā)遞歸執(zhí)行該算法;3.2j=頂點(diǎn)v的下一個(gè)鄰接點(diǎn);13∧

0123

v0

v1

v2

v3

0∧02∧∧template<typenameDataType>voidALGraph<DataType>::DFTraverse(intv){

intj;

EdgeNode*p=nullptr;

cout<<adjList[v].vertex;visited[v]=1;

p=adjList[v].firstEdge;

while(p!=nullptr)

{

j=p->adjvex;

if(visited[j]==0)DFTraverse(j);

p=