有向图的概念和java代码实现

水深无声 2023-09-23 20:36 114阅读 0赞

# 有向图定义 #

> 有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。

> **出度：**  
> 由某个顶点指出的边的个数称为该顶点的出度。  
> **入度：**  
> 指向某个顶点的边的个数称为该顶点的入度。  
> **有向路径：**  
> 由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。  
> **有向环：**  
> 一条至少含有一条边，且起点和终点相同的有向路径。  
> ![在这里插入图片描述][cf52abf9fe014e19ace27ab7b29cbe95.png]  
> 一副有向图中两个顶点v和w可能存在以下四种关系：
> 
> 1.  没有边相连；
> 2.  存在从v到w的边v—>w;
> 3.  存在从w到v的边w—>v;
> 4.  既存在w到v的边，也存在v到w的边，即双向连接；  
>     ![在这里插入图片描述][7e9ad609e4ee4aaab431436a3c1f6868.png]

# 有向图API设计 #

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>Digraph</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td>Digraph(int V)：创建一个包含V个顶点但不包含边的有向图</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.public int V():获取图中顶点的数量<br>2.public int E():获取图中边的数量<br>3.public void addEdge(int v,int w):向有向图中添加一条边 v-&gt;w<br>4.public Queue adj(int v)：获取由v指出的边所连接的所有顶点<br>5.private Digraph reverse():该图的反向图</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>

# 有向图代码实现 #

public class Digraph {
        
        private final int V; //顶点数目
        private  int E; //边的数目
        private Queue<Integer>[] adj; //邻接表
        public Digraph(int V){
        
            this.V = V; //初始化顶点数量
            this.E= E; //初始化边的数量
            this.adj = new Queue[V];//初始化邻接表
            for (int i = 0; i < adj.length; i++) {
        //初始化邻接表中的空队列
                adj[i]=new Queue<Integer>();
    
            }
        }
        public int V(){
         //获取顶点数目
            return V;
        }
        public int E(){
        //获取边的数目
            return E;
    
        }
        public void addEdge(int v,int w){
         //向有向图中添加一条边 v->w
            adj[v].enqueue(w); //由于有向图中边是有向的，v->w 边，只需要让w出现在v的邻接表中，而不需要让v出现在w的邻接表中
            E++;//边的数目自增1
        }
        public Queue<Integer>adj(int v){
        //获取由v指出的边所连接的所有顶点
            return adj[v];
        }
        private Digraph reverse(){
         //该图的反向图
            Digraph r = new Digraph(V); //创建新的有向图对象
            for (int v = 0; v < V; v++) {
        //遍历0~V-1所有顶点,拿到每一个顶点v
                for(Integer w:adj(v)){
         //得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;
                    r.addEdge(w,v);
                }
    
    
            }
            return r;
        }
    }

[cf52abf9fe014e19ace27ab7b29cbe95.png]: https://img-blog.csdnimg.cn/cf52abf9fe014e19ace27ab7b29cbe95.png
[7e9ad609e4ee4aaab431436a3c1f6868.png]: https://img-blog.csdnimg.cn/7e9ad609e4ee4aaab431436a3c1f6868.png