好资源导航 » 文章资讯 » C++实现邻接表顶点的删除

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

2023-07-26 16:30:04 73

本文实例为大家分享了C++实现邻接表顶点的删除代码，供大家参考，具体内容如下

这里的边是无向边

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

再接着需要删除顶点v。

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

边和顶点的定义如下：

structEdge{//边节点的定义
intdest;//边的另一顶点位置
Ecost;//边上的权值
Edge*link;//下一条边链指针
Edge(){}//构造函数
Edge(intnum,Eweight):dest(num),cost(weight),link(NULL){}//构造函数
booloperator!=(Edge&R)const{
return(dest!=R.dest)?true:false;
}
};

template
structVertex{//顶点的定义
Tdata;//顶点的名字
Edge*adj;//边链表的头指针
};

删除函数如下：

//在图中删除一个指定顶点v，v是顶点号。
template
boolGraphlink::removeVertex(intv){
if(v<0||v>=numVertices||numVertices==1)returnfalse;

Edge*t,*p,*s;
inti,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;
}
deletes;
}
//以上代码是用来将顶点v的入度删除

NodeTable[v].adj=p->link;
deletep;//删除顶点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;
}
elses=s->link;
}
p=p->link;

}
returntrue;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
514930285
czq8825@qq.com

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

热门推荐

随机推荐