dbs第十章ppt課件(編輯修改稿)
2025-06-01 12:08 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 刪除 0,2邊 鄰接表表示法 要點(diǎn)： 為圖中每一個(gè)頂點(diǎn)建立一個(gè)單鏈表； 頂點(diǎn) u的單鏈表中的每一個(gè)結(jié)點(diǎn)指示 u的一個(gè) 鄰接點(diǎn) v ， 即代表一條邊 (u,v) 或 u,v 頂點(diǎn) u的單鏈表記錄了與 u相鄰接 (鄰接自 u)的所有頂點(diǎn)。 每個(gè)單鏈表相當(dāng)于鄰接 矩陣的一行 ,它指示了該行中的非零的元素。 0 1 3 2 01 2 3 ? 1 ? 3 ? 0 0 2 ? 邊結(jié)點(diǎn)的結(jié)構(gòu) adjVex W nextArc (b) 帶權(quán)的邊結(jié)點(diǎn) adjVex nextArc (a) 邊結(jié)點(diǎn) 指示頂點(diǎn) u的一個(gè)鄰接點(diǎn) 指向 u的下一個(gè)邊結(jié)點(diǎn) 邊上的權(quán)值 u ? 1 ? 3 ? v 0 2 ? element firstArc (c) 頂點(diǎn)結(jié)點(diǎn) 存放頂點(diǎn)的名稱及其他信息 指向 u的第一個(gè)邊結(jié)點(diǎn) u ? 1 ? 3 ? v 0 2 ? 每個(gè)單鏈表可設(shè)立一個(gè)存放頂點(diǎn) u的有關(guān)信息的表頭結(jié)點(diǎn)，也稱頂點(diǎn)結(jié)點(diǎn) 。 頂點(diǎn)結(jié)點(diǎn)存入一個(gè)一維數(shù)組。 01 2 3 2 ? 1 0 3 ? 1 3 ? 1 3 ? 2 0 (a)圖 G1的鄰接表 0 1 3 2 圖 G1 01 2 3 ? 1 ? 3 ? 0 0 2 ? (b)圖 G2的鄰接表 0 1 3 2 圖 G2 01 2 3 ? 3 3 ? 0 1 1 1 ? 2 5 ? 0 4 (c)圖 G3的鄰接表 4 0 1 3 2 圖 G3 3 1 1 5 typedef struct enode{ int AdjVex。 T W。 struct enode * NextArc。 }ENode。 typedef struct graph{ int Vertices 。 ENode** A。 } Graph。 邊結(jié)點(diǎn)的結(jié)構(gòu)類型 圖中的頂點(diǎn)數(shù) 01 2 3 ? 1 ? 3 ? 0 0 2 ? A 鄰接表的表頭組成一維指針數(shù)組， A是指向該數(shù)組的指針 3. 建立鄰接表 函數(shù) CreateGraph構(gòu)造一個(gè)有 n個(gè)頂點(diǎn)，但 不包含邊 的有向圖。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動(dòng)態(tài)存儲(chǔ)分配的一維指針數(shù)組 。 void CreateGraph(Graph* g, int n) { int i。 gVertices=n。 gA=(ENode**)malloc(n*sizeof(ENode*))。 for(i=0。 in。 i++) gA[i]=NULL。 } 0 1 ... n1 ... ? ? ? 搜索、插入或刪除從頂點(diǎn) u發(fā)出的邊，只在 A[u]所指向的單鏈表中操作 。程序如下： 邊的搜索、插入和刪除 01 2 3 2 ? 1 0 3 ? 1 3 ? 1 3 ? 2 0 1,2是否有邊？ //搜索邊的函數(shù) BOOL Exist(Graph g, int u, int v) { int n。 ENode* p。 n=。 if(u0 || un1) return FALSE。 for(p=[u]。 pamp。amp。pAdjVex!=v。 ) p=pNextArc。 if (!p) return FALSE。 return TRUE。 } //插入邊的函數(shù) BOOL Add(Graph *g, int u, int v, T w) { int n。 ENode *p。 n=gVertices。 if (u0 || v0 || un1 || vn1 || u==v || Exist(*g, u, v)){ printf(BadInput\n)。 return FALSE。 } p=NewENode(v, w, gA[u])。 gA[u]=p。 return TRUE。 } 01 2 3 ? 1 ? 3 ? 0 0 2 ? p ↓ 1,3 3 0 1 3 2 插入鄰接表中由指針 A[u]所指示的單鏈表的最前面 ENode* NewENode( int vex, T weight, ENode* nextarc) { ENode* p。 p=(ENode*)malloc(sizeof(ENode))。 pAdjVex=vex。 pW=weight。 pNextArc=nextarc。 return p。 } //刪除邊的函數(shù) BOOL Delete(Graph *g, int u, int v) { int n=gVertices。ENode* p, *q。 if(u1 amp。amp。 un) { p=gA[u]。 q=NULL。 while (pamp。amp。 pAdjVex!=v){ q=p。 p=pNextArc。 } if (p) { if (q) qNextArc=pNextArc。 else gA[u]=pNextArc。 free(p)。 return TRUE。 } } printf(BadInput\n)。 return FALSE。 } 01 2 3 ? 1 ? 3 ? 0 0 2 ? 0 1 3 2 3 1,3 P ↓ q=NULL 在由指針 A[u]所指示的單鏈表中，搜索 AdjVex域的值為 v的邊結(jié)點(diǎn) 圖的遍歷 圖的遍歷 : 指從圖 G的任意一個(gè)頂點(diǎn) v出發(fā)，訪問(wèn)圖中所有結(jié)點(diǎn)且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次的過(guò)程。 圖遍歷的方法 :深度優(yōu)先搜索 （類似于樹(shù)的先序遍歷）和 寬度優(yōu)先搜索 （類似于樹(shù)的按層次遍歷） 課堂提要 第 10章 圖 圖的基本概念 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷 最小代價(jià)生成 樹(shù) 深度優(yōu)先遍歷 圖遍歷與樹(shù)遍歷的差異 : 從圖中任意一個(gè)頂點(diǎn)出發(fā)未必能到達(dá)其它所有頂點(diǎn)； 圖中存在回路時(shí)，又可能多次經(jīng)過(guò)同一個(gè)頂點(diǎn)。 為了避免發(fā)生上述兩種情況 ， 圖的搜索算法通常為圖的每個(gè)頂點(diǎn)保留一個(gè)標(biāo)志位 (mark bit)。 算法開(kāi)始時(shí) ， 所有頂點(diǎn)的標(biāo)志位清零 。 在遍歷過(guò)程中 ， 當(dāng)某個(gè)頂點(diǎn)被訪問(wèn)時(shí) ， 其標(biāo)志位被標(biāo)記 。 在搜索中遇到被標(biāo)記過(guò)的頂點(diǎn)則不再訪問(wèn)它 。 搜索結(jié)束后 ， 如果還有未標(biāo)記過(guò)的頂點(diǎn) ， 遍歷算法可以選一個(gè)未標(biāo)記的頂點(diǎn) ， 從它出發(fā)開(kāi)始繼續(xù)搜索 。 深度優(yōu)先搜索算法 從圖 G中某個(gè)頂點(diǎn) v出發(fā) ,深度優(yōu)先搜索 圖的 DFS算法如下： 訪問(wèn)頂點(diǎn) v并打上標(biāo)記。 依次從 v的未訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索 圖 G. 從 A出發(fā) 將訪問(wèn)走過(guò)的邊保留，去掉訪問(wèn)時(shí)未走過(guò)的邊，就得到以 A為根的 DFS生成樹(shù)。 如果是連通的無(wú)向圖或強(qiáng)連通的有向圖，上述 DFS算法必定可以系統(tǒng)地訪問(wèn)圖中的全部頂點(diǎn)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1