温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C++如何实现邻接表顶点的删除

发布时间:2020-07-30 13:42:12 来源:亿速云 阅读:217 作者:小猪 栏目:编程语言

这篇文章主要讲解了C++如何实现邻接表顶点的删除,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。

这里的边是无向边

删除顶点v时,要找到顶点v的邻接顶点w,把w中指向v的边删除掉,再删除边(v,w)。循环这个过程,直到把和顶点v有关的边都删除掉为止。

再接着需要删除顶点v。

不可以直接像数组那样直接把顶点v之后的顶点位置像前移动一位,因为这样其他顶点的位置将会发生变化,顶点边中的顶点位置将会出错。

边和顶点的定义如下:

struct Edge{//边节点的定义 
int dest;//边的另一顶点位置 
E cost;//边上的权值 
Edge<T, E> *link;//下一条边链指针 
Edge(){}//构造函数 
Edge(int num, E weight):dest(num),cost(weight),link(NULL){}//构造函数 
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;//边链表的头指针 
}; 

删除函数如下:

//在图中删除一个指定顶点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++如何实现邻接表顶点的删除有进一步的了解,如果还想学习更多内容,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI