數(shù)據(jù)結(jié)構(gòu)隨堂筆記第一章概

論1.數(shù)據(jù)：信息的載體,能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。3.數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它包括：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)；2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，依賴于計(jì)算機(jī)語(yǔ)言。3）數(shù)據(jù)的運(yùn)算，定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的運(yùn)算：檢索/插入/刪除/更新/排序。4.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。5.數(shù)據(jù)類型：一個(gè)值的集合及在值上定義的一組操作的總稱。分為：原子類型和結(jié)構(gòu)類型。6.抽象數(shù)據(jù)類型：抽象數(shù)據(jù)的組織和與之相關(guān)的操作。優(yōu)點(diǎn)：將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。7.抽象數(shù)據(jù)類型ADT：是在概念層上描述問題；類：是在實(shí)現(xiàn)層上描述問題；在應(yīng)用層上操作對(duì)象（類的實(shí)例）解決問題。8.數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)，有：（1）線性結(jié)構(gòu)，若結(jié)構(gòu)是非空集則僅有一個(gè)開始和終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和后繼。（2）非線性結(jié)構(gòu)，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和后繼。9.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有：1）順序存儲(chǔ)，把邏輯相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)。2）鏈接存儲(chǔ)，結(jié)點(diǎn)間的邏輯關(guān)系由附加指針字段表示。3）索引存儲(chǔ)，存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加索引表，有稠密索引和稀疏索引。4）散列存儲(chǔ)，按結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出存儲(chǔ)地址。10.評(píng)價(jià)算法的好壞是：算法是正確的；執(zhí)行算法所耗的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（輔助存儲(chǔ)空間）；易于理解、編碼、調(diào)試。11.算法的時(shí)間復(fù)雜度T(n)：是該算法的時(shí)間耗費(fèi)，是求解問題規(guī)模n的函數(shù)。記為O(n)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、……k次方階O(n^k)、指數(shù)階O(2^n)。13.算法的空間復(fù)雜度S(n)：是該算法的空間耗費(fèi)，是求解問題規(guī)模n的函數(shù)。12.算法衡量：是用時(shí)間復(fù)雜度和空間復(fù)雜度來衡量的，它們合稱算法的復(fù)雜度。13.算法中語(yǔ)句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。

第二章

線性表1.線性表：是由n(n≥0)個(gè)數(shù)據(jù)元素組成的有限序列。2.線性表的基本運(yùn)算有：1）InitList(L),構(gòu)造空表，即表的初始化；2）ListLength(L),求表的結(jié)點(diǎn)個(gè)數(shù)，即表長(zhǎng)；3）GetNode(L,i),取表中第i個(gè)結(jié)點(diǎn)，要求1≤i≤ListLength(L)；4）LocateNode(L,x)查找L中值為x的結(jié)點(diǎn)并返回結(jié)點(diǎn)在L中的位置，有多個(gè)x則返回首個(gè)，沒有則返回特殊值表示查找失敗。5）InsertList(L,x,i)在表的第i個(gè)位置插入值為x的新結(jié)點(diǎn)，要求1≤i≤ListLength(L)+1；6）DeleteList(L,i)刪除表的第i個(gè)位置的結(jié)點(diǎn)，要求1≤i≤ListLength(L)；3.順序表：把線性表的結(jié)點(diǎn)按邏輯次序存放在一組地址連續(xù)的存儲(chǔ)單元里。4.順序表結(jié)點(diǎn)的存儲(chǔ)地址計(jì)算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n5.順序表上的基本運(yùn)算（1）插入voidinsertlist(seqlist*L,datatypex,inti){

intj;

if(i<1||i>L->length+1)

error(“positionerror”);

if(L->length>=listsize)

error(“overflow”);

for(j=L->length-1;j>=i-1;j--)

L->data[j+1]=L->data[j];

結(jié)點(diǎn)后移

L->data[i-1]=x;

L->length++;}在順序表上插入要移動(dòng)表的n/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。（2）刪除voiddelete(seqlist*L,inti){

intj;

if(i<1||i>L->length)

error(“positionerror”);

for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j];

結(jié)點(diǎn)前移

L->length--;}在順序表上刪除要移動(dòng)表的（n+1）/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。6.單鏈表：只有一個(gè)鏈域的鏈表稱單鏈表。在結(jié)點(diǎn)中存儲(chǔ)結(jié)點(diǎn)值和結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址，data

next

data是數(shù)據(jù)域，next是指針域。（1）建立單鏈表。時(shí)間復(fù)雜度為O(n)。加頭結(jié)點(diǎn)的優(yōu)點(diǎn)：1）鏈表第一個(gè)位置的操作無需特殊處理；2）將空表和非空表的處理統(tǒng)一。（2）查找運(yùn)算。時(shí)間復(fù)雜度為O(n)。1）按序號(hào)查找。Listnode*getnode(linklisthead,inti){

intj;

listnode*p;

p=head;j=0;

while(p->next&&j<i){

p=p->next;指針下移

j++;

}

if(i==j)

returnp;

else

returnNULL;}2）按值查找。Listnode*locatenode(linklisthead,datatypekey){

listnode*p=head->next;

while(p&&p->data!=key)

p=p->next;

returnp;}（3）插入運(yùn)算。時(shí)間復(fù)雜度為O(n)。Voidinsertlist(linklisthead,datatypex,inti){

listnode*p;

p=getnode(head,i-1);

if(p==NULL);

error(“positionerror”);

s=(listnode*)malloc(sizeof(listnode));

s->data=x;

s->next=p->next;

p->next=s;}（4）刪除運(yùn)算。時(shí)間復(fù)雜度為O(n)。Voiddeletelist(linklisthead,inti){

listnode*p,*r;

p=getnode(head,i-1);

if(p==NULL||p->next==NULL)

error(“positionerror”);

r=p->next;

p->next=r->next;

free(r);}7.循環(huán)鏈表：是一種首尾相連的鏈表。特點(diǎn)是無需增加存儲(chǔ)量，僅對(duì)表的鏈接方式修改使表的處理靈活方便。8.空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。9.很多時(shí)候表的操作是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯的不夠方便，改用尾指針rear來表示單循環(huán)鏈表。用頭指針表示的單循環(huán)鏈表查找開始結(jié)點(diǎn)的時(shí)間是O(1),查找尾結(jié)點(diǎn)的時(shí)間是O(n)；用尾指針表示的單循環(huán)鏈表查找開始結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)間都是O(1)。10.在結(jié)點(diǎn)中增加一個(gè)指針域，prior|data|next。形成的鏈表中有兩條不同方向的鏈稱為雙鏈表。1)雙鏈表的前插操作。時(shí)間復(fù)雜度為O(1)。Voiddinsertbefore(dlistnode*p,datatypex){

dlistnode*s=malloc(sizeof(dlistnode));

s->data=x;

s->prior=p->prior;

s->next=p;

p->prior->next=s;

p->prior=s;}2)雙鏈表的刪除操作。時(shí)間復(fù)雜度為O(1)。Voidddeletenode(dlistnode*p){

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);}11.順序表和鏈表的比較1）基于空間的考慮：順序表的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。順序表的存儲(chǔ)密度比鏈表大。因此，在線性表長(zhǎng)度變化不大，易于事先確定時(shí)，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。2）基于時(shí)間的考慮：順序表是隨機(jī)存取結(jié)構(gòu)，若線性表的操作主要是查找，很少有插入、刪除操作時(shí)，宜用順序表結(jié)構(gòu)。對(duì)頻繁進(jìn)行插入、刪除操作的線性表宜采用鏈表。若操作主要發(fā)生在表的首尾時(shí)采用尾指針表示的單循環(huán)鏈表。12.存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量）/（整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量）存儲(chǔ)密度：順序表=1，鏈表<1。第三章

棧和隊(duì)列

1.棧是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表又稱為后進(jìn)先出表（LIFO表）。插入、刪除端稱為棧頂，另一端稱棧底。表中無元素稱空棧。2.棧的基本運(yùn)算有：1）initstack(s),構(gòu)造一個(gè)空棧；2）stackempty(s),判?？眨?）stackfull(s),判棧滿；4）push(s,x),進(jìn)棧；5）pop(s),退棧；6）stacktop(s)，取棧頂元素。3.順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)稱順序棧。4.當(dāng)棧滿時(shí)，做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，稱“上溢”。當(dāng)棧空時(shí)，做退棧運(yùn)算必定產(chǎn)生空間溢出，稱“下溢”。上溢是一種錯(cuò)誤應(yīng)設(shè)法避免，下溢常用作程序控制轉(zhuǎn)移的條件。6.鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱鏈棧。棧頂指針是鏈表的頭指針。

8.隊(duì)列是一種運(yùn)算受限的線性表，允許刪除的一端稱隊(duì)首，允許插入的一端稱隊(duì)尾。隊(duì)列又稱為先進(jìn)先出線性表，F(xiàn)IFO表。9.隊(duì)列的基本運(yùn)算：1）initqueue(q),置空隊(duì)；2）queueempty(q),判隊(duì)空；3）queuefull(q),判隊(duì)滿；4）enqueue(q,x),入隊(duì)；5）dequeue(q),出隊(duì)；6）queuefront(q),返回隊(duì)頭元素。10.順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱順序隊(duì)列。設(shè)置front和rear指針表示隊(duì)頭和隊(duì)尾元素在向量空間的位置。11.順序隊(duì)列中存在“假上溢”現(xiàn)象，由于入隊(duì)和出隊(duì)操作使頭尾指針只增不減導(dǎo)致被刪元素的空間無法利用，隊(duì)尾指針超過向量空間的上界而不能入隊(duì)。12.為克服“假上溢”現(xiàn)象，將向量空間想象為首尾相連的循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱循環(huán)隊(duì)列。i=(i+1)%queuesize13.循環(huán)隊(duì)列的邊界條件處理：由于無法用front==rear來判斷隊(duì)列的“空”和“滿”。解決的方法有：1）另設(shè)一個(gè)布爾變量以區(qū)別隊(duì)列的空和滿；2）少用一個(gè)元素，在入隊(duì)前測(cè)試rear在循環(huán)意義下加1是否等于front；3）使用一個(gè)記數(shù)器記錄元素總數(shù)。15.鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱鏈隊(duì)列，鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一確定。第六章

樹1.樹：是n個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱空樹，否則滿足：1）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；2）其余結(jié)點(diǎn)可分為m個(gè)互不相交的子集，每個(gè)子集本身是一棵樹，并稱為根的子樹。2.樹的表示方法：1）樹形表示法；2）嵌套集合表示法；3）凹入表表示法；4）廣義表表示法；3.一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度；一棵樹的度是指樹中結(jié)點(diǎn)最大的度數(shù)。4.度為零的結(jié)點(diǎn)稱葉子或終端結(jié)點(diǎn)；度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)5.根結(jié)點(diǎn)稱開始結(jié)點(diǎn)，根結(jié)點(diǎn)外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；6.樹中某結(jié)點(diǎn)的子樹根稱該結(jié)點(diǎn)的孩子；該結(jié)點(diǎn)稱為孩子的雙親；7.樹中存在一個(gè)結(jié)點(diǎn)序列K1，K2，…Kn，使Ki為Ki+1的雙親，則稱該結(jié)點(diǎn)序列為K1到Kn的路徑或道路；8.樹中結(jié)點(diǎn)K到Ks間存在一條路徑，則稱K是Ks的祖先，Ks是K的子孫；9.結(jié)點(diǎn)的層數(shù)從根算起，若根的層數(shù)為1，則其余結(jié)點(diǎn)層數(shù)是其雙親結(jié)點(diǎn)層數(shù)加1；雙親在同一層的結(jié)點(diǎn)互為堂兄弟；樹中結(jié)點(diǎn)最大層數(shù)稱為樹的高度或深度；10.樹中每個(gè)結(jié)點(diǎn)的各個(gè)子樹從左到右有次序的稱有序樹，否則稱無序樹；11.森林是m棵互不相交的樹的集合。12.二叉樹：是n個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭占?，或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為該根的左子樹和右子樹的二叉樹組成。13.二叉樹不是樹的特殊情況，這是兩種不同的數(shù)據(jù)結(jié)構(gòu)；它與無序樹和度為2的有序樹不同。14.二叉樹的性質(zhì)：1）二叉樹第i層上的結(jié)點(diǎn)數(shù)最多為2^(i-1)；2）深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；3）在任意二叉樹中，葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；15.滿二叉樹是一棵深度為k的且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹；16.完全二叉樹是至多在最下兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層的結(jié)點(diǎn)集中在該層最左的位置的二叉樹；17.具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2N取整加1；18.二叉樹的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)：把一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹，從樹根起自上而下、從左到右對(duì)所有結(jié)點(diǎn)編號(hào)，然后依次存儲(chǔ)在一個(gè)向量b[0~n]中，b[1~n]存放結(jié)點(diǎn)，b[0]存放結(jié)點(diǎn)總數(shù)。各個(gè)結(jié)點(diǎn)編號(hào)間的關(guān)系：1）i=1是根結(jié)點(diǎn)；i>1則雙親結(jié)點(diǎn)是i/2取整；2）左孩子是2i,右孩子是2i+1；（要小于n）3）i>（n/2取整）的結(jié)點(diǎn)是葉子；4）奇數(shù)沒有右兄弟，左兄弟是i-1；5）偶數(shù)沒有左兄弟，右兄弟是i+1；（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)為：lchild|data|rchild；相應(yīng)的類型說明：typedefchardata;typedefstructnode{

datatypedata;

structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;19.在二叉樹中所有類型為bintnode的結(jié)點(diǎn)和一個(gè)指向開始結(jié)點(diǎn)的bintree類型的頭指針構(gòu)成二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱二叉鏈表。20.二叉鏈表由根指針唯一確定。在n個(gè)結(jié)點(diǎn)的二叉鏈表中有2n個(gè)指針域，其中n+1個(gè)為空。21.二叉樹的遍歷方式有：前序遍歷、中序遍歷、后序遍歷。時(shí)間復(fù)雜度為O(n)。22.線索二叉樹：利用二叉鏈表中的n+1個(gè)空指針域存放指向某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指針稱線索。加線索的二叉鏈表稱線索鏈表。相應(yīng)二叉樹稱線索二叉樹。23.線索鏈表結(jié)點(diǎn)結(jié)構(gòu)：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指針；ltag=1,lchild是指向前趨的線索；rtag=0,rchild是指向右孩子的指針；rtag=1,rchild是指向后繼的線索；24.查找*p在指定次序下的前趨和后繼結(jié)點(diǎn)。算法的時(shí)間復(fù)雜度為O(h)。線索對(duì)查找前序前趨和后序后繼幫助不大。25.遍歷線索二叉樹。時(shí)間復(fù)雜度為O(n)。

26.樹、森林與二叉樹的轉(zhuǎn)換（1）樹、森林與二叉樹的轉(zhuǎn)換1）樹與二叉樹的轉(zhuǎn)換：1}所有兄弟間連線；2}保留與長(zhǎng)子的連線，去除其它連線。該二叉樹的根結(jié)點(diǎn)的右子樹必為空。2）森林與二叉樹的轉(zhuǎn)換：1}將所有樹轉(zhuǎn)換成二叉樹；2}將所有樹根連線。（2）二叉樹與樹、森林的轉(zhuǎn)換。是以上的逆過程。27.樹的存儲(chǔ)結(jié)構(gòu)（1）雙親鏈表表示法：為每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)parent指針，就可唯一表示任何一棵樹。Data|parent（2）孩子鏈表表示法：為每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)firstchild指針，指向孩子鏈表頭指針，鏈表中存放孩子結(jié)點(diǎn)序號(hào)。Data|firstchild。（3雙親孩子鏈表表示法：將以上方法結(jié)合。Data|parent|firstchild（4）孩子兄弟鏈表表示法：附加兩個(gè)指向左孩子和右兄弟的指針。Leftmostchild|data|rightsibling28.樹和森林的遍歷：前序遍歷一棵樹等價(jià)于前序遍歷對(duì)應(yīng)二叉樹；后序遍歷等價(jià)于中序遍歷對(duì)應(yīng)二叉樹。29.最優(yōu)二叉樹（哈夫曼樹）：樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。將樹中的結(jié)點(diǎn)賦予實(shí)數(shù)稱為結(jié)點(diǎn)的權(quán)。30.結(jié)點(diǎn)的帶權(quán)路徑是該結(jié)點(diǎn)的路徑長(zhǎng)度與權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度又稱樹的代價(jià)，是所有葉子的帶權(quán)路徑長(zhǎng)度之和。31.帶權(quán)路徑長(zhǎng)度最小的二叉樹稱最優(yōu)二叉樹（哈夫曼樹）。32.具有2n-1個(gè)結(jié)點(diǎn)其中有n個(gè)葉子，并且沒有度為1的分支結(jié)點(diǎn)的樹稱為嚴(yán)格二叉樹。33.哈夫曼編碼34.對(duì)字符集編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼前綴，這種編碼稱前綴碼。35.字符出現(xiàn)頻度與碼長(zhǎng)乘積之和稱文件總長(zhǎng)；字符出現(xiàn)概率與碼長(zhǎng)乘積之和稱平均碼長(zhǎng)；36.使文件總長(zhǎng)或平均碼長(zhǎng)最小的前綴碼稱最優(yōu)前綴碼37.利用哈夫曼樹求最優(yōu)前綴碼，左為0，右為1。編碼平均碼長(zhǎng)最??；沒有葉子是其它葉子的祖先，不可能出現(xiàn)重復(fù)前綴。

第七章

圖1.圖：圖G是由頂點(diǎn)集V和邊集E組成，頂點(diǎn)集是有窮非空集，邊集是有窮集；2.G中每條邊都有方向稱有向圖；有向邊稱弧；邊的始點(diǎn)稱弧尾；邊的終點(diǎn)稱弧頭；G中每條邊都沒有方向的稱無向圖。3.頂點(diǎn)n與邊數(shù)e的關(guān)系：無向圖的邊數(shù)e介于0~n(n-1)/2之間，有n(n-1)/2條邊的稱無向完全圖；有向圖的邊數(shù)e介于0~n(n-1)之間，有n(n-1)條邊的稱有向完全圖；4.無向圖中頂點(diǎn)的度是關(guān)聯(lián)與頂點(diǎn)的邊數(shù)；有向圖中頂點(diǎn)的度是入度與出度的和。所有圖均滿足：所有頂點(diǎn)的度數(shù)和的一半為邊數(shù)。5.圖G（V，E），如V’是V的子集，E’是E的子集，且E’中關(guān)聯(lián)的頂點(diǎn)均在V’中，則G’(V’,E’)是G的子圖。6.在有向圖中，從頂點(diǎn)出發(fā)都有路徑到達(dá)其它頂點(diǎn)的圖稱有根圖；7.在無向圖中，任意兩個(gè)頂點(diǎn)都有路徑連通稱連通圖；極大連通子圖稱連通分量；8.在有向圖中，任意順序兩個(gè)頂點(diǎn)都有路徑連通稱強(qiáng)連通圖；極大連通子圖稱強(qiáng)連通分量；9.將圖中每條邊賦上權(quán)，則稱帶權(quán)圖為網(wǎng)絡(luò)。10.圖的存儲(chǔ)結(jié)構(gòu)：（1）鄰接矩陣表示法：鄰接矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣。n個(gè)頂點(diǎn)就是n階方陣。無向圖是對(duì)稱矩陣；有向圖行是出度，列是入度。（2）鄰接表表示法：對(duì)圖中所有頂點(diǎn)，把與該頂點(diǎn)相鄰接的頂點(diǎn)組成一個(gè)單鏈表，稱為鄰接表，adjvex|next,如要保存頂點(diǎn)信息加入data；對(duì)所有頂點(diǎn)設(shè)立頭結(jié)點(diǎn)，vertex|firstedge,并順序存儲(chǔ)在一個(gè)向量中；vertex保存頂點(diǎn)信息，firstedge保存鄰接表頭指針。11.鄰接矩陣表示法與鄰接表表示法的比較：1）鄰接矩陣是唯一的，鄰接表不唯一；2）存儲(chǔ)稀疏圖用鄰接表，存儲(chǔ)稠密圖用鄰接矩陣；3）求無向圖頂點(diǎn)的度都容易，求有向圖頂點(diǎn)的度鄰接矩陣較方便；4）判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞時(shí)間為O(n)；5）求邊數(shù)e，鄰接矩陣耗時(shí)為O(n^2)，與e無關(guān)，鄰接表的耗時(shí)為O(e+n)；12.圖的遍歷：（1）圖的深度優(yōu)先遍歷：類似與樹的前序遍歷。按訪問頂點(diǎn)次序得到的序列稱DFS序列。對(duì)鄰接表表示的圖深度遍歷稱DFS，時(shí)間復(fù)雜度為O(n+e);對(duì)鄰接矩陣表示的圖深度遍歷稱DFSM，時(shí)間復(fù)雜度為O(n^2);（2）圖的廣度優(yōu)先遍歷：類似與樹的層次遍歷。按訪問頂點(diǎn)次序得到的序列稱BFS序列。對(duì)鄰接表表示的圖廣度遍歷稱BFS，時(shí)間復(fù)雜度為O(n+e);對(duì)鄰接矩陣表示的圖廣度遍歷稱BFSM，時(shí)間復(fù)雜度為O(n^2);13.將沒有回路的連通圖定義為樹稱自由樹。14.生成樹：連通圖G的一個(gè)子圖若是一棵包含G中所有頂點(diǎn)的樹，該子圖稱生成樹。有DFS生成樹和BFS生成樹，BFS生成樹的高度最小。非連通圖生成的是森林。15.最小生成樹：將權(quán)最小的生成樹稱最小生成樹。（是無向圖的算法）（1）普里姆算法：1）確定頂點(diǎn)S、初始化候選邊集T[0~n-2]；formvex|tovex|lenght2）選權(quán)值最小的T[i]與第