第13章非線性結(jié)構(gòu)ppt課件

1、本章課件制造：靳展第三部分第三部分 數(shù)據(jù)構(gòu)造根底數(shù)據(jù)構(gòu)造根底本章內(nèi)容樹形構(gòu)造本章內(nèi)容樹形構(gòu)造 樹的根本概念樹的根本概念 二叉樹的根本概念和性質(zhì)二叉樹的根本概念和性質(zhì) 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造 二叉樹的遍歷二叉樹的遍歷 C+ C+中的二叉樹類中的二叉樹類 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 哈夫曼樹哈夫曼樹 本章內(nèi)容圖形構(gòu)造本章內(nèi)容圖形構(gòu)造 圖的概念圖的概念 圖的存儲構(gòu)造圖的存儲構(gòu)造 圖的遍歷圖的遍歷 圖的生成樹和最小生成樹圖的生成樹和最小生成樹 最短途徑最短途徑 拓?fù)渑判蛲負(fù)渑判?關(guān)鍵途徑關(guān)鍵途徑 樹的根本概念樹的根本概念 1. 樹的特點樹的特點2. 樹的定義樹的定義 樹是樹

2、是n(n0)個數(shù)據(jù)元素的有限集合。它滿足以下兩個數(shù)據(jù)元素的有限集合。它滿足以下兩個條件：個條件：有且僅有一個特定的稱為根的元素；有且僅有一個特定的稱為根的元素；其他元素分為其他元素分為個互不相交的有限集個互不相交的有限集合合1、2、，其中每個集合又都是一棵樹并、，其中每個集合又都是一棵樹并稱其為根的子樹。稱其為根的子樹。 樹形構(gòu)造是一類非常重要的樹形構(gòu)造是一類非常重要的非線性構(gòu)造，適宜于描畫數(shù)據(jù)元非線性構(gòu)造，適宜于描畫數(shù)據(jù)元素之間的層次關(guān)系素之間的層次關(guān)系 樹的常用術(shù)語樹的常用術(shù)語 雙親、子女、邊雙親、子女、邊:假設(shè)結(jié)點是結(jié)點的一棵子樹的根，那么假設(shè)結(jié)點是結(jié)點的一棵子樹的根，那么稱做的稱做的“

3、雙親雙親 稱做的稱做的“子女；有序?qū)?，子女；有序?qū)?，稱做從到的稱做從到的“邊邊 。 兄弟：具有同一雙親的結(jié)點兄弟：具有同一雙親的結(jié)點 。 途徑、途徑長度：假設(shè)樹中存在著一個結(jié)點的序列途徑、途徑長度：假設(shè)樹中存在著一個結(jié)點的序列12j，使，使ki是是ki+1 的雙親，那么稱該結(jié)的雙親，那么稱該結(jié)點序列為從點序列為從k1到到kj的一條途徑；途徑長度的一條途徑；途徑長度 等于等于-，它是該途徑所經(jīng)過的邊的數(shù)目，它是該途徑所經(jīng)過的邊的數(shù)目 。 結(jié)點的層數(shù)：根結(jié)點層數(shù)為，其他結(jié)點層數(shù)等于其雙親結(jié)結(jié)點的層數(shù)：根結(jié)點層數(shù)為，其他結(jié)點層數(shù)等于其雙親結(jié)點層數(shù)加點層數(shù)加 。 樹的深度高度：即樹中層數(shù)最大的結(jié)點的層

4、數(shù)樹的深度高度：即樹中層數(shù)最大的結(jié)點的層數(shù) 。 結(jié)點的度數(shù)、樹的度數(shù)：一個結(jié)點子女的個數(shù)稱為該結(jié)點的結(jié)點的度數(shù)、樹的度數(shù)：一個結(jié)點子女的個數(shù)稱為該結(jié)點的“度數(shù)。度數(shù)。 樹中度數(shù)最大的結(jié)點的度數(shù)叫做樹中度數(shù)最大的結(jié)點的度數(shù)叫做“樹的度數(shù)樹的度數(shù) 。 樹葉、分支結(jié)點：度數(shù)為的結(jié)點叫做樹葉、分支結(jié)點：度數(shù)為的結(jié)點叫做“樹葉樹葉 ；度數(shù)大于；度數(shù)大于的結(jié)點叫做的結(jié)點叫做“分分 支結(jié)點或支結(jié)點或“內(nèi)結(jié)點內(nèi)結(jié)點 。 有序樹、無序樹：假設(shè)將樹中每個結(jié)點的各個子樹看成從左有序樹、無序樹：假設(shè)將樹中每個結(jié)點的各個子樹看成從左到右有序的，到右有序的， 那么稱該樹為有序樹；否那么為無序樹那么稱該樹為有序樹；否那么為

5、無序樹 。 森林：森林：棵互不相交的樹的集合稱為森林棵互不相交的樹的集合稱為森林 。樹的常用術(shù)語舉例樹的常用術(shù)語舉例 是的雙親，是的子女，是從到的是的雙親，是的子女，是從到的邊。邊。 、互為兄弟，而和不是兄弟、互為兄弟，而和不是兄弟 。 ADIN是從結(jié)點到結(jié)點的一條途徑，其長度為是從結(jié)點到結(jié)點的一條途徑，其長度為 。 層數(shù)為的結(jié)點有，層數(shù)為的結(jié)點有、層數(shù)為的結(jié)點有，層數(shù)為的結(jié)點有、 。 樹的深度為樹的深度為 。 、的度數(shù)分別為、；樹的度數(shù)、的度數(shù)分別為、；樹的度數(shù)為為 。 、都是樹葉，其他結(jié)點都是分、都是樹葉，其他結(jié)點都是分支結(jié)點支結(jié)點 。森 林二叉樹的根本概念二叉樹的根本概念二叉樹是二叉樹是

6、個結(jié)點的有限集合。它或者是空集個結(jié)點的有限集合。它或者是空集，或者由一個根結(jié)點及兩棵互不相交的、分別稱為，或者由一個根結(jié)點及兩棵互不相交的、分別稱為這個根的左子樹和右子樹的二叉樹組成。這個根的左子樹和右子樹的二叉樹組成。1.二叉樹的定義二叉樹的定義 2. 二叉樹五種根本形狀二叉樹五種根本形狀 二叉樹的子樹有左、右之分，樹的子樹是一樣的。二叉樹的子樹有左、右之分，樹的子樹是一樣的。 二叉樹可以是空，而樹不能為空。二叉樹可以是空，而樹不能為空。 3.樹和二叉樹的差別樹和二叉樹的差別二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)性質(zhì) 二叉樹第層上的結(jié)點數(shù)目最多為二叉樹第層上的結(jié)點數(shù)目最多為2i。性質(zhì)性質(zhì) 深度為的二叉

7、樹至多有深度為的二叉樹至多有2k+1-1個結(jié)點個結(jié)點。性質(zhì)性質(zhì) 在恣意一棵二叉樹中，假設(shè)終端結(jié)點的個數(shù)為在恣意一棵二叉樹中，假設(shè)終端結(jié)點的個數(shù)為n0、度數(shù)為的結(jié)點、度數(shù)為的結(jié)點的個數(shù)為的個數(shù)為n2，那么，那么n0=n2+1。1. 二叉樹的性質(zhì)二叉樹的性質(zhì)2. 兩種特殊的二叉樹兩種特殊的二叉樹滿二叉樹滿二叉樹 完全二叉樹完全二叉樹完全二叉樹性質(zhì)完全二叉樹性質(zhì) 性質(zhì)性質(zhì)4 具有個結(jié)點的完全二叉樹的深度為具有個結(jié)點的完全二叉樹的深度為 log2n 性質(zhì)性質(zhì)5 假設(shè)對一棵有個結(jié)點的完全二叉樹，按自頂向下、同假設(shè)對一棵有個結(jié)點的完全二叉樹，按自頂向下、同層由左到右順序依次為其每個結(jié)點從層由左到右順序依次

8、為其每個結(jié)點從0開場編號，那么對編號為開場編號，那么對編號為的結(jié)點的結(jié)點kin-1那么有：那么有：假設(shè)假設(shè)0，那么，那么ki雙親結(jié)點的編號為雙親結(jié)點的編號為 (i-1)/2 假設(shè)假設(shè)=，那么，那么ki是根結(jié)點。是根結(jié)點。假設(shè)假設(shè)2i+1n，那么，那么ki左子女結(jié)點的編號是左子女結(jié)點的編號是2i+1，否那，否那么么ki無左子女。無左子女。假設(shè)假設(shè)2i+2n，那么，那么ki右子女結(jié)點的編號為右子女結(jié)點的編號為2i+2，否那，否那么么ki無右子女。無右子女。二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造 對完全二叉樹，利用性質(zhì)對完全二叉樹，利用性質(zhì)5，將其一切結(jié)點按編號順序依次存儲在一維數(shù)組里。，將其一切結(jié)點按編

9、號順序依次存儲在一維數(shù)組里。 對普通二叉樹，需求加上一些并不存在的對普通二叉樹，需求加上一些并不存在的“虛結(jié)點，轉(zhuǎn)換為完全二叉樹的方式。虛結(jié)點，轉(zhuǎn)換為完全二叉樹的方式。1. 順序存儲構(gòu)造順序存儲構(gòu)造 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造 2. 鏈?zhǔn)酱鎯?gòu)造鏈?zhǔn)酱鎯?gòu)造 鏈接存儲時結(jié)點的構(gòu)造鏈接存儲時結(jié)點的構(gòu)造template template class BinTree;/二叉樹類BinTree的前視聲明template class Nodefriend class BinTree;/定義二叉樹類BinTree為友元 public:Node():lchild(NULL),rchild(NULL)

10、/無參構(gòu)造函數(shù) Node(T val, Node *lptr=NULL,Node *rptr=NULL)/帶參構(gòu)造函數(shù)data=val;lchild=lptr;rchild=rptr;二叉樹的遍歷二叉樹的遍歷先序遍歷先序遍歷 訪問根結(jié)點，先序遍歷左子樹，先序遍歷右子樹。訪問根結(jié)點，先序遍歷左子樹，先序遍歷右子樹。中序遍歷中序遍歷 中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹。中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹。后序遍歷后序遍歷 后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點。后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點。層次遍歷層次遍歷 按層數(shù)由小到大、同一層從左到右順序依次訪問二按層數(shù)由小到

11、大、同一層從左到右順序依次訪問二叉樹的各個結(jié)點叉樹的各個結(jié)點 先序訪問序列先序訪問序列 ：ABDGECF中序訪問序列中序訪問序列 ：DGBEAFC后序訪問序列后序訪問序列 ：GDBEAFC層次訪問序列層次訪問序列 ：ABCDEFG 二叉排序樹類二叉排序樹類二叉排序樹：一種特殊的二叉樹，其特點是：左子二叉排序樹：一種特殊的二叉樹，其特點是：左子樹上一切結(jié)點的值均小于其雙親結(jié)點的值，右子樹樹上一切結(jié)點的值均小于其雙親結(jié)點的值，右子樹上一切結(jié)點的值均大于或等于其雙親結(jié)點的值。上一切結(jié)點的值均大于或等于其雙親結(jié)點的值。 template class BinTree public: BinTree():

12、root(NULL)/構(gòu)造一棵空樹 BinTree()Destroy(root);/析構(gòu)函數(shù) void insertNode(T val)/向二叉樹插入值為val的結(jié)點 insertNode(root,val); void PreOrder()PreOrder(root);/前序遍歷二叉樹 void InOrder()InOrder(root);/中序遍歷二叉樹 void PostOrder()PostOrder(root);/后序遍歷二叉樹 void LevelOrder()LeverOrder(root);/層次遍歷二叉樹 private: Node *root;/根結(jié)點指針 void i

13、nsertNode(Node *&t,T val);/向t指向的二叉樹中插入結(jié)點 void PreOrder(Node *t);/前序遍歷t指向的二叉樹 void InOrder(Node *t);/中序遍歷t指向的二叉樹 void PostOrder(Node *t);/后序遍歷t指向的二叉樹 void LeverOrder(Node *t);/層次遍歷t指向的二叉樹 void Destroy(Node *t);/刪除二叉樹;二叉排序樹類的成員函數(shù)二叉排序樹類的成員函數(shù)template void BinTree:insertNode(Node *&t,T val)if(t=N

14、ULL)t=new Node(val);else if(valdata) insertNode(t-lchild,val);else insertNode(t-rchild,val);template void BinTree:PreOrder(Node *t) if(t!=NULL) coutdatalchild);/先序遍歷左子樹 PreOrder(t-rchild);/先序遍歷右子樹 template void BinTree:InOrder(Node *t) if(t!=NULL) InOrder(t-lchild); /中序遍歷左子樹 coutdatarchild); /中序遍歷右子

15、樹 template void BinTree:PostOrder(Node *t) if(t!=NULL) PostOrder(t-lchild); /后序遍歷左子樹 PostOrder(t-rchild); /后序遍歷右子樹樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 將樹轉(zhuǎn)換成二叉樹：將樹轉(zhuǎn)換成二叉樹： 在一切的兄弟之間加一條連線；在一切的兄弟之間加一條連線；對每個結(jié)點，除了保管與最左邊子女的連線外，去掉對每個結(jié)點，除了保管與最左邊子女的連線外，去掉與其他子女連線；與其他子女連線；將保管下來的邊作為左子樹的邊，兄弟間的連線作為將保管下來的邊作為左子樹的邊，兄弟間的連線作為右子樹的邊。右子

16、樹的邊。 將一個森林轉(zhuǎn)換成二叉樹：將一個森林轉(zhuǎn)換成二叉樹：先將森林中的每一棵樹變?yōu)槎鏄?，然后將各二叉樹的先將森林中的每一棵樹變?yōu)槎鏄洌缓髮⒏鞫鏄涞母Y(jié)點看成兄弟，根結(jié)點看成兄弟，用線把它們連到一同，經(jīng)整理后可得到相用線把它們連到一同，經(jīng)整理后可得到相應(yīng)的二叉樹。應(yīng)的二叉樹。 樹、森林到二叉樹的轉(zhuǎn)換樹、森林到二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 續(xù)續(xù)假設(shè)結(jié)點是其雙親的左子女，那么把的右子女、假設(shè)結(jié)點是其雙親的左子女，那么把的右子女、右子女的右子女右子女的右子女都與連線，最后去掉一切雙親到右子女都與連線，最后去掉一切雙親到右子女的連線。的連線。 2二叉樹到樹、森林的轉(zhuǎn)換

17、二叉樹到樹、森林的轉(zhuǎn)換 哈夫曼樹根本概念哈夫曼樹根本概念 擴展二叉樹和帶權(quán)途徑長度：擴展二叉樹和帶權(quán)途徑長度：假設(shè)假設(shè)W0，W1，Wn-1是個實數(shù)的集合，其中是個實數(shù)的集合，其中Wi-。假設(shè)是一棵有個葉結(jié)點的二叉樹。假設(shè)是一棵有個葉結(jié)點的二叉樹，而且將，而且將W0，W1，Wn-1分別賦給的個葉結(jié)點作為它分別賦給的個葉結(jié)點作為它們的權(quán)，那么稱是權(quán)值為們的權(quán)，那么稱是權(quán)值為W0，W1，Wn-1的擴展二叉樹的擴展二叉樹。帶有權(quán)值的葉結(jié)點叫做擴展二叉樹的外結(jié)點，其他的分支結(jié)。帶有權(quán)值的葉結(jié)點叫做擴展二叉樹的外結(jié)點，其他的分支結(jié)點叫做內(nèi)結(jié)點。點叫做內(nèi)結(jié)點。一個有個外結(jié)點的擴展二叉樹的帶權(quán)途徑長度一個有個

18、外結(jié)點的擴展二叉樹的帶權(quán)途徑長度為：為： WPL=其中，其中，Wi為外結(jié)點所帶的權(quán)值；為外結(jié)點所帶的權(quán)值；li為從根結(jié)點到外結(jié)為從根結(jié)點到外結(jié)點的途徑長度。點的途徑長度。 inil10iW(a) WPL=40 (b) WPL=50(c) WPL=38 哈夫曼樹根本概念哈夫曼樹根本概念 續(xù)續(xù)2最優(yōu)二叉樹最優(yōu)二叉樹通常，把權(quán)值取為通常，把權(quán)值取為W0，W1，Wn-1的一切擴展的一切擴展二叉樹中為最小的擴展二叉樹稱為最優(yōu)二叉樹。二叉樹中為最小的擴展二叉樹稱為最優(yōu)二叉樹。3哈夫曼樹哈夫曼樹利用哈夫曼提出的方法構(gòu)造出的最優(yōu)二叉樹稱為哈夫曼利用哈夫曼提出的方法構(gòu)造出的最優(yōu)二叉樹稱為哈夫曼樹。樹。 4哈夫曼

19、樹構(gòu)造方法哈夫曼樹構(gòu)造方法由給定的個權(quán)值由給定的個權(quán)值W0，W1，Wn-1構(gòu)造含構(gòu)造含有棵擴展二叉樹的森林，森林中的每棵二叉樹都只需一個有棵擴展二叉樹的森林，森林中的每棵二叉樹都只需一個根結(jié)點，且每個根結(jié)點都取一個各不一樣的根結(jié)點，且每個根結(jié)點都取一個各不一樣的Wi作為權(quán)值；作為權(quán)值；用森林中根結(jié)點的權(quán)值為最小和次小的兩棵二叉樹用森林中根結(jié)點的權(quán)值為最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造出一棵新的二叉樹，并將新二叉樹的根結(jié)作為左、右子樹構(gòu)造出一棵新的二叉樹，并將新二叉樹的根結(jié)點的權(quán)值取為左、右子樹根結(jié)點權(quán)值之和；點的權(quán)值取為左、右子樹根結(jié)點權(quán)值之和；從森林中刪去作為新二叉樹左、右子樹的兩棵二

20、叉從森林中刪去作為新二叉樹左、右子樹的兩棵二叉樹，將新構(gòu)造的二叉樹參與到森林中；樹，將新構(gòu)造的二叉樹參與到森林中；反復(fù)步驟和，直到中僅剩下一棵二叉樹為止。反復(fù)步驟和，直到中僅剩下一棵二叉樹為止。哈夫曼樹的構(gòu)造哈夫曼樹的構(gòu)造 哈夫曼樹的運用哈夫曼樹的運用例例 設(shè)電文字符集為設(shè)電文字符集為a，b，c，d，e，f，各字符發(fā)送頻率是，各字符發(fā)送頻率是6，2，3，3，4，9，利用哈夫曼樹構(gòu)造個字符的編碼。，利用哈夫曼樹構(gòu)造個字符的編碼。以字符發(fā)送頻率為權(quán)值構(gòu)造哈夫曼樹以字符發(fā)送頻率為權(quán)值構(gòu)造哈夫曼樹哈夫曼編碼哈夫曼編碼各字符的哈夫曼編碼是各字符的哈夫曼編碼是 a：01 b：001 c：001 d：100

21、 e：101 f：100圖的概念圖的概念圖的定義圖的定義 圖用二重組，表示。其中，是頂點的有窮非空集合；是圖用二重組，表示。其中，是頂點的有窮非空集合；是中頂點偶對稱為邊的有窮集合。中頂點偶對稱為邊的有窮集合。對一個給定的圖，用表示頂點集，用表示邊集。對一個給定的圖，用表示頂點集，用表示邊集。 有向圖有向圖 假設(shè)一個圖中的每條邊都有方假設(shè)一個圖中的每條邊都有方向，稱它為有向圖。在有向圖中，一條向，稱它為有向圖。在有向圖中，一條有向邊是由兩個頂點組成的有序?qū)ΑＳ杏邢蜻吺怯蓛蓚€頂點組成的有序?qū)?。有序?qū)ΤＳ眉饫ㄌ柋硎?，序?qū)ΤＳ眉饫ㄌ柋硎?，例如，例如，表示一條有向邊表示一條有向邊，Vi是邊的始點，是邊

22、的始點，Vj是邊的終點。是邊的終點。 和和表示的是兩條不同的表示的是兩條不同的邊。邊。 無向圖無向圖假設(shè)一個圖中每條邊都是沒有假設(shè)一個圖中每條邊都是沒有方向的，那么稱此圖為無向圖。無向圖方向的，那么稱此圖為無向圖。無向圖中組成邊的兩個頂點是無序的，通常用中組成邊的兩個頂點是無序的，通常用圓括號表示。圓括號表示。例如，例如，(Vi,Vj)表示一條無向邊表示一條無向邊。 (Vi,Vj)和和(Vj ,Vi)表示的是同一條邊。表示的是同一條邊。 圖的常用術(shù)語圖的常用術(shù)語 鄰接頂點鄰接頂點 在無向圖中，假設(shè)，是圖中的一條邊，那么稱頂點和互為在無向圖中，假設(shè)，是圖中的一條邊，那么稱頂點和互為鄰接頂點。在有

23、向圖中，假設(shè)，是圖中的一條邊，那么稱頂點鄰接到頂鄰接頂點。在有向圖中，假設(shè)，是圖中的一條邊，那么稱頂點鄰接到頂點，頂點鄰接自頂點。點，頂點鄰接自頂點。頂點的度頂點的度 與頂點相關(guān)聯(lián)的邊的數(shù)目叫做度。有向圖頂點的度還有入度與出度之分：與頂點相關(guān)聯(lián)的邊的數(shù)目叫做度。有向圖頂點的度還有入度與出度之分：頂點的入度即以該頂點為終點的邊的數(shù)目；頂點的出度即以該頂點為始點的邊的數(shù)頂點的入度即以該頂點為終點的邊的數(shù)目；頂點的出度即以該頂點為始點的邊的數(shù)目。目。子圖子圖 設(shè)有兩個圖，、設(shè)有兩個圖，、，。假設(shè)。假設(shè)VV、EE，并且，并且中的邊所關(guān)聯(lián)的頂點都在中的邊所關(guān)聯(lián)的頂點都在中，那么稱圖中，那么稱圖是圖的子圖

24、。是圖的子圖。 圖的常用術(shù)語續(xù)圖的常用術(shù)語續(xù) 權(quán)權(quán) 有些圖的邊附帶有數(shù)據(jù)信息，稱這些數(shù)據(jù)信息為權(quán)。常把帶權(quán)的圖稱為網(wǎng)絡(luò)。有些圖的邊附帶有數(shù)據(jù)信息，稱這些數(shù)據(jù)信息為權(quán)。常把帶權(quán)的圖稱為網(wǎng)絡(luò)。 途徑途徑 在圖在圖G=(V,E)中，假設(shè)存在頂點序列中，假設(shè)存在頂點序列VP,Vi1,Vi2,Vin, Vq使得使得(VP,Vi1),( Vi1,Vi2),(Vin, Vq)都在中，那么稱從頂點都在中，那么稱從頂點VP到到Vq存在一存在一條途徑。條途徑。途徑長度途徑長度 對于不帶權(quán)的圖，途徑長度是指途徑上邊的數(shù)目；對帶權(quán)的圖，途徑對于不帶權(quán)的圖，途徑長度是指途徑上邊的數(shù)目；對帶權(quán)的圖，途徑長度是指途徑上各條

25、邊的權(quán)值之和。長度是指途徑上各條邊的權(quán)值之和。簡單途徑簡單途徑 假設(shè)一條途徑上除第一個頂點和最后一個頂點可以一樣外，其他頂點假設(shè)一條途徑上除第一個頂點和最后一個頂點可以一樣外，其他頂點都不一樣，那么稱此途徑為簡單途徑。都不一樣，那么稱此途徑為簡單途徑。 連通圖連通圖 對無向圖，而言，假設(shè)從頂點對無向圖，而言，假設(shè)從頂點Vi到頂點到頂點Vj有一條途徑，那么有一條途徑，那么稱稱Vi和和Vj是連通的。假設(shè)中恣意兩個不同的頂點是連通的。假設(shè)中恣意兩個不同的頂點Vi和和Vj都連通，那么稱都連通，那么稱此圖為連通圖。此圖為連通圖。 圖的存儲構(gòu)造圖的存儲構(gòu)造稱稱A為鄰接矩陣。為鄰接矩陣。 1鄰接矩陣法鄰接矩

26、陣法設(shè)圖，有設(shè)圖，有個頂點個頂點 V0，V1，Vn-1，可以用，可以用一個一個nn階的矩陣階的矩陣A描畫圖中邊的情況。對于描畫圖中邊的情況。對于A中的每個元素中的每個元素aij滿足滿足否則或（若0),1EVVVVajijiij0in-1, 0jn-1 圖的存儲構(gòu)造圖的存儲構(gòu)造性質(zhì)：對無向圖而言，頂點性質(zhì)：對無向圖而言，頂點Vi的度數(shù)的度數(shù)di是矩陣第是矩陣第i行元素值之和行元素值之和，即，即 ； 對有向圖而言，頂點對有向圖而言，頂點Vi的出度為第行元的出度為第行元素值之和，頂點素值之和，頂點Vi的入度為第列的入度為第列元素值之和。頂點元素值之和。頂點Vi的度為的度為1鄰接矩陣法續(xù)鄰接矩陣法續(xù)對

27、于帶權(quán)的圖，鄰接矩陣對于帶權(quán)的圖，鄰接矩陣A中的元素可以定義為中的元素可以定義為 ：0in-1, 0jn-1 jijiEVVVVjiWajijiijij否則，但否則，但或（，且若0),10njijiad1010njjinjijiaad圖的存儲構(gòu)造圖的存儲構(gòu)造2鄰接表法鄰接表法 用鄰接表表示有個頂點的無向圖時，需求一個以順序方式或鏈接方式存用鄰接表表示有個頂點的無向圖時，需求一個以順序方式或鏈接方式存儲的頂點表和個單鏈表。儲的頂點表和個單鏈表。頂點表的每個表目包括兩個域：一個域用來存放頂點頂點表的每個表目包括兩個域：一個域用來存放頂點Vi的信息，另一個域的信息，另一個域用來存放一個指針，它指向與

28、該頂點對應(yīng)的單鏈表。用來存放一個指針，它指向與該頂點對應(yīng)的單鏈表。與頂點與頂點Vi對應(yīng)的單鏈表中的每個結(jié)點代表了一個與對應(yīng)的單鏈表中的每個結(jié)點代表了一個與Vi相鄰接的頂點，它包相鄰接的頂點，它包括三個域：括三個域：dest、weight和和link。dest域中保管了一個與域中保管了一個與Vi相鄰接的頂點的下標(biāo)；相鄰接的頂點的下標(biāo)；weight域存放相應(yīng)邊的權(quán)值對不帶權(quán)的圖，域存放相應(yīng)邊的權(quán)值對不帶權(quán)的圖，weight域可以省略；域可以省略；link域保管指域保管指向鏈表中下一個結(jié)點的指針。向鏈表中下一個結(jié)點的指針。 圖的存儲構(gòu)造圖的存儲構(gòu)造2鄰接表法鄰接表法 續(xù)續(xù)有向圖的鄰接表在構(gòu)造與頂點有

29、向圖的鄰接表在構(gòu)造與頂點Vi相關(guān)的鏈表時只鏈入以相關(guān)的鏈表時只鏈入以Vi為起點的一切有為起點的一切有向邊，稱這種鄰接表為出邊表。向邊，稱這種鄰接表為出邊表。在頂點在頂點Vi的邊鏈表中鏈接一切以的邊鏈表中鏈接一切以Vi為終點的邊，稱這種鏈表為入邊表。為終點的邊，稱這種鏈表為入邊表。 性質(zhì)：從有向圖的出邊表中統(tǒng)計性質(zhì)：從有向圖的出邊表中統(tǒng)計Vi的邊鏈表中結(jié)點個數(shù)即可得的邊鏈表中結(jié)點個數(shù)即可得頂點頂點Vi的出度。的出度。從有向圖的入邊表中統(tǒng)計從有向圖的入邊表中統(tǒng)計Vi的邊鏈表中結(jié)點個數(shù)即可得的邊鏈表中結(jié)點個數(shù)即可得頂點頂點Vi的入度。的入度。比較：在鄰接矩陣表示法中占用的存儲單元個數(shù)與圖中邊的數(shù)比較

30、：在鄰接矩陣表示法中占用的存儲單元個數(shù)與圖中邊的數(shù)目無關(guān)，只與圖中目無關(guān)，只與圖中頂點的個數(shù)有關(guān)。在鄰接表表示法中，需頂點的個數(shù)有關(guān)。在鄰接表表示法中，需求運用的存儲單元不僅與圖中頂求運用的存儲單元不僅與圖中頂點的個數(shù)有關(guān)，而且與邊數(shù)點的個數(shù)有關(guān)，而且與邊數(shù)也有關(guān)。也有關(guān)。 圖的遍歷圖的遍歷 深度優(yōu)先遍歷序列：、深度優(yōu)先遍歷序列：、廣度優(yōu)先遍歷序列：、廣度優(yōu)先遍歷序列：、 深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷從圖中的一個頂點從圖中的一個頂點V為起點并訪問之，然后訪問與相為起點并訪問之，然后訪問與相鄰接但至今未被訪問過的頂點，再訪問與鄰接但未被訪問鄰接但至今未被訪問過的頂點，再訪問與鄰接但未被訪問過

31、的恣意一個頂點，依此類推。過的恣意一個頂點，依此類推。當(dāng)?shù)竭_(dá)一個一切鄰接頂點都被訪問過的頂點時，從曾經(jīng)當(dāng)?shù)竭_(dá)一個一切鄰接頂點都被訪問過的頂點時，從曾經(jīng)被訪問過的頂點序列中最后一個還有未被訪問過的鄰接頂點的被訪問過的頂點序列中最后一個還有未被訪問過的鄰接頂點的頂點開場，反復(fù)上述遍歷過程。頂點開場，反復(fù)上述遍歷過程。 廣度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷恣意指定圖中的一個頂點，訪問此頂點，然后訪問與恣意指定圖中的一個頂點，訪問此頂點，然后訪問與頂點鄰接的全部頂點頂點鄰接的全部頂點W1、2、b，再依次訪問與，再依次訪問與W1、2、b相鄰的但未被訪問過的頂點，如此下去相鄰的但未被訪問過的頂點，如此下去。圖

32、的生成樹和最小生成樹圖的生成樹和最小生成樹 圖的生成樹圖的生成樹對連通的無向圖、強連通的有向圖或有根的有向圖，從對連通的無向圖、強連通的有向圖或有根的有向圖，從其中任何一個頂點或根出發(fā)都可以不延續(xù)地訪問到圖中的全部其中任何一個頂點或根出發(fā)都可以不延續(xù)地訪問到圖中的全部頂點。由圖的一切頂點加上遍歷過程中所經(jīng)過的邊構(gòu)成的子圖頂點。由圖的一切頂點加上遍歷過程中所經(jīng)過的邊構(gòu)成的子圖稱為圖的生成樹。稱為圖的生成樹。有有n個頂點的生成樹必有個頂點的生成樹必有n-1條邊。條邊。 圖的生成樹不是獨一圖的生成樹不是獨一的。的。 最小生成樹最小生成樹圖的各個生成樹中各邊權(quán)值之和為最小的生成樹稱為圖圖的各個生成樹中

33、各邊權(quán)值之和為最小的生成樹稱為圖的最小生成樹。的最小生成樹。 圖的最小生成樹圖的最小生成樹 普里姆算法普里姆算法:從恣意一個頂點開場，首先把這個頂點包括在生成樹里從恣意一個頂點開場，首先把這個頂點包括在生成樹里，然后在一個頂點已在生成樹里而另一個頂點還未在生成樹里，然后在一個頂點已在生成樹里而另一個頂點還未在生成樹里的邊中找出權(quán)值最小的一條邊，并把這條邊和其不在生成樹里的邊中找出權(quán)值最小的一條邊，并把這條邊和其不在生成樹里的那個頂點包括進(jìn)生成樹，如此進(jìn)展下去直到把一切的頂點都的那個頂點包括進(jìn)生成樹，如此進(jìn)展下去直到把一切的頂點都包括進(jìn)生成樹。包括進(jìn)生成樹。 最小生成樹不是獨一的。最小生成樹不是

34、獨一的。 圖的最短途徑圖的最短途徑 最短途徑最短途徑 :在帶權(quán)的有向圖中求兩個頂點間長度最短的途徑問題。在帶權(quán)的有向圖中求兩個頂點間長度最短的途徑問題。兩種情況：一是求從一個頂點到其他各頂點的最短途徑兩種情況：一是求從一個頂點到其他各頂點的最短途徑； 二是求每對頂點之間的最短途徑。二是求每對頂點之間的最短途徑。03030350201502051504510500A的最短路徑到尚未找到從的最短路徑到已找到從iiVVVVis0001AOV網(wǎng)和拓?fù)渑判蚓W(wǎng)和拓?fù)渑判駻OV網(wǎng)網(wǎng) :在有向圖中，用頂點表示活動，用有向邊表示活動之間在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后關(guān)系。稱這樣有向圖為用頂點表示活動的網(wǎng)絡(luò)，簡稱的先后關(guān)系。稱這樣有向圖為用頂點表示活動的網(wǎng)絡(luò)，簡稱AOV網(wǎng)網(wǎng)(Activity On Vertices) 。 拓?fù)湫蛄泻屯負(fù)渑判颍和負(fù)湫蛄泻屯負(fù)渑判颍簩⒁粋€將一個AOV網(wǎng)一切頂點排成一個線性序列，并使該序列網(wǎng)一切頂點排成一個線性序列，并使該序列滿足以下條件：滿足以下條件：假設(shè)在