有向网的各种功能实现：

1：在邻接矩阵、邻接表和逆邻接表之间转换。

2：完成增加顶点和删除顶点的功能，删除顶点也要删除与之关联的边；

3：完成增加边和删除边的功能；

4：完成图的深度优先遍历和广度优先遍历；

5：广度优先的生成树并对生成树进行遍历

6：判断图的连通性，输出连通分量的个数；

7：判断图中是否存在环；

8：判断u到v是否存在路径；

9：实现Dijkstra和Floyd算法求最短路径；

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Stack;public class DiNet
    
      {	class Ver
     
      {      //存储顶点		int data;		Arc firstArc;		boolean visit;		boolean known;		Ver path;		int dist;		int inDeg;		public Ver(int data){			this.data=data;			this.firstArc=null;			this.inDeg=0;		}		public Ver(int dist,int data){			this.dist=dist;			this.data=data;		}	}	class Arc
      
       {         //存储邻接点		int adjVex;		Arc nextArc;		int weight;		public Arc(int adjVex,int weight){			this.adjVex=adjVex;			this.nextArc=null;			this.weight=weight;		}			}	class CSNode
       
        {     //孩子兄弟表示法  结点定义		int data;		CSNode firstChild;		CSNode nextSibling;		public CSNode(int data){			this.data=data;			this.firstChild=null;			this.nextSibling=null;		}		public CSNode(){			this.firstChild=null;			this.nextSibling=null;		}	}	Ver vertexts[];	Scanner sc=new Scanner(System.in);	int count=0;    //连通性标志	Ver begin,end;    //判断是否存在环时用到，路径的开始与结尾	boolean flag;//是否存在环的标识符//创建图	public Ver[] creatNet(){		System.out.println("请输入顶点个数");		int verNumber=sc.nextInt();		System.out.println("请输入要创建的网的边数：");		int edgeNumber=sc.nextInt();		System.out.println("请输入各个节点的数据：");		vertexts=new Ver[verNumber];		for(int i=0;i
        
         =0;w=nextArc(v,w)){			if(vertexts[w].visit==false){				DFS(w);					}		}	}	public void DFSTravel(){		for(int i=0;i
         
           q=new LinkedList
          
           (); for(int i=0;i
           
            =0;w=nextArc(v,w)){ //对v的所有邻接点都进行判断是否已访问 if(vertexts[w].visit==false){ System.out.print(vertexts[w].data+" "); vertexts[w].visit=true; q.add(w); } } } } } System.out.println(); }//转换成邻接矩阵 public void matrix(){ int max=999; //初始值为无穷，用一个极大的数代替 int num=vertexts.length; int m[][]=new int[num][num]; //初始化数组，值均为max for(int i=0;i
            
             =vertexts.length) System.out.println("要删除的顶点不存在"); else{ for(int i=0;i
             
              n){ //邻接点的数据大于n，则减1 p.adjVex--; } p=p.nextArc; } } System.out.println("删除成功！！！"); } } //增加边 public void addEdge(){ System.out.println("请输入要增加边"); int v=sc.nextInt(); //弧尾 int w=sc.nextInt(); //弧头 System.out.println("请输入要增加边的权"); int we=sc.nextInt(); Arc p=new Arc(w,we); p.nextArc=vertexts[v].firstArc; vertexts[v].firstArc=p; System.out.println("添加成功！！！"); }//删除边 public void deleteEdge(){ System.out.println("请输入要删除的边"); int v=sc.nextInt(); int w=sc.nextInt(); deleteEdge(v,w); System.out.println("删除成功！！！"); } public void deleteEdge(int v,int w){ Arc p=vertexts[v].firstArc; if(p.adjVex==w){ //是第一个邻接点 vertexts[v].firstArc=p.nextArc; } else{ //不是第一个邻接点 while(p.nextArc.adjVex!=w&&p.nextArc!=null){ p=p.nextArc; } p.nextArc=p.nextArc.nextArc; } }//判断是否为连通图 public void isLianTong(){ DFSTravel(); if(count==1) System.out.println("该图为连通图"); else System.out.println("该图不是连通图,连通分量个数为："+count); count=0; }//广度优先生成树 public CSNode BFSTree(){ int w; int n=0; //判断是否已近存在一个根 CSNode rootNode=null; Queue
              
                q=new LinkedList
               
                (); for(int i=0;i
                
                 =0;w=nextArc(v,w)){ if(vertexts[w].visit==false){ if(node.firstChild==null) //第一个孩子 node.firstChild=new CSNode(vertexts[w].data); else{ //第一个孩子的兄弟 CSNode p=node.firstChild; while(p.nextSibling!=null){ p=p.nextSibling; } p.nextSibling=new CSNode(vertexts[w].data); } vertexts[w].visit=true; q.add(w); } } } n++; } } return rootNode; }//层次非递归遍历 public void levelOrder(CSNode root){ int i=0; Queue
                 
                   q=new LinkedList
                  
                   (); q.add(root); while(q.isEmpty()!=true){ CSNode step=q.remove(); System.out.print(step.data); if(step.firstChild!=null){ q.add(step.firstChild); } if(step.nextSibling!=null){ q.add(step.nextSibling); } } System.out.println(); }//判断是否存在环 拓扑排序 public void topSort(){ boolean flag=true; //是否存在环的标志符 Queue
                   
                     q=new LinkedList
                    
                     (); for(int i=0;i
                     
                      =0;w=nextArc(v,w)){ vertexts[w].inDeg--; //与v相邻点的入度减1 if(vertexts[w].inDeg==0){ q.add(w); } } } for(int i=0;i
                      
                       0){ flag=false; break; } } if(flag==false) System.out.println("存在环"); else System.out.println("不存在环"); }//Dijkstra算法 public Ver Dijkstra(){ System.out.println("请输入起始点"); int s=sc.nextInt(); System.out.println("请输入起终点"); int e=sc.nextInt(); for(int i=0;i
                       
                        (v.dist+w.weight)&&vertexts[w.adjVex].known==false){ //w.dist与v.dist+w.weight 比较，确定w.dist vertexts[w.adjVex].dist=v.dist+w.weight; vertexts[w.adjVex].path=v; } w=w.nextArc; } } return vertexts[e]; } public void printpath(Ver v){ if(v.path!=null){ printpath(v.path); System.out.print("to"); } System.out.print(v.data); }//Floyd算法 //核心 public int[][] floyd(){ int num=vertexts.length; int d[][]=new int[num][num]; int e[][]=new int[num][num]; //存放最短路径 int max=999; //定义n阶矩阵D,存储初始两个顶点之间的距离 for(int i=0;i
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

 

 

版权声明：本文为博主原创文章，未经博主允许不得转载。