加权有向图的java代码实现

阳光穿透心脏的1/2处 2023-09-23 20:56 124阅读 0赞

# 1.加权有向图的边表示 #

## 1.1 API设计 ##

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>DirectedEdge</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td>DirectedEdge(int v,int w,double weight)：通过顶点v和w，以及权重weight值构造一个边对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.public double weight():获取边的权重值<br>2.public int from():获取有向边的起点<br>3.public int to():获取有向边的终点</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private final int v：起点<br>2.private final int w：终点<br>3.private final double weight：当前边的权重</td> 
  </tr> 
 </tbody> 
</table>

## 1.2 代码实现方法 ##

public class DirectedEdge{
        
    	private final int v;//起点
    	private final int w;/终点
    	private final double weight;//当前边的权重
    	//通过顶点v和w，以及权重weight值构造一个边对象
    	public DirectedEdge(int v,int w, double weight){
        
    		this.v =v;
    		this.w =w;
    		this.weight = weight;
    	}
    	publiv double weight(){
        //获取边的权重值
    		return weight;
    	}
    	public int from(){
        //获取有向边的起点
    		return v
    	}
    	public int to()	{
        //获取有向边的终点
    		return w;
    	}
    }

# 2.加权有向图的代码实现 #

## 2.1 API设计 ##

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>EdgeWeightedDigraph</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td>EdgeWeightedDigraph(int V)：创建一个含有V个顶点的空加权有向图</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.public int V():获取图中顶点的数量<br>2.public int E():获取图中边的数量<br>3.public void addEdge(DirectedEdge e):向加权有向图中添加一条边e<br> 4.public Queue adj(int v)：获取由顶点v指出的所有的边<br>5.public Queue edges()：获取加权有向图的所有边</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private final int V: 记录顶点数量<br>2.private int E: 记录边数量<br>3.private Queue[] adj: 邻接表</td> 
  </tr> 
 </tbody> 
</table>

## 2.2 代码实现 ##

public class EdgeWeightedDigraph {
        
    	//顶点总数
    	private final int V;
    	//边的总数
    	private int E;
    	//邻接表
    	private Queue<DirectedEdge>[] adj;
    	//创建一个含有V个顶点的空加权有向图
    	public EdgeWeightedDigraph(int V) {
        
    		//初始化顶点数量
    		this.V = V;
    		//初始化边的数量
    		this.E = 0;
    		//初始化邻接表
    		this.adj = new Queue[V];
    		//初始化邻接表中的空队列
    		for (int i = 0; i < adj.length; i++) {
        
    			adj[i] = new Queue<DirectedEdge>();
    		}
    	}
    	//获取图中顶点的数量
    	public int V() {
        
    		return V;
    	}
    	//获取图中边的数量
    	public int E() {
        
    		return E;
    	}
    	//向加权有向图中添加一条边e
    	public void addEdge(DirectedEdge e) {
        
    		//获取有向边的起点
    		int v = e.from();
    		//因为是有向图，所以边e只需要出现在起点v的邻接表中
    		adj[v].enqueue(e);
    		//边的数量+1
    		E++;
    	}
    	//获取由顶点v指出的所有的边
    	public Queue<DirectedEdge> adj(int v) {
        
    		return adj[v];
    	}
    	//获取加权有向图的所有边
    	public Queue<DirectedEdge> edges() {
        
    		//创建一个队列，存储所有的边
    		Queue<DirectedEdge> allEdge = new Queue<>();
    		//遍历顶点，拿到每个顶点的邻接表
    		for (int v = 0; v < this.V; v++) {
        
    		//遍历邻接表，拿到邻接表中的每条边存储到队列中
    		for (DirectedEdge e : adj(v)) {
        
    			allEdge.enqueue(e);
    		}
    	}
    		return allEdge;
    	}
    }