【正文】 i]) DFSM(G,i)。 } void DFSM(MGraph *G， int i) { int j。 printf(\t\t深度優(yōu)先遍歷結點：結點 %c\n， Gvexs[i])； visited[i]=TRUE。 //TRUE在 C語言中定義為 0， 以下同 for(j=0。jGn。j++) if(Gedges[i][j]==1amp。amp。!visited[j]) DFSM(G,j)。 } 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 (Breadth First Search)遍歷類似于樹的按層遍歷 。 ? 廣度優(yōu)先搜索的方法如下 : ① 首先訪問出發(fā)點 V， 接著依次訪問 V的所有鄰接點 W1,W2,W3… ； ② 然后再依次訪問與 W1,W2,W3… 鄰接的所有未訪問過的頂點 ， 依次類推； ③ 直到所有連通的結點都已訪問到為止； ④ 若此時圖中仍有未訪問過的結點 ， 則選一個未訪問過的結點作為源點重復上述操 作 ， 直至所有結點均已被訪問 。 ? 廣度優(yōu)先搜索的時間復雜度為 O(n+e)。 廣度優(yōu)先搜索 在鄰接表的存儲結構下進行廣度優(yōu)先搜索的算法 (算法 )如下 : void BFSTraverseM(MGraph *G) { int visited[max]。 int I。 for(i=0。iGn。i++) visited[i]=FALSE。 for(i=0。iGn。i++) if(!visited[i]) BFSM(G,i)。 } void BFSM(MGraph *G,int k) { int i,i。 CirQueue Q。 InitQueue(amp。Q)。 //初始化 printf(廣度優(yōu)先遍歷 ：結點 %c\n,Gvexs[k])。 visited[k]=TRUE。 EnQueue(amp。Q,k)。 while(!QueueEmpty(amp。Q)) { i=OutQueue(amp。Q)。 //出隊 for(j=0。jGn。j++) if(Gedges[i][j]==1amp。amp。!visited[j]) { printf(“ 廣度優(yōu)先遍歷結點： %c\n， Gvexs[j])。 visited[i]=TRUE。 EnQueue(amp。Q,j)。 //進隊 } } } 生成樹和最小生成樹 ? 生成樹 ? 最小生成樹 生成樹 ? 構造生成樹的方法有以下兩種 : ? 使用深度優(yōu)先搜索方法遍歷一個連通圖 ， 所經(jīng)過的邊和頂點成為一棵樹 ， 稱為深度優(yōu)先生成樹 。 如圖 (a)所示 。 ? 使用廣度優(yōu)先搜索方法遍歷一個連通圖 ， 所經(jīng)過的邊和頂點成為一棵樹 ， 稱為廣度優(yōu)先生成樹 。 如圖 (b)所示 。 (a) 圖 G4的深度優(yōu)先生成樹 (b) 圖 G4廣度優(yōu)先生成樹 圖 生成樹 最小生成樹 ? 對加權的連通圖 ， 去掉多余的邊 ， 使圖成為樹 ， 樹的枝上的權值的和最小 ， 該樹稱為 最小生成樹 。 ? Prim方法 圖 Prim方法構造最小生成樹的過程 。 Prim方法： ① 從加權圖中選取權值最小的邊 ， 與該邊相關聯(lián)的頂點被選擇； ② 從與被選擇的頂點相關聯(lián)的未被選擇的邊中選取權值最小的邊 ， 若該邊使已經(jīng)選 擇的頂點和邊構成圈 ， 則去掉該邊； ③ 重復步驟 ② ， 直到?jīng)]有未被選擇也未被去掉的邊 ， 剩下的邊和圖的全部頂點構成最小生成樹 。 ? 2. 構造最小生成樹的 Kruskal方法 圖 Kruskal方法構造最小生成樹的過程。 圖 用 Prim方法構造最小生成樹的過程 (a) (b) (c) (d) (e) (f) 圖 用 Kruskal方法構造最小生成樹的過程 習 題 ? 1 填空題 ? 2 選擇題 ? 3 問答題 習 題 __填空題 ? 1. 填空題 (1) 一個具有 n個頂點的完全圖的邊數(shù)為 ____________。 (2) 無向圖中的連通分量定義為無向圖的 ____________。 (3) 設無向圖 G的頂點數(shù)為 n，則 G最少有 ______________條邊。 (4) 一個具有 n個頂點的有向完全圖的弧數(shù)為 ____________。 (5) 有向圖中的強連通分量定義為有向圖的 ____________。 習 題 __選擇題 (1) 連通分量是 _______的極大連通子圖 。 C. 樹 (2) 強連通分量是 _______的極大連通子圖 。 C. 樹 (3) 有 n個頂點的無向圖的鄰接矩陣是用 ______數(shù)組存儲 。 n列 n列 (4) 有 n條邊的無向圖的鄰接表存儲法中 ， 鏈表中結點的個數(shù)是 ______個 。 A. n B. 2n C. n/2 D. n*n (5) 某圖的鄰接表如圖 。 ① 從 V1頂點進行深度優(yōu)先搜索 ， 搜索中要經(jīng)過的順序是 _______。 ② 從 V1頂點進行廣度優(yōu)先搜索 ， 搜索中要經(jīng)過的順序是 _______。 習 題 __選擇題 (6) — 個加權的無向連通圖的最小生成樹 ________。 B. 只有一棵 D. 可能不存在 (7) 下列有關圖遍歷的說法中不正確的是 _______。 “ 先進先出 ” 的特征 (8) 無向圖的鄰接矩陣是一個 _______。 A. 對稱矩陣 B. 零矩陣 (9) 下列說法中正確的是 _______。 n個頂點的無向完全圖的邊數(shù)為 n(n1) ， 每調用一次深度優(yōu)先搜索算法都得到該圖 的一個連通分量 (10) 如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點 ，則該圖一定是 _______。 習 題 __問答題 3. 問答題 (1) 假設圖的頂點是 A， B， … ， 請根據(jù)如圖 出相應的無向圖或有向圖 。 (2) 假設一棵完全圖包含 A， B， … ， G七個結點 ， 寫出其鄰接矩陣 。 (3) 假設一棵完全圖包含 A， B， C， D四個結點 ， 畫出其鄰接表 。 (4) 按圖 V6點出發(fā)進行廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列 圖 某圖的鄰接表 習 題 __問答題 (5) 按圖 V1點出發(fā)進行廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列 。 (6) 畫出如圖 。 (7) 根據(jù)如圖 ， 回答問題 。 ① 該圖是強連通圖嗎 ？ 若不是 ， 則給出其強連通分量 。 ② 請給出兩個有向環(huán) 。 ③ 請給出每個頂點的度 、 入度和出度 。 ④ 請給出其鄰接表 、 鄰接矩陣及逆鄰接表 。 (8)已知一個無向圖 G的鄰接矩陣如圖 ， 假設對其每行元素訪問時必須從右到左 ， 請寫出從 V0開始的深度優(yōu)先搜索的序列 。 (9) 已知某無向圖 G的鄰接矩陣如圖 。 假設對其訪問時每行元素必須從右到左 ， 請畫出其所有連通分量 。 (10)已知無向圖 G的鄰接表如圖 ， 請畫出其所有的連通分量 。 ??????????????????????????????01010000011000101000001100111101111011110(a) (b) 圖 鄰接矩陣 圖 加權圖 圖 有向圖 012340 1 2 3 4V 0 1 1 0 0V 1 0 1 1 1V 1 1 0 1 1V 0 1 1 0 1V 0 1 1 1 0 V V V V V????????????????圖 一個無向圖 G的鄰接矩陣 012340 1 2 3 4V 0 0 0 1 0V 0 0 1 0 1V 0 1 0 0 0V 1 0 0 0 0V 0 1 0 0 0V V V V V??????????圖 某無向圖 G的鄰接矩陣 圖 無向圖 G的鄰接表 Q amp。 A? Thanks! 第 7章 內 部 排 序 （時間： 3次課， 6學時） 第 7章 內 部 排 序 ? 教學提示： 本章介紹的各種方法有直接的應用價值。將重點介紹排序方法及實現(xiàn)方法，并分析各種排序方法的特點和優(yōu)點。 ? 教學目標： 通過本章的學習，使讀者能掌握內部排序的概念、方法和算法，并能靈活應用。 第 7章 內 部 排 序 ? 排序概述 ? 插入排序 ? 快速排序 ? 選擇排序 ? 基數(shù)排序 ? 各種內部排序方法的比較 ? 上機實習 ? 習題 排序概述 ? 排序 (Sorting)是計算機程序設計中的一種重要操作 ， 它的功能是將若干個數(shù)據(jù)元素 (或記錄 )構成的任意序列 ， 重新排列成一個按關鍵字排序的序列 。 按關鍵字排序的表或文件便于查找 。 ① 排序是將一組任意排列的數(shù)據(jù)元素按關鍵字的值從小到大或從大到小重新排列成有序的序列 。 ② 排序方法有許多種 ， 可以分為穩(wěn)定的或不穩(wěn)定的 。 在排序前 ， 關鍵字值相等的不同記錄間的前后相對位置保持不變的排序方法稱為 穩(wěn)定的排序方法 。 否則稱為 不 穩(wěn)定的排序方法 。 ③ 內部排序 是指在排序的整個過程中 ， 全部數(shù)據(jù)排序都在計算機的內存中完成 。 ④ 外部排序 是指在排序的整個過程中 ， 全部數(shù)據(jù)都存儲在計算機的外部存部儲器中 ， 在進行排序時 ， 借助于內存儲器進行排序 。 排序概述 ? 排序的定義 ? 穩(wěn)定排序與非穩(wěn)定排序 ? 內部排序與外部排序 ? 排序記錄的存儲方式 排序的定義 假設含 n個記錄的序列為： {R1， R2， … ， Rn} 其相應的關鍵字序列為： {K1， K2， … ， Kn} 需確定 1， 2， … ， n的一種排列 p1， p2， … ， pn， 使其相應的關鍵字滿足如下的非遞減 (或非遞增 )關系： Kp1≤Kp2≤… ≤Kpn 即使式 (71)的序列成為一個按關鍵字有序的序列： {Rp1， Rp2， … ， Rpn} 這樣一種操作稱為 排序 。 穩(wěn)定排序與非穩(wěn)定排序 ? 排序定義中的 關鍵字 Ki可以是記錄 Ri(i=1， 2， … ， n)的主關鍵字 ， 也可以是記錄 Ri的次關鍵字 ， 甚至是若干數(shù)據(jù)項的組合 。 ? 若 Ki是主關鍵字 ， 則任何一個記錄的無序序列經(jīng)排序后得到的結果是惟一的 。 若 Ki是次關鍵字 ， 則排序的結果不惟一 ， 因為待排序的記錄序列中可能存在兩個或兩個以上關鍵字相等的記錄 。 ? 提示： 假設記錄 Ri和 Rj (1≤i≤n， 1≤j≤n， i≠j)的關鍵字 Ki=Kj，且在排序前的序列中 Ri領先于 Rj(即 ij)， 若在排序后的序列中 Ri仍領先于 Rj， 則稱所用的排序方法是穩(wěn)定的 。 反之 ，若可能使排序后的序列中 Rj領先于 Ri， 則稱所用的排序方法是不穩(wěn)定的 。 內部排序與外部