數(shù)據(jù)結(jié)構(gòu)-圖的基本概念和存儲結(jié)構(gòu)

《數(shù)據(jù)結(jié)構(gòu)-圖的基本概念和存儲結(jié)構(gòu)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖和圖的存儲結(jié)構(gòu)圖的定義和術(shù)語圖的存儲表示小結(jié)和作業(yè)創(chuàng)建圖課堂練習(xí)圖和圖的存儲結(jié)構(gòu)1.圖的結(jié)構(gòu)定義2.圖的名詞和術(shù)語3.圖的基本操作圖的結(jié)構(gòu)定義謂詞P(v,w)定義了弧的意義或信息。圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)R＝{

2、v,w∈V且P(v,w)}表示從v到w的一條弧(Arc)，稱v為弧尾(tail)，w為弧頭(head)。圖的結(jié)構(gòu)定義—有向圖如果“弧”是有方向的，則稱由頂點集和弧集構(gòu)成的圖為有向圖。EACBD例如:G1=(V1,R1)V1={A,B,C,D,E}R1={,,<

3、B,C>,,,,}圖的結(jié)構(gòu)定義—無向圖若?R必有?R,則以無序?qū)?v,w)代替這兩個有序?qū)?，稱(v,w)為頂點v和頂點w之間存在一條邊。上述這種由頂點集和邊集構(gòu)成的圖稱作無向圖。圖的結(jié)構(gòu)定義—無向圖例如:G2=(V2,R2)BCAFEDV2={A,B,C,D,E,F}R2={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F)(D,F}名詞和術(shù)語1）網(wǎng)、子圖2）完全圖、稀疏圖、稠密圖3）鄰接點、度、入度、出度4）路徑、路徑長度、簡單路徑、簡單回路5）連通圖、連通分量、強連通圖、強連通分

4、量6）生成樹、生成森林名詞和術(shù)語1）子圖設(shè)圖G=(V,{R})和圖G?=(V?,R?),且V??V,R??R,則稱G?為G的子圖。EACBDEACBDB名詞和術(shù)語1）網(wǎng)弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。ABECD1597211132名詞和術(shù)語2）完全圖、稀疏圖、稠密圖假設(shè)圖中有n個頂點，e條邊，則含有e=n(n-1)/2條邊的無向圖稱作完全圖;含有e=n(n-1)條弧的有向圖稱作有向完全圖;若邊或弧的個數(shù)e

5、頂點v關(guān)聯(lián)的邊的數(shù)目，記為TD（V）。邊(v,w)和頂點v和w相關(guān)聯(lián)。ACDFEB名詞和術(shù)語3）鄰接點、度、入度、出度例如:TD(B)=3TD(A)=2ACDFEB右側(cè)圖中的無向圖名詞和術(shù)語3）鄰接點、度、入度、出度ABECD頂點的出度:以頂點v為弧尾的弧的數(shù)目;記為OD（v）對于右圖所示的有向圖來說，由于弧有方向性，則有入度和出度之分名詞和術(shù)語3）鄰接點、度、入度、出度ABECD頂點的入度:以頂點v為弧頭的弧的數(shù)目，記為ID（v）頂點的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3名詞和術(shù)語ABECD4）路徑、路徑長度、簡單路

6、徑、簡單回路路徑：設(shè)圖G=(V,{R})中的一個頂點序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)?R，1≤j≤m,則稱從頂點u到頂點w之間存在一條路徑。路徑長度：路徑上邊的數(shù)目。如:從A到D長度為3的路徑{A,B,C,D}名詞和術(shù)語4）路徑、路徑長度、簡單路徑、簡單回路簡單路徑:指序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路:指序列中第一個頂點和最后一個頂點相同的路徑。ABECD名詞和術(shù)語5）連通圖、連通分量、強連通圖、強連通分量連通圖：若無向圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖;BACDFE名詞和術(shù)語5）連通圖、連通分

7、量、強連通圖、強連通分量BACDFE連通分量：若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。名詞和術(shù)語5）連通圖、連通分量、強連通圖、強連通分量強連通圖：若有向圖任意兩個頂點之間都存在一條有向路徑，則稱為強連通圖。ABECD否則，其各個強連通子圖稱作它的強連通分量。ABECD名詞和術(shù)語6）生成樹、生成森林連通圖的生成樹：是一個極小連通子圖，它含有圖中的全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。BACDFEBACDFE名詞和術(shù)語6）生成樹、生成森林生成森林：對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。ABEFCDABECF

8、D基本操作1.結(jié)構(gòu)的建立和銷毀3.插入或刪除頂點5.對鄰接點的操作2.對頂點的訪問操作6.遍歷4.插入和刪除弧基本操作CreatGraph(&G,V,R)://按定義(V,R)構(gòu)造圖DestroyGraph(&G)://銷毀圖1.結(jié)構(gòu)的建立和銷毀基本操作2.對頂點的訪問操作LocateVex(G,u);//若G中存在頂點u，則返回該頂點在//圖中“位置”；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。基本操作3.插入或刪除頂點InsertVex(&G,v);//在圖G中增添新頂點v。Del

9、eteVex(&G,v)