Java數(shù)據(jù)結(jié)構(gòu)之有向圖設(shè)計(jì)與實(shí)現(xiàn)詳解

第Java數(shù)據(jù)結(jié)構(gòu)之有向圖設(shè)計(jì)與實(shí)現(xiàn)詳解目錄前言定義及相關(guān)術(shù)語API設(shè)計(jì)代碼實(shí)現(xiàn)

前言

在實(shí)際生活中，很多應(yīng)用相關(guān)的圖都是有方向性的，最直觀的就是網(wǎng)絡(luò)，可以從A頁面通過鏈接跳轉(zhuǎn)到B頁面，那么a和b連接的方向是a-b,但不能說是b-a,此時(shí)我們就需要使用有向圖來解決這一類問題，它和我們之前學(xué)習(xí)的無向圖，最大的區(qū)別就在于連接是具有方向的，在代碼的處理上也會(huì)有很大的不同。

定義及相關(guān)術(shù)語

定義：

有向圖是一副具有方向性的圖，是由一組頂點(diǎn)和一組有方向的邊組成的，每條方向的邊都連著一對(duì)有序的頂點(diǎn)。

出度：

由某個(gè)頂點(diǎn)指出的邊的個(gè)數(shù)稱為該頂點(diǎn)的出度。

入度：

指向某個(gè)頂點(diǎn)的邊的個(gè)數(shù)稱為該頂點(diǎn)的入度。

有向路徑：

由一系列頂點(diǎn)組成，對(duì)于其中的每個(gè)頂點(diǎn)都存在一條有向邊，從它指向序列中的下一個(gè)頂點(diǎn)。

有向環(huán)：

一條至少含有一條邊，且起點(diǎn)和終點(diǎn)相同的有向路徑。

一副有向圖中兩個(gè)頂點(diǎn)v和w可能存在以下四種關(guān)系：

沒有邊相連；存在從v到w的邊v存在從w到v的邊w既存在w到v的邊，也存在v到w的邊，即雙向連接；

API設(shè)計(jì)

類名Digraph成員變量1.privatefinalintV:記錄頂點(diǎn)數(shù)量2.privateintE:記錄邊數(shù)量3.privateQueue[]adj:鄰接表構(gòu)造方法Digraph(intV)：創(chuàng)建一個(gè)包含V個(gè)頂點(diǎn)但不包含邊的有向圖成員方法1.publicintV():獲取圖中頂點(diǎn)的數(shù)量2.publicintE():獲取圖中邊的數(shù)量3.publicvoidaddEdge(intv,intw):向有向圖中添加一條邊v-w4.publicQueueadj(intv)：獲取由v指出的邊所連接的所有頂點(diǎn)5.privateDigraphreverse():該圖的反向圖

在api中設(shè)計(jì)了一個(gè)反向圖，其因?yàn)橛邢驁D的實(shí)現(xiàn)中，用adj方法獲取出來的是由當(dāng)前頂點(diǎn)v指向的其他頂點(diǎn)，如果

能得到其反向圖，就可以很容易得到指向v的其他頂點(diǎn)。

代碼實(shí)現(xiàn)

/**

*有向圖設(shè)計(jì)

*@authoralvin

*@date2025/11/1

*@since1.0

publicclassDigraph{

//頂點(diǎn)數(shù)目

privatefinalintV;

//邊的數(shù)目

privateintE;

//鄰接表

privateQueueInteger[]adj;

publicDigraph(intV){

//初始化頂點(diǎn)數(shù)量

this.V=V;

//初始化邊的數(shù)量

this.E=0;

//初始化鄰接表

this.adj=newQueue[V];

for(inti=0;iadj.length;i++){

adj[i]=newArrayDeque();

//獲取頂點(diǎn)數(shù)目

publicintV(){

returnV;

//獲取邊的數(shù)目

publicintE(){

returnE;

//向有向圖中添加一條邊v-w

publicvoidaddEdge(intv,intw){

//只需要讓頂點(diǎn)w出現(xiàn)在頂點(diǎn)v的鄰接表中，因?yàn)檫吺怯蟹较虻?，最終，頂點(diǎn)v的鄰接表中存儲(chǔ)的相鄰頂點(diǎn)的含義是：v-其他頂點(diǎn)

adj[v].add(w);

E++;

//獲取由v指出的邊所連接的所有頂點(diǎn)

publicQueueIntegeradj(intv){

returnadj[v];

//該圖的反向圖

privateDigraphreverse(){

//創(chuàng)建有向圖對(duì)象

Digraphr=newDigraph(V);

for(intv=0;vv++){

//獲取由該頂點(diǎn)v指出的