溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

C++如何實現(xiàn)鄰接表頂點的刪除

發(fā)布時間：2020-07-30 13:42:12 來源：億速云 閱讀：214 作者：小豬 欄目：編程語言

這篇文章主要講解了C++如何實現(xiàn)鄰接表頂點的刪除，內容清晰明了，對此有興趣的小伙伴可以學習一下，相信大家閱讀完之后會有幫助。

這里的邊是無向邊

刪除頂點v時，要找到頂點v的鄰接頂點w，把w中指向v的邊刪除掉，再刪除邊（v,w)。循環(huán)這個過程，直到把和頂點v有關的邊都刪除掉為止。

再接著需要刪除頂點v。

不可以直接像數(shù)組那樣直接把頂點v之后的頂點位置像前移動一位，因為這樣其他頂點的位置將會發(fā)生變化，頂點邊中的頂點位置將會出錯。

邊和頂點的定義如下：

struct Edge{//邊節(jié)點的定義 
int dest;//邊的另一頂點位置 
E cost;//邊上的權值 
Edge<T, E> *link;//下一條邊鏈指針 
Edge(){}//構造函數(shù) 
Edge(int num, E weight):dest(num),cost(weight),link(NULL){}//構造函數(shù) 
bool operator!=(Edge<T, E>& R)const{ 
return (dest!=R.dest)&#63;true:false; 
} 
}; 
 
template <class T, class E> 
struct Vertex{//頂點的定義 
T data;//頂點的名字 
Edge<T, E> *adj;//邊鏈表的頭指針 
};

刪除函數(shù)如下：

//在圖中刪除一個指定頂點v，v是頂點號。 
template <class T, class E> 
bool Graphlink<T,E>::removeVertex(int v){ 
 if(v<0||v>=numVertices||numVertices==1)return false; 
 
 Edge<T,E> *t, *p, *s; 
 int i, k; 
 
 while(NodeTable[v].adj!=NULL){ //將頂點 
 p = NodeTable[v].adj; 
 k = p->dest; 
 s = NodeTable[k].adj; 
 t = NULL; 
 while(s!=NULL&&s->dest!=v){ 
  t = s; s = s->link; 
 } 
 
 if(s!=NULL){ 
  if(t==NULL){//說明第一條邊的另一個頂點就是v 
   NodeTable[k].adj = s->link; 
  } 
  else{ 
   t->link = s->link; 
  } 
  delete s; 
 } 
 //以上代碼是用來將頂點v的入度刪除 
 
 NodeTable[v].adj = p->link; 
 delete p;//刪除頂點v的邊 
 numEdges--; 
} 
//以上代碼將所有涉及到頂點v的邊都刪除了，接下來要調整表結構 
 
 numVertices--; 
 
 NodeTable[v].data = NodeTable[numVertices].data; 
 p = NodeTable[v].adj = NodeTable[numVertices].adj; 
 
 //把原來頂點numVertices的入度改為頂點v的入度 
 while(p!=NULL){ 
  s = NodeTable[p->dest].adj; 
  while(s!=NULL){ 
  if(s->dest==numVertices){ 
  s->dest = v; 
  break; 
  } 
  else s = s->link; 
  } 
  p = p->link; 
 
 } 
 return true; 
}

看完上述內容，是不是對C++如何實現(xiàn)鄰接表頂點的刪除有進一步的了解，如果還想學習更多內容，歡迎關注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。

AI
助
手