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

时间:2022-01-24 09:32:43

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

这里的边是无向边

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

再接着需要删除顶点v。

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

边和顶点的定义如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)?true:false;
}
};
 
template <class T, class E>
struct Vertex{//顶点的定义
T data;//顶点的名字
Edge<T, E> *adj;//边链表的头指针
};

删除函数如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//在图中删除一个指定顶点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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/xiaoming1430026911/article/details/76217518