【文章內容簡介】 刪除 0,2邊 鄰接表表示法 要點： 為圖中每一個頂點建立一個單鏈表； 頂點 u的單鏈表中的每一個結點指示 u的一個 鄰接點 v ， 即代表一條邊 (u,v) 或 u,v 頂點 u的單鏈表記錄了與 u相鄰接 (鄰接自 u)的所有頂點。 每個單鏈表相當于鄰接 矩陣的一行 ,它指示了該行中的非零的元素。 0 1 3 2 01 2 3 ? 1 ? 3 ? 0 0 2 ? 邊結點的結構 adjVex W nextArc (b) 帶權的邊結點 adjVex nextArc (a) 邊結點 指示頂點 u的一個鄰接點 指向 u的下一個邊結點 邊上的權值 u ? 1 ? 3 ? v 0 2 ? element firstArc (c) 頂點結點 存放頂點的名稱及其他信息 指向 u的第一個邊結點 u ? 1 ? 3 ? v 0 2 ? 每個單鏈表可設立一個存放頂點 u的有關信息的表頭結點，也稱頂點結點 。 頂點結點存入一個一維數(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。 邊結點的結構類型 圖中的頂點數(shù) 01 2 3 ? 1 ? 3 ? 0 0 2 ? A 鄰接表的表頭組成一維指針數(shù)組， A是指向該數(shù)組的指針 3. 建立鄰接表 函數(shù) CreateGraph構造一個有 n個頂點，但 不包含邊 的有向圖。由于圖的頂點數(shù)事先并不知道，所以我們使用動態(tài)存儲分配的一維指針數(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 ... ? ? ? 搜索、插入或刪除從頂點 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的邊結點 圖的遍歷 圖的遍歷 : 指從圖 G的任意一個頂點 v出發(fā)，訪問圖中所有結點且每個結點僅訪問一次的過程。 圖遍歷的方法 :深度優(yōu)先搜索 （類似于樹的先序遍歷）和 寬度優(yōu)先搜索 （類似于樹的按層次遍歷） 課堂提要 第 10章 圖 圖的基本概念 圖的存儲結構 圖的遍歷 最小代價生成 樹 深度優(yōu)先遍歷 圖遍歷與樹遍歷的差異 : 從圖中任意一個頂點出發(fā)未必能到達其它所有頂點； 圖中存在回路時，又可能多次經過同一個頂點。 為了避免發(fā)生上述兩種情況 ， 圖的搜索算法通常為圖的每個頂點保留一個標志位 (mark bit)。 算法開始時 ， 所有頂點的標志位清零 。 在遍歷過程中 ， 當某個頂點被訪問時 ， 其標志位被標記 。 在搜索中遇到被標記過的頂點則不再訪問它 。 搜索結束后 ， 如果還有未標記過的頂點 ， 遍歷算法可以選一個未標記的頂點 ， 從它出發(fā)開始繼續(xù)搜索 。 深度優(yōu)先搜索算法 從圖 G中某個頂點 v出發(fā) ,深度優(yōu)先搜索 圖的 DFS算法如下： 訪問頂點 v并打上標記。 依次從 v的未訪問過的鄰接點出發(fā)，深度優(yōu)先搜索 圖 G. 從 A出發(fā) 將訪問走過的邊保留，去掉訪問時未走過的邊，就得到以 A為根的 DFS生成樹。 如果是連通的無向圖或強連通的有向圖，上述 DFS算法必定可以系統(tǒng)地訪問圖中的全部頂點。