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

更新時間：2020年04月26日 17:23:41 作者：xiaoming1430026911

這篇文章主要為大家詳細介紹了C++實現(xiàn)鄰接表頂點的刪除，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C++實現(xiàn)鄰接表頂點的刪除代碼，供大家參考，具體內(nèi)容如下

這里的邊是無向邊

刪除頂點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)?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; 
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: