轉(zhuǎn)載自：http://blog.csdn.net/gamer_gyt/article/details/51498546

一：圖的分類

1：無向圖

??????? 即兩個頂點(diǎn)之間沒有明確的指向關(guān)系，只有一條邊相連，例如，A頂點(diǎn)和B頂點(diǎn)之間可以表示為 <A, B> 也可以表示為<B, A>，如下所示

??????????????????????

2：有向圖

??????? 頂點(diǎn)之間是有方向性的，例如A和B頂點(diǎn)之間，A指向了B，B也指向了A，兩者是不同的，如果給邊賦予權(quán)重，那么這種異同便更加顯著了

??????????????????????

=================================================================================================

在次基礎(chǔ)上，根據(jù)圖的連通關(guān)系可以分為

無向完全圖：在無向圖的基礎(chǔ)上，每兩個頂點(diǎn)之間都存在一條邊，一個包含N個頂點(diǎn)的無向完全圖，其總邊數(shù)為N（N-1）/2

有向完全圖：在有向圖的基礎(chǔ)上，每兩個頂點(diǎn)之間都存在一條邊，一個包含N個頂點(diǎn)的有向完全圖，其總邊數(shù)為N（N-1）

連通圖：針對無向圖而言的，如果任意兩個頂點(diǎn)之間是連通的，則該無向圖稱為連通圖

非連通圖：無向圖中，存在兩個頂點(diǎn)之間是不連通的，則該無向圖稱為非連通圖

強(qiáng)連通圖：針對有向圖而言的，如果有向圖中任意兩個頂點(diǎn)之間是連通的（注意方向問題，A—>B，成立，但B—>A不一定成立），則該有向圖稱為強(qiáng)連通圖

非強(qiáng)連通圖：如果有向圖中存在兩個頂點(diǎn)之間是不連通的，則該有向圖稱為非強(qiáng)連通圖

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

1：鄰接矩陣

?????? 使用二維數(shù)組來存儲圖的邊的信息和權(quán)重，如下圖所示的4個頂點(diǎn)的無向圖

???????????????????????????????????????????????

??????? 從上面可以看出，無向圖的邊數(shù)組是一個對稱矩陣。所謂對稱矩陣就是n階矩陣的元滿足a_ij?= a_ji。即從矩陣的左上角到右下角的主對角線為軸，右上角的元和左下角相對應(yīng)的元全都是相等的。

如果換成有向圖，則如圖所示的五個頂點(diǎn)的有向圖的鄰接矩陣表示如下

????????????????????????????????

2：鄰接表

??????? 鄰接矩陣是一種不錯的圖存儲結(jié)構(gòu)，但是對于邊數(shù)相對較少的圖，這種結(jié)構(gòu)存在空間上的極大浪費(fèi)，因此找到一種數(shù)組與鏈表相結(jié)合的存儲方法稱為鄰接表。

鄰接表的處理方法是這樣的：

? ? （1）圖中頂點(diǎn)用一個一維數(shù)組存儲，當(dāng)然，頂點(diǎn)也可以用單鏈表來存儲，不過，數(shù)組可以較容易的讀取頂點(diǎn)的信息，更加方便。

? ? （2）圖中每個頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個線性表，由于鄰接點(diǎn)的個數(shù)不定，所以，用單鏈表存儲，無向圖稱為頂點(diǎn)vi的邊表，有向圖則稱為頂點(diǎn)vi作為弧尾的出邊表

如下為無向圖的鄰接表表示：

從圖中可以看出，頂點(diǎn)表的各個結(jié)點(diǎn)由data和firstedge兩個域表示，data是數(shù)據(jù)域，存儲頂點(diǎn)的信息，firstedge是指針域，指向邊表的第一個結(jié)點(diǎn)，即此頂點(diǎn)的第一個鄰接點(diǎn)。邊表結(jié)點(diǎn)由adjvex和next兩個域組成。adjvex是鄰接點(diǎn)域，存儲某頂點(diǎn)的鄰接點(diǎn)在頂點(diǎn)表中的下標(biāo)，next則存儲指向邊表中下一個結(jié)點(diǎn)的指針。

有向圖的鄰接表表示：

3：十字鏈表

對于鄰接表來說，計算頂點(diǎn)的入度是不方便的，那么有沒有一種存儲方式能夠輕松的計算頂點(diǎn)的入度和出度呢，答案是肯定的

在十字鏈表中重新定義了節(jié)點(diǎn)的結(jié)構(gòu)：

firstin表示入邊表頭指針，指向該頂點(diǎn)的入邊表中第一個結(jié)點(diǎn)，firstout表示出邊表頭指針，指向該頂點(diǎn)的出邊表中的第一個結(jié)點(diǎn)

重新定義的邊表結(jié)構(gòu)為：

??????? 其中，tailvex是指弧起點(diǎn)在頂點(diǎn)表的下表，headvex是指弧終點(diǎn)在頂點(diǎn)表的下標(biāo)，headlink是指入邊表指針域，指向終點(diǎn)相同的下一條邊，taillink是指邊表指針域，指向起點(diǎn)相同的下一條邊。如果是網(wǎng)，還可以增加一個weight域來存儲權(quán)值。

?????? 比如下圖，頂點(diǎn)依然是存入一個一維數(shù)組，實(shí)線箭頭指針的圖示完全與鄰接表相同。就以頂點(diǎn)v₀來說，firstout指向的是出邊表中的第一個結(jié)點(diǎn)v₃。所以，v₀邊表結(jié)點(diǎn)hearvex = 3，而tailvex其實(shí)就是當(dāng)前頂點(diǎn)v₀的下標(biāo)0，由于v₀只有一個出邊頂點(diǎn)，所有headlink和taillink都是空的。

??????? 重點(diǎn)需要解釋虛線箭頭的含義。它其實(shí)就是此圖的逆鄰接表的表示。對于v₀來說，它有兩個頂點(diǎn)v₁和v₂的入邊。因此的firstin指向頂點(diǎn)v1的邊表結(jié)點(diǎn)中headvex為0的結(jié)點(diǎn)，如上圖圓圈1。接著由入邊結(jié)點(diǎn)的headlink指向下一個入邊頂點(diǎn)v₂，如上圖圓圈2。對于頂點(diǎn)v₁，它有一個入邊頂點(diǎn)v₂，所以它的firstin指向頂點(diǎn)v₂的邊表結(jié)點(diǎn)中headvex為1的結(jié)點(diǎn)，如上圖圓圈3。

? ? 十字鏈表的好處就是因?yàn)榘燕徑颖砗湍驵徑颖碚显谝黄?#xff0c;這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而比較容易求得頂點(diǎn)的出度和入度。

? ? 而且除了結(jié)構(gòu)復(fù)雜一點(diǎn)外，其實(shí)創(chuàng)建圖算法的時間復(fù)雜度是和鄰接表相同的，因此，在有向圖應(yīng)用中，十字鏈表是非常好的數(shù)據(jù)結(jié)構(gòu)模型。

? ? 這里就介紹以上三種存儲結(jié)構(gòu)，除了第三種存儲結(jié)構(gòu)外，其他的兩種存儲結(jié)構(gòu)比較簡單

三：圖的遍歷

1：深度優(yōu)先遍歷（DFS）

它從圖中某個結(jié)點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中的所有頂點(diǎn)都被訪問到為止。

基本實(shí)現(xiàn)思想：

（1）訪問頂點(diǎn)v；

（2）從v的未被訪問的鄰接點(diǎn)中選取一個頂點(diǎn)w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷；

（3）重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。

遞歸實(shí)現(xiàn)

（1）訪問頂點(diǎn)v；visited[v]=1；//算法執(zhí)行前visited[n]=0

（2）w=頂點(diǎn)v的第一個鄰接點(diǎn)；

（3）while（w存在）??

???????? ??if（w未被訪問）

?????????????????? 從頂點(diǎn)w出發(fā)遞歸執(zhí)行該算法；?
???????????w=頂點(diǎn)v的下一個鄰接點(diǎn)；

?

非遞歸實(shí)現(xiàn)

?（1）棧S初始化；visited[n]=0；

?（2）訪問頂點(diǎn)v；visited[v]=1；頂點(diǎn)v入棧S

?（3）while(棧S非空)

????????????x=棧S的頂元素(不出棧)；

??????????? if(存在并找到未被訪問的x的鄰接點(diǎn)w)

??????????????????? 訪問w；visited[w]=1；

????????????????????w進(jìn)棧;

??????????? else

?????????????????????x出棧；

2：廣度優(yōu)先遍歷（BFS）

它是一個分層搜索的過程和二叉樹的層次遍歷十分相似，它也需要一個隊列以保持遍歷過的頂點(diǎn)順序，以便按出隊的順序再去訪問這些頂點(diǎn)的鄰接頂點(diǎn)。

基本實(shí)現(xiàn)思想：?

（1）頂點(diǎn)v入隊列。

（2）當(dāng)隊列非空時則繼續(xù)執(zhí)行，否則算法結(jié)束。

（3）出隊列取得隊頭頂點(diǎn)v；訪問頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問。

（4）查找頂點(diǎn)v的第一個鄰接頂點(diǎn)col。

（5）若v的鄰接頂點(diǎn)col未被訪問過的，則col入隊列。

（6）繼續(xù)查找頂點(diǎn)v的另一個新的鄰接頂點(diǎn)col，轉(zhuǎn)到步驟（5）。

??????? 直到頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)處理完。轉(zhuǎn)到步驟（2）。

廣度優(yōu)先遍歷圖是以頂點(diǎn)v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通而且路徑長度為1，2，……的頂點(diǎn)。為了使“先被訪問頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問頂點(diǎn)的鄰接點(diǎn)”被訪問，需設(shè)置隊列存儲訪問的頂點(diǎn)。

偽代碼

（1）初始化隊列Q；visited[n]=0；

（2）訪問頂點(diǎn)v；visited[v]=1；頂點(diǎn)v入隊列Q；

（3） while（隊列Q非空）???

????????????? v=隊列Q的對頭元素出隊；

????????????? w=頂點(diǎn)v的第一個鄰接點(diǎn)；

???????????? while（w存在）?

???????????????????? 如果w未訪問，則訪問頂點(diǎn)w；

???????????????????? visited[w]=1；

???????????????????? 頂點(diǎn)w入隊列Q；

???????????????????? w=頂點(diǎn)v的下一個鄰接點(diǎn)。

四：舉例說明

package com.hbut.test; import java.util.Scanner; /** * Created by HP on 2017/6/4. */ /* * 定義圖的結(jié)構(gòu) */ class Graph {static final int MaxNum=20; //最大節(jié)點(diǎn)數(shù)目 static final int MaxValue=65535; char[] Vertex = new char[MaxNum]; //定義數(shù)組，保存頂點(diǎn)信息 int GType; //圖的類型0：無向圖 1：有向圖 int VertxNum; //頂點(diǎn)的數(shù)量 int EdgeNum; //邊的數(shù)量 int[][] EdgeWeight = new int[MaxNum][MaxNum]; //定義矩陣保存頂點(diǎn)邊的信息 int[] isTrav = new int[MaxNum]; //遍歷標(biāo)志 }public class GraphTest {/** * @param args * Author：thinkgamer */ static Scanner scan = new Scanner(System.in); //創(chuàng)建鄰接矩陣圖 static void createGraph(Graph g){int i , j , k; int weight; //權(quán) char EstartV, EndV; //邊的起始頂點(diǎn) System.out.println("輸入圖中各頂點(diǎn)的信息"); for(i=0; i < g.VertxNum; i ++){System.out.println("第" + (i+1) + "個頂點(diǎn)"); g.Vertex[i] = (scan.next().toCharArray() )[0]; }System.out.println("輸入構(gòu)成各個邊的頂點(diǎn)和權(quán)值"); for(k=0;k<g.EdgeNum;k++){System.out.println("第" + (k+1) + "條邊："); EstartV = scan.next().charAt(0); //起始點(diǎn) EndV = scan.next().charAt(0); //終點(diǎn) weight = scan.nextInt(); //權(quán)值 for(i=0; EstartV!=g.Vertex[i] ; i++); //在已有頂點(diǎn)中查找開始節(jié)點(diǎn) for(j=0; EndV != g.Vertex[j]; j++); //在已有節(jié)點(diǎn)上查找終結(jié)點(diǎn) g.EdgeWeight[i][j] = weight; //對應(yīng)位置保存權(quán)重，表示有一條邊 if(g.GType == 0) //如果是無向圖，在對角位置保存權(quán)重 g.EdgeWeight[j][i] = weight; }}//清空圖 static void clearGraph(Graph g){int i,j; for(i=0; i< g.VertxNum; i++)for(j =0; j<g.VertxNum; j++)g.EdgeWeight[i][j] = Graph.MaxValue; //設(shè)置矩陣中各元素的值為MaxValue }//輸出鄰接矩陣 static void OutGraph(Graph g){int i,j; System.out.print("圖的頂點(diǎn)信息："); for(j = 0; j < g.VertxNum;j ++)System.out.print("\t" + g.Vertex[j]); //在第一行輸入頂點(diǎn)信息 System.out.println(); for(i =0 ;i <g.VertxNum; i ++){System.out.print( g.Vertex[i]); for(j = 0;j < g.VertxNum; j++){if(g.EdgeWeight[i][j] == Graph.MaxValue) //若權(quán)值為最大值 System.out.print("\tZ"); //Z 表示無窮大 else System.out.print("\t" + g.EdgeWeight[i][j]); //輸出邊的權(quán)重 }System.out.println(); }}//遍歷圖 static void DeepTraOne(Graph g,int n){//從第n個節(jié)點(diǎn)開始遍歷 int i; g.isTrav[n] = 1; //標(biāo)記為1表示該頂點(diǎn)已經(jīng)被處理過 System.out.println("—>" + g.Vertex[n]); //輸出節(jié)點(diǎn)數(shù)據(jù) //遍歷鄰接矩陣中第n個節(jié)點(diǎn)的直接連通關(guān)系 for(i = 0; i< g.VertxNum; i++){if(g.EdgeWeight[n][i] != g.MaxValue && g.isTrav[i] == 0)//目標(biāo)節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)連通，并且該節(jié)點(diǎn)沒有被訪問過 {DeepTraOne(g, i); //遞歸進(jìn)行遍歷 }}}//深度優(yōu)先遍歷 static void DeepTraGraph(Graph g){int i; for(i = 0; i< g.VertxNum; i++){g.isTrav[i]= 0; }System.out.println("深度優(yōu)先遍歷："); // 從沒有被遍歷的節(jié)點(diǎn)開始深度遍歷 for(i = 0; i< g.VertxNum ; i++){if(g.isTrav[i] == 0)DeepTraOne(g,i);// 若是連通圖，只會執(zhí)行一次 }System.out.println(); }public static void main(String[] args) {Graph g = new Graph(); System.out.println("輸出生成圖的類型："); g.GType = scan.nextInt(); //圖的種類 System.out.println("輸入圖的頂點(diǎn)數(shù)量："); g.VertxNum = scan.nextInt(); System.out.println("輸入圖的邊數(shù)量："); g.EdgeNum = scan.nextInt(); clearGraph(g); //清空圖 createGraph(g); //生成鄰接表結(jié)構(gòu)的圖 System.out.println("該圖的鄰接矩陣數(shù)據(jù)如下："); OutGraph(g); //輸出圖 DeepTraGraph(g); //深度優(yōu)先遍歷圖 }}

運(yùn)行測試結(jié)果：

有向圖測試結(jié)果（無向圖類似，只是在輸入生成圖類型時輸入0）

總結(jié)

以上是生活随笔為你收集整理的图的存储以及深度优先以及广度优先遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。