- 可以說這一篇文章是我開部落格一來最難總結的一篇,畫圖學習,而且還有一些内容并沒有涉及到:比如最小生成樹和最短距離等問題.本文主要是概括的說一下圖的概念,以及圖的周遊方式,對于其他内容以後會陸續更新的,如果本文對你有些許幫助請幫忙點個贊支援一下哈~
- 圖是一種非線性結構,在實際生活中,有很多可以形象比喻的例子:比如人之間的關系圖.地鐵圖等,下面就是一個人際關系圖
- 之前學過的連結清單是一對一關系,樹是一對多關系,那麼圖就是多對多的關系,即圖中的每個元素之間可以任意相關聯,這樣就構成了一個圖結構
基本概念
- 頂點Vertex:圖中的ABC...都是一個頂點
- 邊Edge:圖中連接配接這些頂點的線
- 所有的頂點構成一個頂點集合,所有的邊構成邊集合,一個完整的圖結構由頂點集合和邊結合組成,用數學記為
G = (V , E) 或 G = (V(G) , E(G))
- 其中V(G)表示圖中所有頂點的集合,E(G)是圖中所有邊的集合,每條邊由所連接配接的兩個頂點表示
- 需要注意的是圖中可以沒有邊,但是必須保證有一個頂點,即E(G)可以為空,而(V(G))不可以
- 對于上面的圖應該這樣表示
V(G)頂點={VA,VB,VC,VD,VE,VF,VG} E(G)邊={(VA,VC),(VC,VD),(VD,VE),(VE,VG),(VG,VF),(VF,VB),(VA,VF),(VA,VB),(VB,VG),(VB,VD)} - 無向圖:就是上面這種,邊并沒有方向,但是需要注意的是,在表示的時候E=(VA,VB)和E=(VB,VA)隻能有一個,在無向圖中,正反和反正視為一條邊
- 有向圖:,如下圖,即圖中的邊都是有方向的,那麼這種圖就是有向圖,既然邊有了方向,是以在表示邊集合E的時候,就需要按照邊的指向來表示
- 上面有向圖的表示方式
V(G)頂點={VA,VB,VC,VD,VE,VF,VG} E(G)邊={<VC,VA>,<VD,VC>,<VB,VC>,<VB,VD>,<VB,VF>,<VA,VB>,<VF,VA>,<VF,VG>,<VG,VE>,<VE,VD>,<VE,VB>,<VG,VB>} - 邊E的表示方向不能錯誤,,是不同的兩條邊
- 注意無向圖的邊的表示是用
()
<>
- 頂點的度:連接配接頂點的邊的數量就是該頂點的度,對于無向圖來說,有幾條邊連到該節點,該節點的度就是多少,比如C頂點的度為2,B頂點的度為4.而對于有向圖來說,分為入度和出度
- 入度,就是幾個邊指向該頂點,比如B的入度是3,即為ID
- 出度,就是該頂點有幾個邊指向外面,比如B的出度是2,即為OD
- 是以有向圖的頂點的總度就是該節點的出度+入度之和,比如B的總度就是3+2=5,即D(V)= ID(V)+OD(V)
- 鄰接頂點:即一條邊的兩端頂點,比如無向圖中A與B通過邊相連,那麼A就是B的鄰接頂點,B也是A的鄰接頂點,A也是C和F的鄰接頂點
- 而對于有向圖來說,又要分為入邊鄰接頂點和出邊鄰接頂點
- 入邊鄰接頂點:連接配接該頂點的邊中的起始頂點,即該起始節點就為該頂點的入邊鄰接頂點,比如,B連接配接到F,邊方向指向F,是以B是這條邊的起始頂點,即B是F的入邊鄰接頂點
- 出邊鄰接頂點:連接配接該頂點的邊中的結束頂點,即結束節點就是該節點的出邊鄰接節點,比如,E連到B,方向指向B,是以B是結束節點,即B是E的出邊鄰接節點
- 無向完全圖:即在一個霧像圖中,每兩個頂點之間都存在一條邊,邊數計算公式是(N(N-1)/2),N為頂點數
- 有向完全圖:在一個有向圖中,每兩個頂點之間都存在反向相反的兩條邊,邊數計算公式是N(N-1),N為頂點數
- 從上面的圖也可以看到有向完全圖的邊是無向完全圖邊數的兩倍
- 子圖:概念類似子集合,由于一個完整的圖包含頂點和邊,是以,一個子圖的頂點和邊都應該是圖結構的子集合
- 如上右邊四個被框起來的,都是左邊無向圖的子圖
- 路徑:就是兩個頂點之間的連線,連接配接兩個頂點的路徑不止一條,比如上圖中,VA到VG,可以有VA-VB-VG,VA-VF-VG等等方案,經過的連線數為此路徑的路徑長度,前面列舉的方案的路徑長度都是2
- 圖結構中的路徑還可以細分為三種形式
- 簡單路徑:即如果一條路徑上頂點不重複出現,則稱為簡單路徑,如下
- 環:如果路徑的第一個頂點和最後一個頂點相同,即首尾相連了,則稱為環或者回路,如下
- 簡單回路:如果除第一個頂點和最後一個頂點相同,其餘各項頂點都不重複的回路為簡單回路,應該就是上圖這種情況
- 連通,連通圖,連通分量
- 如果圖結構中兩個頂點之間有路徑,則稱這兩個頂點是連通的,這裡需要注意連通的兩個頂點可以不是鄰接頂點,隻要有路徑連接配接即可,可以有經過很多頂點
- 如果無向圖中任意兩個頂點都是連通的,那麼這個圖就可以成為連通圖,如果無向圖中包含兩個頂點是不連通的,那麼這個圖就稱為非連通圖
- 無向圖的極大連通子圖稱為該圖的連通分量
- 對于一個連通圖,其連通分量就有一個,即此連通圖是不可拆分的,如果是一個非連通圖,則有可能存在多個連通分量
- 強連通圖和強連通分量
- 這是對于有向圖來說的
- 如果兩個頂點之間有路徑,也稱為這兩個頂點是連通的,但是需要注意邊的方向,方向不對即不連通
- 如果有向圖中任意兩個頂點都是連通的,則稱為該圖為強連通圖,如果不是那麼就是非強連通圖
- 有向圖的極大強聯通子圖稱為該圖的強連通分量
- 如無向圖一緻,當有向圖是強連通圖時,這個強連通圖是不可拆分的,否則就可以拆分為強連通分量
- 權:即各個邊上的值,之前我們圖中邊都是空的,我們可以将它指派作為邊的權,這個權在生活中可以想象成地鐵圖之間的距離,比如
- 網:邊帶有權值就可以成為網
- 了解完一些基本概念了,那麼我們就來看一下圖到底怎麼去存
鄰接矩陣法
- 先看無向圖
- 采用結構數組的形式來單獨儲存頂點資訊,然後采用二維數組的形式儲存頂點之間的關系,這種儲存頂點之間關系的數組稱為鄰接矩陣(當我畫完圖,我咋感覺儲存頂點的數組并沒有什麼用呢?如果我了解的不對,請指正)
- 為什麼會出現對稱現象:比如V1和V2吧,由于是無向圖,V1和V2公用一個邊,即(V1,V2),是以就會儲存兩次這個邊,即int1和int2,在上圖中下标我都是減一處理的.
- 那麼怎麼知道某頂點的度呢?由于無向圖存儲數組是對稱的,是以我們取頂點對應的行或者列相加即可,比如頂點3的度是4,那麼圖中我們可以取頂點3對應的行,即下标為2的行或者下标為2的列相加即可1+1+1+1=4
- 怎麼知道哪些頂點與該頂點是鄰接節點呢?比如3的鄰接節點為1,2,4,5,我們直接掃描頂點對應的行或者列也就可以了,比如掃描第三行,即下标為2的行,我們掃描得到在列為0,1,3,4的位置上是1,那麼就可以知道有哪些鄰接節點了
- 這樣存放雖然友善,但是這樣看就會有很多的空間存放重複的元素了,因為無向圖是對稱的,是以我們可以隻存放二維數組的一半
- 那麼哪些權該怎麼進行儲存呢,直接将辨別為1的替換為權值即可,判斷的時候非0就是鄰接節點
- 再來看有向圖
- 我們可以看出有向圖由于邊有方向 ,是以并不能構成數組的對稱分布,是以對于無向圖的簡化存儲,在有向圖這是行不通的,是以就隻能夠inti來判斷是否有鄰接節點了
- 對于有向圖,怎麼判斷其入度和出度呢?我們從圖中看頂點1的入度是1,出度是2,那麼怎麼從數組中展現出來
圖結構基本概念鄰接矩陣法鄰接法表示十字連結清單存儲圖的儲存形式可以完全不同于上面方法,你可以完全按照你的想法或者業務需求來設計自己的資料結構,是以這是不唯一的,上面的方法隻是給一個參考圖的周遊:深度優先周遊圖的廣度優先周遊 - 行即是出度,列是入度,頂點為1,是以它與其他頂點的關系就都表現在第0行和第0列,是以掃描就知道頂點的度了
- 鄰接矩陣表示法這麼存儲有什麼好處
- 簡單直接容易了解
- 友善檢查任意頂點之間是否有邊
- 友善查找與該頂點鄰接的所有鄰接節點
- 有什麼缺點呢?
- 除了在無向圖中可以簡化一點,但是依舊存在浪費空間情況,而在有向圖中更加明顯
- 因為我們的二維數組是根據頂點的最大值建立的,是以如果存在很多頂點,但是頂點之間的邊非常少,這樣就會造成數組基本都是0的情況,這就是為什麼說是浪費空間
- 我們知道了數組的建立方式,是以如果我們真的遇到了頂點多邊少的情況,當我們統計在這種情況下的邊,我們就不得不一直去周遊0,然後收集僅僅那麼幾個1,是以時間上也是有浪費的
鄰接法表示
- 對于上面的缺點,就是對于稀疏圖(即頂點多,邊少)的存儲比較浪費空間的情況,可以考慮鄰接法,實作方法就是數組加連結清單
- 上面是無向表的存儲,我們可以看到這種格式避免了存儲垃圾資料,1和3不搭邊,鄰接矩陣還需要存儲一個0,而鄰接法則不需要,他隻需要存儲于自己相關的資料,但是,如果仔細觀察還是有問題的,因為我們是用連結清單加數組,連結清單的建立必定是一個對象,那麼這個對象存儲就比數組存儲值空間大的多,并且我們看到,假如頂點2和4用這種方法存儲,頂點而會記錄一個到4的連結清單,而頂點4會記錄一個到2的連結清單,存儲重複,這個也是比較浪費空間的,是以說這個方法比較适合存儲稀疏圖
- 對于無向圖,計算頂點的度,很容易,即周遊連結清單個數即可,判斷是否是鄰接節點也是相當容易的,隻要連結清單中有,就代表這兩個頂點是鄰接節點.
- 看一下有向圖
- 存儲結構沒有多大變動,但是由于邊的方向的關系,上面的存儲結構在計算出度的時候十分容易,即周遊連結清單做累加,但是計算入度的時候就很費勁了,我們還需要一個逆鄰接表,即反向指針,兩個表結合一起使用,才會很容易的計算出度和入度
十字連結清單存儲
- 我們看完上面的鄰接法表示,他的連結清單對象肯定是這樣的
Node { T element 頂點值 Node next 連結指向 } - 正因為是這樣,是以我們隻能在一個鄰接表中友善的得出入度或者出度,那麼我們有什麼辦法可以解決這個限制嗎,那就是十字連結清單,他的連結清單的結構是怎麼樣的呢
- 十字連結清單分為頂點表和邊表,即存儲頂點資訊的和直接存儲邊資訊的表
- 頂點表
Node{ element //頂點值 fristin //入邊鄰接節點 firstout //出邊鄰接節點 } - 上面的頂點表也是用數組存儲的,然後數組指向頂點表,頂點表指向邊表
- 邊表
Node { tailVex 即入邊鄰接節點的起始頂點在數組中的位置,結合圖來看 headVex 即入邊鄰接節點的終止頂點在數組中的位置 headLink 即表示指向弧頭相同的下一條弧 tailLink 即表示指向弧尾相同的下一條弧 } - 首先上面出現了生詞,弧
- 現在我才提弧頭和弧尾,因為之前提這個并沒有太大的作用,那麼他是什麼情況下用呢,即有向圖的邊都稱為弧,弧分為弧頭即指針方向,指針的反方向即為弧尾
- 上面五花八門的,那麼我們慢慢的來梳理為什麼是這麼多指向
- 我們首先找到各頂點的出邊鄰接節點,即
V1:{<1,4>} V2:{<2,1>,<2,3>} V3:{<3,2>,<3,1>} V4:{<>} - 我們來看一下一個小例子
邊表(1,2,null,null)代表什麼 結合圖來看,就代表<2,3>即有向圖頂點2指向頂點3的那條弧(邊),是以這是記錄的弧而不是一個頂點 - 好了我們找到了出邊之後,我們就先看藍色指針的指向
- V1頂點表的出邊即第三個格指向邊表(0,3,null,null),對照上面我們找出來的出邊,應該沒疑問,數字減一因為是數組下表從零開始的
- V2頂點有兩個出邊,這時候V2其實是弧尾,指向的是弧頭,是以V2的頂點表的出邊屬性首先指向邊表(1,0,null,null),這時候還剩下一個<2,3>沒有處理,則讓(1,0,null,null)的第四個屬性指向(1,2,null,null)即可.(因為V2指向V1和V3的時候,V2都是弧尾的角色,是以出路的指向相同即可連續指向,如果再讓V2指向V4即<2,4>,那麼我們就可以在(1,2,null,null)的第四個屬性繼續指向(1,3,null,null))
- V3頂點和V2一樣,他有兩個出邊,就可以讓頂點表的第三個出邊屬性指向一個邊表(2,1,null,null),然後由于都是出邊,是以(2,1,null,null)邊表的第四個屬性可以連續指向(2,0,null,null)
- V4頂點隻有入邊,沒出邊,是以無出邊指向
- 現在藍色代表的出邊指向已經完成了,還剩了紅色代表入邊鄰接節點的指向未處理
- 還是首先整理一下各頂點的入邊情況
V1:{<2,1>,<3,1>} V2:{<3,2>} V3:{<2,3>} V4:{<1,3>} - OK現在來看一下他的入邊是怎麼指向的
- V1頂點有頂點2和頂點3入邊,是以在V1的頂點表的第二個入邊屬性指向(1,0,null,null)即<2,1>,然後由于都是入邊,是以在處理<3,1>的時候,可以讓(1,0,null,null)的第三個弧頭屬性指向(2,0,null,null)即<3,1>
- V2頂點隻有一個入邊,那就讓V2的頂點表的第二個入邊屬性指向(2,1,null,null)即<3,2>即可
- V3,V4同V2一樣的操作
- 好了現在我們就知道了十字連結清單的具體的存儲細節了
- 在十字連結清單中怎麼取入度呢,哇這就簡單了,隻需要周遊頂點表的入邊屬性就可以了,出度就周遊出邊屬性,對于判斷節點間的入邊鄰接節點和出邊鄰接節點一樣是看出邊和入邊屬性即可
圖的儲存形式可以完全不同于上面方法,你可以完全按照你的想法或者業務需求來設計自己的資料結構,是以這是不唯一的,上面的方法隻是給一個參考
圖的周遊:深度優先周遊
圖的廣度優先周遊
- 代碼:無向圖的建立和周遊
import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class MyMatrixImpl { private int vertexCount; //頂點數量 private int edgeCount; private int[][] elementDataArr ;//二維數組 private String[] vertexValueArr ;//頂點值 public static final Scanner SCANNER = new Scanner(System.in); public void createGraph(){ System.out.println("頂點數"); vertexCount = SCANNER.nextInt(); //初始化存放頂點值數組 vertexValueArr = new String[vertexCount]; //将頂點值添加到數組 addVertexValueToArr(); System.out.println("邊數"); edgeCount = SCANNER.nextInt(); //初始化二維數組 elementDataArr = new int[vertexCount][vertexCount]; //開始畫圖 drawGraph(); printGraph(); BFS(); DFS(); } private void printGraph() { System.out.println("\n 建構的圖為 :"); for (int i = 0; i < elementDataArr.length; i++) { for (int j = 0; j < elementDataArr[i].length; j++) { System.out.print(elementDataArr[i][j] + " "); } System.out.println(); } } //畫圖 private void drawGraph() { System.out.println("輸入頂點關系和權重:比如輸入AB2,代表頂點A和頂點B相連,權重為2"); for (int i = 0; i < edgeCount; i++) { //輸入AB2切分為 A B 2 ,并處理為 0 1 2,即對應下标 int[] tmp = splitStr(SCANNER.next()); int row = tmp[0]; int col = tmp[1]; int weight = tmp[2]; elementDataArr[row][col] = weight; elementDataArr[col][row] = weight; } } //輸入AB2切分為 A B 2 ,并處理為 0 1 2,即對應下标 private int[] splitStr(String str) { int[] tmp = new int[3]; String[] split = str.split(""); for (int i = 0; i < tmp.length - 1; i++) { tmp[i] = Arrays.binarySearch(vertexValueArr,split[i]); } tmp[2] = Integer.parseInt(split[2]); //權重 return tmp; } //将頂點值添加到數組 private void addVertexValueToArr() { System.out.println("各個頂點名稱"); for (int i = 0; i < vertexCount; i++) { vertexValueArr[i] = SCANNER.next(); } } //深度優先周遊 public void DFS(){ System.out.println("\n深度優先周遊"); boolean[] isVisited = new boolean[vertexCount];//辨別每個頂點是否被通路過,預設false DFS(isVisited,0); } private void DFS(boolean[] isVisited, int row) { System.out.print(vertexValueArr[row]); isVisited[row] = true; for (int i = 0; i < vertexCount; i++) { if (elementDataArr[row][i] != 0 && !isVisited[i]){ DFS(isVisited,i); } } } //廣度優先周遊,從第一個頂點開始,即數組内第一個存儲頂點 public void BFS(){ System.out.println("廣度優先周遊"); boolean[] isVisited = new boolean[vertexCount];//辨別每個頂點是否被通路過,預設false LinkedList<Integer> list = new LinkedList<>(); list.offer(0); //即第一個頂點對應的第0行 int tmpNum ; while (!list.isEmpty()){ tmpNum = list.poll(); if (!isVisited[tmpNum]){ System.out.print(vertexValueArr[tmpNum]); isVisited[tmpNum] = true; //表示被通路過了 } for (int i = 0; i < vertexCount; i++) { if (elementDataArr[tmpNum][i] != 0 && !isVisited[i]){ list.offer(i); } } } } public static void main(String[] args) { new MyMatrixImpl().createGraph(); } } - 測試
頂點數 7 各個頂點名稱 A B C D E F G 邊數 10 輸入頂點關系和權重:比如輸入AB2,代表頂點A和頂點B相連,權重為2 AC1 CD1 DE1 EG1 GF1 FA1 AB1 BD1 BG1 BF1 建構的圖為 : 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 廣度優先周遊 ABCFDGE 深度優先周遊 ABDCEGF