當(dāng)前位置：首頁 > 编程语言 > java >内容正文

java

Java数据结构和算法：图

發(fā)布時間：2025/4/16 java 20 豆豆

生活随笔收集整理的這篇文章主要介紹了 Java数据结构和算法：图小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

圖的基本概念

1. 圖的定義

定義：圖(graph)是由一些點(vertex)和這些點之間的連線(edge)所組成的；其中，點通常被成為”頂點(vertex)”，而點與點之間的連線則被成為”邊或弧”(edege)。通常記為，G=(V,E)。

2. 圖的種類

根據(jù)邊是否有方向，將圖可以劃分為：無向圖和有向圖。

2.1 無向圖

上面的圖G0是無向圖，無向圖的所有的邊都是不區(qū)分方向的。G0=(V1,{E1})。其中，

(01) V1={A,B,C,D,E,F}。 V1表示由”A,B,C,D,E,F”幾個頂點組成的集合。
(02) E1={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), (C,D),(E,F),(C,E)}。 E1是由邊(A,B),邊(A,C)…等等組成的集合。其中，(A,C)表示由頂點A和頂點C連接成的邊。

2.2 有向圖

上面的圖G2是有向圖。和無向圖不同，有向圖的所有的邊都是有方向的！ G2=(V2,{A2})。其中，

(01) V2={A,C,B,F,D,E,G}。 V2表示由”A,B,C,D,E,F,G”幾個頂點組成的集合。
(02) A2={

3. 鄰接點和度

3.1 鄰接點

一條邊上的兩個頂點叫做鄰接點。
例如，上面無向圖G0中的頂點A和頂點C就是鄰接點。

在有向圖中，除了鄰接點之外；還有”入邊”和”出邊”的概念。
頂點的入邊，是指以該頂點為終點的邊。而頂點的出邊，則是指以該頂點為起點的邊。
例如，上面有向圖G2中的B和E是鄰接點；

3.2 度

在無向圖中，某個頂點的度是鄰接到該頂點的邊(或弧)的數(shù)目。
例如，上面無向圖G0中頂點A的度是2。

在有向圖中，度還有”入度”和”出度”之分。
某個頂點的入度，是指以該頂點為終點的邊的數(shù)目。而頂點的出度，則是指以該頂點為起點的邊的數(shù)目。
頂點的度=入度+出度。
例如，上面有向圖G2中，頂點B的入度是2，出度是3；頂點B的度=2+3=5。

4. 路徑和回路

路徑：如果頂點(Vm)到頂點(Vn)之間存在一個頂點序列。則表示Vm到Vn是一條路徑。
路徑長度：路徑中”邊的數(shù)量”。
簡單路徑：若一條路徑上頂點不重復(fù)出現(xiàn)，則是簡單路徑。
回路：若路徑的第一個頂點和最后一個頂點相同，則是回路。
簡單回路：第一個頂點和最后一個頂點相同，其它各頂點都不重復(fù)的回路則是簡單回路。

5. 連通圖和連通分量

連通圖：對無向圖而言，任意兩個頂點之間都存在一條無向路徑，則稱該無向圖為連通圖。對有向圖而言，若圖中任意兩個頂點之間都存在一條有向路徑，則稱該有向圖為強(qiáng)連通圖。

連通分量：非連通圖中的各個連通子圖稱為該圖的連通分量。

6. 權(quán)

在學(xué)習(xí)”哈夫曼樹”的時候，了解過”權(quán)”的概念。圖中權(quán)的概念與此類似。

上面就是一個帶權(quán)的圖。

圖的存儲結(jié)構(gòu)

上面了解了”圖的基本概念”，下面開始介紹圖的存儲結(jié)構(gòu)。圖的存儲結(jié)構(gòu)，常用的是”鄰接矩陣”和”鄰接表”。

1. 鄰接矩陣

鄰接矩陣是指用矩陣來表示圖。它是采用矩陣來描述圖中頂點之間的關(guān)系(及弧或邊的權(quán))。
假設(shè)圖中頂點數(shù)為n，則鄰接矩陣定義為：

下面通過示意圖來進(jìn)行解釋。

圖中的G1是無向圖和它對應(yīng)的鄰接矩陣。

圖中的G2是無向圖和它對應(yīng)的鄰接矩陣。

通常采用兩個數(shù)組來實現(xiàn)鄰接矩陣：一個一維數(shù)組用來保存頂點信息，一個二維數(shù)組來用保存邊的信息。
鄰接矩陣的缺點就是比較耗費空間。

2. 鄰接表

鄰接表是圖的一種鏈?zhǔn)酱鎯Ρ硎痉椒āＫ歉倪M(jìn)后的”鄰接矩陣”，它的缺點是不方便判斷兩個頂點之間是否有邊，但是相對鄰接矩陣來說更省空間。