数据结构之图的邻接表的实现

迷南。 2023-05-28 09:48 8阅读 0赞

1.邻接表的存储方式  
（1）是一种顺序存储和链式存储相结合和存储方法  
（2）顺序存储用来保存顶点的信息  
（3）链式存储用来保存图中边或弧的信息  
（4）使用一个一维数组，其中的每一个元素都包含两个域：顶点域（data），和头指针域（firstadj）  
（5）邻接表中每一个结点都依附在该顶点的一条边上，称为边结点  
（6）边结点包含三个域，邻接点域（adjvex，对应着一维数组的索引号），数据域（inof，存储权值），链域（nextadj，指向于依附于该顶点的下一个边结点）  
2.添加顶点

public boolean addVex(E v) {
        
    	//判断数组是否满了
    	if(numOfVexs>=maxNumOfVexs) {
        
    		return false;
    	}
    	//定义一个顶点
    	VNode<E> vex = new VNode<E>();
    	//将添加的元素赋值给顶点vex的data域
    	vex.data=v;
    	//将顶点vex存放进一维数组中，且顶点数量加1
    	vexs[numOfVexs++]=vex;
    	return true;
    }

3.删除顶点

public boolean deleteVex(E v) {
        
    	//遍历数组
    	for(int i=0;i<numOfVexs;i++) {
        
    		//判断数组中的顶点是否与参数相同
    		if(vexs[i].data.equals(v)) {
        
    			//如果相同则将该顶点前面的顶点向前移动一步
    			for(int j=i;j<numOfVexs-1;j++) {
        
    				vexs[j]=vexs[j+1];
    			}
    			//将数组最后一位元素赋值为空
    			vexs[numOfVexs-1]=null;
    			//数组元素个数减1
    			numOfVexs--;
    			//创建指针current和previous
    			ENode current;
    			ENode previous;
    			//遍历数组
    			for(int j=0;j<numOfVexs;j++) {
        
    				//判断数组元素vexs[j]的头指针是否为空，如果为空则跳出此次循环
    				if(vexs[j].firstadj==null)
    					continue;
    				//如果数组元素vexs[j]（顶点）的边结点的索引号等于要删除的顶点的索引号，则将顶点vexs[j]的头指针指向下下个边结点
    				if(vexs[j].firstadj.adjvex==i) {
        
    					vexs[j].firstadj=vexs[j].firstadj.nextadj;
    					continue;
    				}
    				//将指针curret指向该数组元素（顶点）的指针域
    				current = vexs[j].firsadj;
    				//如果current不为空，则将previous指针指向current，current指向下一个边结点
    				while(current!=null) {
        
    					previous=current;
    					current=current.nextadj;
    					//如果current不为空，且该结点的存放的一维数组索引号与要删除的顶点的索引号相同，则将previous的下一个节点的地址赋值给current的下一个节点的地址
    					if(current!=null&&current.adjvex==i) {
        
    						previous.nextadj=current.nextadj;
    						break;
    					}
    				}
    			}
    			//遍历数组
    			for(int j=0;j<numOfVexs;j++) {
        
    				//将指针current依次赋值为数组元素的头指针
    				current=vexs[j].firstadj;
    				//如果current不为空，且各个结点对应的一维数组的索引比要删除顶点的索引号大，则结点对应的索引号减1，current指向下一个节点
    				while(current!=null) {
        
    					if(current.adjvex>i) {
        
    						current.adjvex--;
    						current=current.nextadj;
    					}
    				}
    			}
    		}
    	}
    	return false;
    }

4.定位顶点的位置

public int indexOfvex(E v) {
        
    	   //遍历数组
    	   for(int i=0;i<numOfVexs;i++) {
        
    		   //如果数组元素与参数相同，则返回该元素对应的索引号
    		   if(vexs[i].data.equals(v))
    			   return i;
    	   }
    	   return -1;
       }

5.定位指定位置的顶点

public int valueOfVex(int v) {
        
    	  //判断参数是否在范围内
    	 if(v<0||v>=maxNumOfVexs]) {
        
    		 return null;
    	 }
    	 //如果在，直接返回该索引号的元素
    	 return vexs[v];
    	  
      }

6.添加边

public boolean addEdge(int v1,int v2,int weight) {
        
    	  //判断参数是否在范围内，如果不在，则抛出异常
    	  if(v1<0||v2<0||v1>=numOfVexs||v2>=numOfVexs) {
        
    		  throw new ArrayInderOutOfBoundsException();
    	  }
    	  //创建一个索引号为v2，权值为weight的结点vex1，
    	  ENode vex1 = new ENode(v2,weight);
    	  //判断以v1为索引号的元素的头指针是否为空，为空，则直接将结点vex1的的值赋值给该头结点
    	  if(vexs[v1].firstadj==null) {
        
    		
    		  vexs[v1].firstadj=vex1;
    	  }
    	  //否则，将元素vexs[v1]的头结点vex1结点的下一个结点地址
    	  else
    	  {
        
    		  vex1.nextadj=vexs[v1].firstadj;
    		  vexs[v1].firstadj=vex1;
    	  }
    	  //创建以v1为索引号，权值为weight的结点vex2
    	  ENode vex2= new ENode(v1,weight);
    	  //如果数组元素vexs[v2]的头指针为空，则直接将vex2的地址赋值给该元素，否则，将结点vex2的链域指向该元素的头结点，将该头结点指向该节点的地址
    	  if(vexs[v2].firstadj==null) {
        
    		  vexs[v2].firstadj=vex2;
    	  }else
    	  {
        
    		  vex2.nextadj=vexs[v2].firstadj;
    		  vexs[v2].firstadj=vex2;
    	  }
    	  return true;
      }

7.删除边

public boolean deleteEdge(int v1,int v2) {
        
    	  //判断参数是否在范围内
    	  if(v1<0||v2<0||v1>=numOfVexs||v2>=numOfVexs) {
        
    		  throw new ArrayIndexOutOfBoundsException();
    	  }
    	  //创建指针current赋值为vexs[v1]顶点的头指针
    	  ENode  current = vexs[v1].firstadj;
    	  //创建指针previous赋值为null
    	  ENode previous =null;
    	  //判断current是否为空，current结点的索引号是否等于v2，如果不是，则将previous和current结点都往下一个结点移动
    	  while(current!=null&&current.adjvex!=v2) {
        
    		  previous=current;
    		  current=current.nextadj;
    	  }
    	  //如果current不为空，且previous为空，则直接将current结点的链域赋值给vexs[v1]顶点的头指针
    	  if(current!=null&&prevous==null)
    	  {
          
    		  vexs[v1].firstadj=current.nextadj;
    	  }
    	  //否则，直接将current的链域赋值给previous的链域
    	  else
    	  {
        
    		  previous.nextadj=current.nextadj;
    	  }
    	  //使指针current指向下一个元素的头指针
    	  current=vexs[v2].firstadj;
    	  //previous赋值为空
    	  previous=null;
    	  //和上面的步骤一样
    	  while(current!=null&&current.adjvex!=v1) {
        
    		  previous=current;
    		  current=current.nextadj;
    	  }
    	  if(current!=null&&privous==null) {
        
    		  vexs[v2].firstadj=current.nextadj;
    	  }else
    	  {
        
    		  previous.nextadj=current.nextadj;
    	  }
      }

8.查找边

public int getEdge(int v1,int v2) {
        
    	  //判断参数是否在范围内
    	  if(v1<0||v2<0||v1>=numOfVexs||v2>=numOfVexs) {
        
    		  throw new ArrayInderOutOfBoundsException();
    	  }
    	  //创建一个指针current指向vexs[v1]的头指针
    	  ENode current=vexs[v1].firstadj;
    	  //如果current不为空，且，current的链域的v2，则返回该节点的权值，否则再往下找结点
    	  while(current!=null) {
        
    		  if(current.adjvex==v2) {
        
    			  return current.weight;
    		  }
    		  current=current.nextadj;
    	  }
    	  return 0;
      }

9.获得顶点数

public int getNumOfVertex() {
        
    	  return numOfVexs;
      }

10.获得边数

public int getNumOfEdge() {
        
    	  //创建一个整型变量count赋值为0
    	  int count = 0;
    	  //创建一个current指针，赋值为空
    	  ENode current=null;
    	  //遍历数组，指针current不为空则count自增1，且current指向下一个结点
    	  for(int i=0;i<numOfVexs;i++) {
        
    		  current=vexs[i].firstadj;
    		  while(current!=null) {
        
    			  count++;
    			  current=current.nextadj;
    		  }
    	  }
    	  //每一条边都有两个结点，所以边的数目是二分之一count
    	  return count/2;
      }