devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】图的基本操作_1、分别以临接矩阵和临接表作为存储结构,实现以下图的基本操作: (1)增加新节点 (

作者：运维做开发 | 2024-08-15 18:37:27

赞

踩

1、分别以临接矩阵和临接表作为存储结构,实现以下图的基本操作: (1)增加新节点 (

一、问题描述

分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：

  • 增加一个新结点v，Insert(G,v)；
  • 删除顶点v及其相关的边，Delete(G,v)；
  • 增加一条边<v,w>，Insert(G,v,w)；
  • 删除一条边<v,w>，Delete(G,v,w)；

二、设计思路

1、邻接矩阵实现：

        邻接矩阵实现图的基本操作，主要通过二维数组寻址方式进行数据处理。函数包括：邻接矩阵创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接矩阵打印。

        邻接矩阵创建并存储，先根据输入的总顶点数、边数对二维数组初始化，边权为MaxInt，表示两点无关联。将顶点信息存储至顶点数组集中。存储数据时，依次循环根据输入边相关的两点以及权重，先通过顶点寻址函数寻找两点位置，后利用二维数组将矩阵相应位置边权赋予新值，完成数据存储。

        顶点寻址函数设计，只需根据顶点信息，在顶点数组集中遍历，返回其对应数组下标即可。

        增加顶点时，在顶点数组集中增加一位，并将邻接矩阵中多加的一行一列赋值为MaxInt。

        删除顶点时，需要通过数组移动，列方面从待删点开始右侧数据，全部左移；行方面从待删顶点开始下方数据，全部上移。最后删除顶点在顶点数组中的位置。上述操作通过数组移动实现开销较大，也可以在删除时，将最后一个顶点相关信息替代删除顶点，因为本身顶点在数组中的位置无现实意义，可减少算法时间复杂度。

        增加边时，通过顶点寻址函数获取两个顶点位置，通过二维数组将邻接矩阵中对应的边权赋予新值即可。

        删除边时，通过顶点寻址函数获取两个顶点位置，通过二维数组将邻接矩阵中对应的边权赋予MaxInt即可。

        邻接矩阵打印，只需通过二维数组，将其各行各列依次输出，为了增加矩阵可观性，可输出行名、列名以及控制权重输出格式。

        最后通过主函数测试上述所有的函数。

2、邻接表实现：

        邻接表实现图的基本操作，主要通过数组+链表方式进行数据处理。函数包括：邻接表创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接表打印。

        邻接表创建并存储，先根据输入的总顶点数、边数对邻接表初始化，数组单元接收顶点信息，由于开始无边，将各单元firstarc指针赋NULL，避免野指针。存储边信息时，创建两个边结点并创建相应指针，在边结点中存储边权以及关联点通过顶点寻址函数查找的下标（如a、b两个顶点，则边结点e1中adjvex存放为b的下标，边结点e2中adjvex存放为a的下标）。并将边结点插入各自数组单元的关联顶点链表首结点（即被各单元firstarc指针指向）。

        顶点寻址函数设计，只需根据顶点信息，在顶点数组集中遍历，返回其对应数组下标即可。

        增加顶点，只需在邻接表数组单元vertices中存储新的顶点信息，并将其firstarc指针赋值为NULL。

        删除顶点，下述操作：先删除待删顶点中所有关联顶点链表中其他顶点信息 ；用最后一个顶点替代删除结点位置(目的在于避免顶点表中出现废弃点占位情况)。实现操作需要遍历邻接表数组单元vertices中关联顶点链表中所有的adjvex，与待删顶点的位置下标比对，相同时删除该结点。结点删除时，需要单独优先考虑表头首结点元素中adjvex是否为待删结点下标，循环删除至表头结点adjvex不为待删结点下标为止，遍历后续所有结点（优先考虑的原因是表头结点有一个firstarc指向问题，不考虑则会出现断链情况）。删除完待删结点在其他单元的信息时，循环待删结点所在单元格关联顶点链表所有结点，将firstarc赋值为NULL。最后将数组vertices中最后一个顶点替代待删结点位置（数组前移覆盖会增加额外的开销）。

        增加边即为上述邻接表存储步骤单次操作，通过创建两个边结点，分别赋值相应数据后，插入两个对应vertices单元格的关联顶点链表的表头（即成为首结点）。

        删除边，即为删除顶点中单次操作，先定位待删边的两个顶点位置，然后遍历两个顶点对应数组vertices单元中的关联顶点链表，查找adjvex的值，删除含有对应顶点位置的边结点，同样注意单独考虑首结点是否含有删除对应顶点位置信息。

        用于删除函数多次使用，因此在优化时，将输出函数提取。

        邻接表打印时，依次访问vertices所有单元中的关联顶点链表，输出所有其中边结点的adjvex对应的顶点信息以及边权。

        最后通过主函数测试上述所有函数。

三、代码展示

1、邻接矩阵实现：

  1. #include<iostream>
  2. using namespace std;
  3. typedef int Status;
  4. #define OK 1
  5. #define ERROR -1
  6. #define MaxInt 32767			//初始化边权无穷大
  7. #define MVNum 100
  8. #define VerTexType char
  9. #define ArcType int
  10.  
  11. typedef struct AMGraph{		//定义邻接矩阵
  12.  VerTexType vexs[MVNum];   	//创建顶点集
  13.  ArcType arcs[MVNum][MVNum];  //创建邻接矩阵
  14.  int vexnum,arcnum;   			//存放当前图的总顶点数和边数
  15. };
  16.  
  17. int VexLocate(AMGraph &G,VerTexType u){	//返回顶点在顶点集的位置
  18.  for(int i=0;i<G.vexnum;i++){		//循环遍历顶点集
  19.   if(u==G.vexs[i]) return i;		//找到顶点返回其数组下标
  20.  }
  21.  return -1;
  22. }
  23.  
  24. Status UDNCreate(AMGraph &G){		//无向邻接矩阵创建并存储数据
  25.  cout<<"请输入无向图总顶点数和总边数：";
  26.  cin>>G.vexnum>>G.arcnum;  		//输入图的顶点数和边数
  27.  cout<<"请输入顶点信息：";
  28.  for(int i=0;i<G.vexnum;i++){
  29.   cin>>G.vexs[i];
  30.  }
  31.  for(int i=0;i<G.vexnum;i++){ 			//初始化邻接矩阵边权为无穷 
  32.   for(int j=0;j<G.vexnum;j++){
  33.    G.arcs[i][j]=MaxInt;
  34.   }
  35.  }
  36.  VerTexType v1,v2;						//结点信息
  37.  ArcType w;								//边权重
  38.  cout<<"请输入边的两顶点及所构边的权重："<<endl; 
  39.  for(int i=0;i<G.arcnum;i++){		//利用二维数组寻址相对两点赋权
  40.   cin>>v1>>v2>>w;    				//依次输入两个顶点以及所构边的权重
  41.   G.arcs[VexLocate(G,v1)][VexLocate(G,v2)]=w;
  42.   G.arcs[VexLocate(G,v2)][VexLocate(G,v1)]=w;
  43.  }
  44.  return OK;
  45. }
  46.  
  47. Status VexInsert(AMGraph &G,VerTexType v){	//插入顶点
  48.  G.vexs[G.vexnum]=v;     //由于数组下标比数量少1，可用旧顶点数做下标
  49.  							  //增加新顶点 
  50.  G.vexnum++;      		  //顶点数加1 
  51.  for(int i=0;i<G.vexnum;i++){  //构建新顶点与其他顶点关联，初始化边权
  52.  									 //为无穷 
  53.   G.arcs[G.vexnum-1][i]=MaxInt;
  54.   G.arcs[i][G.vexnum-1]=MaxInt;
  55.  }
  56. }
  57.  
  58. Status VexDelete(AMGraph &G,VerTexType v){	//顶点删除
  59.  int p=VexLocate(G,v);					//存放待删顶点下标位置
  60.  for(int i=0;i<G.vexnum;i++){			//删除待删顶点所在列数据
  61.   for(int j=p+1;j<G.vexnum;j++){
  62.    G.arcs[i][j-1]=G.arcs[i][j];
  63.   }
  64.  }
  65.  for(int i=0;i<G.vexnum;i++){			//删除待删顶点所在行数据
  66.   for(int j=p+1;j<G.vexnum;j++){
  67.    G.arcs[j-1][i]=G.arcs[j][i];
  68.   }
  69.  }
  70.  for(int i=p+1;i<G.vexnum;i++){		//删除在顶点集中的待删顶点
  71.   G.vexs[i-1]=G.vexs[i];
  72.  }
  73.  G.vexnum--;							//顶点数自减
  74.  return OK;
  75. }
  76.  
  77. Status ArcInsert(AMGraph &G,VerTexType v1,VerTexType v2,ArcType w)
  78. { 												//插入边
  79.  int p1=VexLocate(G,v1),p2=VexLocate(G,v2);	//存放两个关联点位置
  80.  G.arcs[p1][p2]=w;						//将关联点在矩阵两处边权赋值
  81.  G.arcs[p2][p1]=w;
  82.  return OK;
  83. }
  84.  
  85. Status ArcDelete(AMGraph &G,VerTexType v1,VerTexType v2){//删除边
  86.  int p1=VexLocate(G,v1),p2=VexLocate(G,v2);	//存放两个关联点位置
  87.  G.arcs[p1][p2]=MaxInt;			  //将关联点在矩阵两处边权赋为无穷
  88.  G.arcs[p2][p1]=MaxInt;
  89.  return OK; 
  90. }
  91.  
  92. Status AMGraphPrint(AMGraph &G){	//打印无向邻接矩阵
  93.  cout<<"邻接矩阵展示："<<endl;
  94.  for(int i=0;i<G.vexnum;i++){
  95.   cout<<G.vexs[i]<<":";		  //输出矩阵行名
  96.   for(int j=0;j<G.vexnum;j++){	  //循环输出各点与其他点的边权，0为无边
  97.    if(G.arcs[i][j]!=MaxInt) cout<<G.arcs[i][j]<<"\t";
  98.    else cout<<"0"<<"\t";
  99.   }
  100.   cout<<endl;
  101.  }
  102.  return OK;
  103. }
  104.  
  105. int main(){
  106.  AMGraph G;					//创建无向邻接矩阵
  107.  UDNCreate(G);				//无向邻接矩阵初始化并存储数据
  108.  AMGraphPrint(G);			//打印无向邻接矩阵
  109.  VerTexType v1,v2;
  110.  ArcType w;
  111.  cout<<"请输入要插入的顶点：";
  112.  cin>>v1;
  113.  VexInsert(G,v1);			//插入顶点
  114.  AMGraphPrint(G);			//打印无向邻接矩阵
  115.  cout<<"请输入要删除的顶点：";
  116.  cin>>v2;
  117.  VexDelete(G,v2);			//删除顶点
  118.  AMGraphPrint(G);			//打印无向邻接矩阵
  119.  cout<<"请输入增加边的两个顶点及边权重：";
  120.  cin>>v1>>v2>>w;
  121.  ArcInsert(G,v1,v2,w);		//插入边
  122.  AMGraphPrint(G);			//打印无向邻接矩阵
  123.  cout<<"请输入删除边的两个顶点：";
  124.  cin>>v1>>v2;
  125.  ArcDelete(G,v1,v2);		//删除边
  126.  AMGraphPrint(G);			//打印无向邻接矩阵
  127.  return 0;
  128. }

2、邻接表实现：

  1. #include<iostream>
  2. using namespace std;
  3. typedef int Status;
  4. #define OK 1
  5. #define ERROR -1
  6. #define VerTexType char
  7. #define ArcType int
  8. #define MVNum 50 
  9.  
  10. typedef struct ArcNode{    //边结点 
  11.  int adjvex;     			//该边所指向的顶点位置
  12.  struct ArcNode* nextarc;  //指向下一条边指针
  13.  int weight;     			//边的权重 
  14. };
  15.  
  16. typedef struct VNode{   	//顶点信息 
  17.  VerTexType data;   		//顶点数据 
  18.  ArcNode *firstarc;   		//指向第一条与该点相连的边的指针 
  19. }VNode,AdjList[MVNum];   	//邻接表 
  20.  
  21. typedef struct{     		//定义图 
  22.  AdjList vertices;   		//顶点表 
  23.  int vexnum,arcnum;   		//图当前顶点数与边数 
  24. }ALGraph;
  25.  
  26. int VexLocate(ALGraph &G,VerTexType v){  //顶点定位，找出其在邻接表
  27.  												//中数组下标的位置 
  28.  for(int i=0;i<G.vexnum;i++){
  29.   if(v==G.vertices[i].data) return i;  //根据顶点数据查找，返回表中数
  30.  											  //组下标值 
  31.  }
  32.  return -1;
  33. }
  34.  
  35. Status ALGraphprint(ALGraph &G){    //邻接表打印函数 
  36.  cout<<"操作后新的连接表如下："<<endl;
  37.  for(int i=0;i<G.vexnum;i++){    //依次输出每个顶点与相连顶点的情况
  38.  									   //以及边权 
  39.   cout<<G.vertices[i].data<<":";   	 //输出当前顶点数据 
  40.   ArcNode* p=G.vertices[i].firstarc;  //指向与当前顶点相连的第一个顶
  41.  											//点的边的指针 
  42.   while(p!=NULL){       		//依次遍历所有与该顶点相连的点的边     
  43.    cout<<G.vertices[p->adjvex].data<<"("<<p->weight<<")"<<"\t"; 
  44.  									//输出与该顶点相连的所有点以及边的权重
  45.    p=p->nextarc;
  46.   }
  47.   cout<<endl;
  48.  }
  49.  return OK;
  50. }
  51.  
  52. Status Delete(ALGraph &G,int pos1,int pos2){ //删除邻接表中，指定两
  53.  													//顶点的边 
  54.  ArcNode* p=G.vertices[pos1].firstarc;  //指向pos1所表示顶点的与其
  55.  											   //第一个相连顶点的边的指针
  56.  if(p&&p->adjvex==pos2){      //由于firstarc指针固定，不能单纯删除p
  57.  									//的结点，因此表头结点需要单独考虑 
  58.   G.vertices[pos1].firstarc=p->nextarc; //如果表头结点存放连接信息为
  59.  										  //要删结点位置信息pos2，直接删除
  60.   delete p;
  61.  }
  62.  else{
  63.   while(p!=NULL){       		//否则从p开始循环遍历表中所有连接点
  64.    if(p->nextarc!=NULL&&p->nextarc->adjvex==pos2){  //如果找到要删
  65.  											  //结点pos2，进行链表删除操作
  66.     ArcNode* temp=p->nextarc;
  67.     p->nextarc=p->nextarc->nextarc;
  68.     delete temp;
  69.     break;
  70.    }
  71.    p=p->nextarc;      			//没有找到，p指针后移 
  72.   }
  73.  }
  74.  return OK;
  75. }
  76.  
  77. Status UDGCreate(ALGraph &G){		//邻接表创建并存储数据
  78.  cout<<"请输入图的总顶点数和总边数：";
  79.  cin>>G.vexnum>>G.arcnum;
  80.  cout<<"请输入顶点信息：";
  81.  for(int i=0;i<G.vexnum;i++){    //初始化表头结点指针域为NULL 
  82.   cin>>G.vertices[i].data;    	   //输入顶点数据 
  83.   G.vertices[i].firstarc=NULL;
  84.  }
  85.  VerTexType v1,v2;
  86.  ArcType w;
  87.  int pos1,pos2;
  88.  cout<<"请输入边的两顶点及所构边的权重："<<endl;
  89.  for(int i=0;i<G.arcnum;i++){    //输出边的信息 
  90.   cin>>v1>>v2>>w;
  91.   pos1=VexLocate(G,v1);     	   //获取顶点v1位置 
  92.   pos2=VexLocate(G,v2);     	   //获取顶点v2位置 
  93.   ArcNode* p1=new ArcNode;    	   //创建边结点 
  94.   p1->adjvex=pos2;     		   //v1开始的边所连另一端为v2位置
  95.   p1->weight=w;
  96.   p1->nextarc=G.vertices[pos1].firstarc;  
  97.   G.vertices[pos1].firstarc=p1;    //将边加入v1的边表头部
  98.   ArcNode* p2=new ArcNode;     	 //创建边结点
  99.   p2->adjvex=pos1;       			 //v2开始的边所连另一端为v1
  100.   p2->weight=w;
  101.   p2->nextarc=G.vertices[pos2].firstarc;
  102.   G.vertices[pos2].firstarc=p2;    //将边加入v2的边表头部 
  103.  }
  104.  return OK; 
  105. }
  106.  
  107. Status VexInsert(ALGraph &G,VerTexType v){  //实现顶点的插入 
  108.  G.vertices[G.vexnum].data=v;    //由于数组下标从0开始，则新增顶点存
  109.  									   //放位置为G.vexnum 
  110.  G.vertices[G.vexnum].firstarc=NULL; //避免野指针情况，指针域为NULL 
  111.  G.vexnum++;         			   //顶点数自增 
  112. }
  113.  
  114. Status VexDelete(ALGraph &G,VerTexType v){  //顶点删除 
  115.  int pos=VexLocate(G,v);      	//查找待删除顶点 
  116.  for(int i=0;i<G.vexnum;i++){ //删除其他顶点连接表中的待删除顶点信息
  117.   Delete(G,i,pos);
  118.   
  119.   //下半部份代码优化为Delete()函数 
  120. //  ArcNode* p=G.vertices[i].firstarc;
  121. //  if(p&&p->adjvex==pos){
  122. //   G.vertices[i].firstarc=p->nextarc;
  123. //   delete p;
  124. //  }
  125. //  else{
  126. //   while(p!=NULL){
  127. //    if(p->nextarc!=NULL&&p->nextarc->adjvex==pos){
  128. //     ArcNode* temp=p->nextarc;
  129. //     p->nextarc=p->nextarc->nextarc;
  130. //     delete temp;
  131. //     break;
  132. //    }
  133. //    p=p->nextarc;
  134. //   }
  135. //  }
  136.  }
  137.  
  138. //下述操作：1、先删除待删顶点中所有连接表中其他顶点信息 2、用最后一个顶
  139. //点替代删除结点位置(目的在于避免顶点表中出现废弃点占位情况)
  140.  ArcNode* p=G.vertices[pos].firstarc;  //p指向待删顶点的第一个连接
  141.  										   //点的边的指针 
  142.  G.vertices[pos].firstarc=NULL;     //野指针问题，删除记得赋值为NULL，
  143.  										  //否则运行无结果 
  144.  while(p!=NULL){        //循环删除该点连接表下所有顶点信息 
  145.   ArcNode* temp=p;
  146.   p=p->nextarc;
  147.   delete temp;
  148.  }
  149.  G.vertices[pos]=G.vertices[G.vexnum-1];  //将最后一个顶点替代删除
  150.  												 //顶点的位置 
  151.  G.vexnum--;         						 //顶点数自减 
  152.  return OK; 
  153. }
  154.  
  155. Status ArcInsert(ALGraph &G,VerTexType v1,VerTexType v2,int w){  
  156.  												//插入边 
  157.  int pos1,pos2;
  158.  pos1=VexLocate(G,v1);
  159.  pos2=VexLocate(G,v2);
  160.  ArcNode* p1=new ArcNode;     //创建边结点 
  161.  p1->adjvex=pos2;       		//v1开始的边所连另一端为v2位置 
  162.  p1->weight=w;
  163.  p1->nextarc=G.vertices[pos1].firstarc;  
  164.  G.vertices[pos1].firstarc=p1;//将边加入v1的边表头部
  165.  ArcNode* p2=new ArcNode;     //创建边结点
  166.  p2->adjvex=pos1;       		//v2开始的边所连另一端为v1
  167.  p2->weight=w;
  168.  p2->nextarc=G.vertices[pos2].firstarc;
  169.  G.vertices[pos2].firstarc=p2;    //将边加入v2的边表头部
  170.  G.arcnum++;         			//边数自增 
  171.  return OK;
  172. }
  173.  
  174. Status ArcDelete(ALGraph &G,VerTexType v1,VerTexType v2){ //删除边
  175.  int pos1,pos2;
  176.  pos1=VexLocate(G,v1);      //存放删除边的第一个顶点位置 
  177.  pos2=VexLocate(G,v2);      //存放删除边的第二个顶点位置 
  178.  ArcNode* p1=G.vertices[pos1].firstarc;  //指向第一个顶点的连接表中
  179.  												//与该顶点相连的边的指针 
  180.  ArcNode* p2=G.vertices[pos2].firstarc;  //指向第二个顶点的连接表中
  181.  												//与该顶点相连的边的指针
  182.  Delete(G,pos1,pos2);      //在第一个顶点连接表中删除第二顶点的信息 
  183.  Delete(G,pos2,pos1);      //在第二个顶点连接表中删除第一顶点的信息
  184.  
  185.  //下半部份代码用Delete()函数进行优化替代 
  186. // if(p1&&p1->adjvex==pos2){
  187. //  G.vertices[pos1].firstarc=p1->nextarc;
  188. //  delete p1;
  189. // }
  190. // else{
  191. //  while(p1!=NULL){
  192. //   if(p1->nextarc!=NULL&&p1->nextarc->adjvex==pos2){
  193. //    ArcNode* temp=p1->nextarc;
  194. //    p1->nextarc=p1->nextarc->nextarc;
  195. //    delete temp;
  196. //    break;
  197. //   }
  198. //   p1=p1->nextarc;
  199. //  }
  200. // }
  201. // if(p2&&p2->adjvex==pos1){
  202. //  G.vertices[pos2].firstarc=p2->nextarc;
  203. //  delete p2;
  204. // }
  205. // else{
  206. //  while(p2!=NULL){
  207. //   if(p2->nextarc!=NULL&&p2->nextarc->adjvex==pos1){
  208. //    ArcNode* temp=p2->nextarc;
  209. //    p2->nextarc=p2->nextarc->nextarc;
  210. //    delete temp;
  211. //    break;
  212. //   }
  213. //   p2=p2->nextarc;
  214. //  }
  215. // }
  216.  G.arcnum--;				//边数自减
  217.  return OK;
  218. }
  219.  
  220.  
  221.  
  222. int main(){
  223.  ALGraph G;
  224.  UDGCreate(G);         	//构建图 
  225.  ALGraphprint(G);         //打印图 
  226.  VerTexType v1,v2;
  227.  int w;
  228.  cout<<"请输入要插入的顶点：";
  229.  cin>>v1;
  230.  VexInsert(G,v1);        //插入顶点 
  231.  ALGraphprint(G);
  232.  cout<<"请输入要删除的顶点：";
  233.  cin>>v1;
  234.  VexDelete(G,v1);        //删除顶点 
  235.  ALGraphprint(G);
  236.  cout<<"请输入要插入边的两顶点及边权重：";
  237.  cin>>v1>>v2>>w;
  238.  ArcInsert(G,v1,v2,w);   //插入边 
  239.  ALGraphprint(G);
  240.  cout<<"请输入要删除边的两顶点：";
  241.  cin>>v1>>v2;
  242.  ArcDelete(G,v1,v2);     //删除边 
  243.  ALGraphprint(G);
  244.  return 0;
  245. }

四、结果展示

1、邻接矩阵结果：

 2、邻接表结果：

 五、算法时间复杂度

        1、邻接矩阵实现图的基本操作，函数包括：邻接矩阵创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接矩阵打印。其中操作建立于二维数组，与数据规模有关，设总顶点数与总边数数据规模为n，则总体算法时间复杂度为O(n2)。

        2、邻接表实现图的基本操作，主要通过数组+链表方式进行数据处理。函数包括：邻接表创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接表打印。其中操作主要建立于链表上，与数据规模有关，设总顶点数与总边数数据规模为n，则总体算法时间复杂为O(n)。

PS：第一次写博客，有问题欢迎交流。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/984740
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号