偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

圖算法系列之無(wú)向圖的數(shù)據(jù)結(jié)構(gòu)

大數(shù)據(jù) 數(shù)據(jù)分析 算法
從本篇開(kāi)始我們將會(huì)一起來(lái)學(xué)習(xí)圖相關(guān)的算法,圖算有很多相當(dāng)實(shí)用算法,比如:垃圾回收器的標(biāo)記清除算法、地圖上求路徑的最短距離、拓?fù)渑判虻?。在開(kāi)始學(xué)習(xí)這些算法之前我們需要先來(lái)了解下圖的基本定義,以及使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一張圖,本篇我們先從無(wú)向圖開(kāi)始學(xué)習(xí)。

[[393944]]

 本文轉(zhuǎn)載自微信公眾號(hào)「貝塔學(xué)JAVA」,作者Silently9527。轉(zhuǎn)載本文請(qǐng)聯(lián)系貝塔學(xué)JAVA公眾號(hào)。

前言

從本篇開(kāi)始我們將會(huì)一起來(lái)學(xué)習(xí)圖相關(guān)的算法,圖算有很多相當(dāng)實(shí)用算法,比如:垃圾回收器的標(biāo)記清除算法、地圖上求路徑的最短距離、拓?fù)渑判虻?。在開(kāi)始學(xué)習(xí)這些算法之前我們需要先來(lái)了解下圖的基本定義,以及使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一張圖,本篇我們先從無(wú)向圖開(kāi)始學(xué)習(xí)。

圖的定義

圖:是有一組頂點(diǎn)和一組能夠?qū)蓚€(gè)訂單相連組成的。連接兩個(gè)頂點(diǎn)的邊沒(méi)有方向,這種圖稱之為無(wú)向圖。

圖的術(shù)語(yǔ)

通過(guò)同一條邊相連的兩個(gè)頂點(diǎn)我們稱這兩個(gè)頂點(diǎn)相鄰;

某個(gè)頂點(diǎn)的度數(shù)即表示連接這個(gè)頂點(diǎn)的邊的總數(shù);如上圖:頂點(diǎn)1的度數(shù)是3

一條邊連接了一個(gè)頂點(diǎn)與其自身,我們稱為自環(huán)

連接同一對(duì)頂點(diǎn)的邊稱為平行邊

術(shù)語(yǔ)還有很多,暫時(shí)這里只列出本篇我們需要使用到的術(shù)語(yǔ),后面有在使用到其他的術(shù)語(yǔ)再做解釋,太多也不太容易記得住

如何表示出圖

圖用什么數(shù)據(jù)結(jié)構(gòu)來(lái)表示主要參考兩個(gè)要求:

  1. 在開(kāi)發(fā)圖的相關(guān)算法時(shí),圖的表示的數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ),所以這種數(shù)據(jù)結(jié)構(gòu)效率的高
  2. 在實(shí)際的過(guò)程中圖的大小不確定,可能會(huì)很大,所以需要預(yù)留出足夠的空間

考慮了這兩個(gè)要求之后大佬們提出以下三個(gè)方法來(lái)供選擇:

  • 鄰接矩陣 鍵入有v個(gè)頂點(diǎn)的圖,我們可以使用v乘以v的矩陣來(lái)表示,如果頂點(diǎn)v與w相連,那么把v行w列設(shè)置為true,這樣就可以表示兩個(gè)頂點(diǎn)相連,但是這個(gè)方式有個(gè)問(wèn)題,如果遇到圖很大,會(huì)造成空間的浪費(fèi)。不滿足第二點(diǎn)。其次這種方式?jīng)]辦法表示平行邊
  • 邊的數(shù)組 可以定義一個(gè)表示的邊對(duì)象,包含兩個(gè)int屬性表示頂點(diǎn),但是如果需要找到某個(gè)頂點(diǎn)的相連頂點(diǎn)有哪些,我們就需要遍歷一遍全部的邊。這種數(shù)據(jù)結(jié)構(gòu)的效率較差
  • 鄰接表數(shù)組 定義一個(gè)數(shù)組,數(shù)組的大小為頂點(diǎn)的個(gè)數(shù),數(shù)據(jù)下標(biāo)表示頂點(diǎn),數(shù)組中每個(gè)元素都是一個(gè)鏈表對(duì)象(LinkedListQueue),鏈表中存放的值就是與該頂點(diǎn)相連的頂點(diǎn)。(LinkedListQueue我們已經(jīng)在之前的文章中實(shí)現(xiàn),可以參考文章《https://juejin.cn/post/6926685994347397127》)

無(wú)向圖的API定義

  1. public class Graph { 
  2.     public Graph(int V); //創(chuàng)建含有v個(gè)頂點(diǎn)不含邊的圖 
  3.      
  4.     public int V(); //返回頂點(diǎn)的個(gè)數(shù) 
  5.      
  6.     public int E(); //返回圖中邊的總數(shù) 
  7.      
  8.     public void addEdge(int v, int w); //向圖中添加一條邊 v-W  
  9.          
  10.     public Iterable<Integer> adj(int v); //返回與v相鄰的所有頂點(diǎn) 
  11.      
  12.     public String toString(); //使用字符串打印出圖的關(guān)系 

無(wú)向圖API的實(shí)現(xiàn)

要實(shí)現(xiàn)上面定義的API,我們需要三個(gè)成員變量,v表示圖中頂點(diǎn)的個(gè)數(shù),e表示圖總共邊的數(shù)據(jù),LinkedListQueue的數(shù)組用來(lái)存儲(chǔ)頂點(diǎn)v的相鄰節(jié)點(diǎn);

構(gòu)造函數(shù)會(huì)初始化空的鄰接表數(shù)組

因?yàn)槭菬o(wú)向圖,所以addEdge方法在向圖中添加邊既要添加一條v->w的邊,有需要添加一條w->v的邊

  1. public class Graph { 
  2.     private final int v; 
  3.     private int e; 
  4.     private LinkedListQueue<Integer>[] adj; 
  5.  
  6.     public Graph(int v) { 
  7.         this.v = v; 
  8.         this.adj = (LinkedListQueue<Integer>[]) new LinkedListQueue[v]; 
  9.         for (int i = 0; i < v; i++) { 
  10.             this.adj[i] = new LinkedListQueue<>(); 
  11.         } 
  12.     } 
  13.  
  14.     public int V() { 
  15.         return v; 
  16.     } 
  17.  
  18.     public int E() { 
  19.         return e; 
  20.     } 
  21.  
  22.     public void addEdge(int v, int w) { 
  23.         this.adj[v].enqueue(w); 
  24.         this.adj[w].enqueue(v); 
  25.         this.e++; 
  26.     } 
  27.  
  28.     public Iterable<Integer> adj(int v) { 
  29.         return this.adj[v]; 
  30.     } 
  31.  
  32.     @Override 
  33.     public String toString() { 
  34.         StringBuilder sb = new StringBuilder(); 
  35.         sb.append(v).append(" 個(gè)頂點(diǎn),").append(e).append(" 條邊\n"); 
  36.         for (int i = 0; i < v; i++) { 
  37.             sb.append(i).append(": "); 
  38.             for (int j : this.adj[i]) { 
  39.                 sb.append(j).append(" "); 
  40.             } 
  41.             sb.append("\n"); 
  42.         } 
  43.         return sb.toString(); 
  44.     } 

圖的常用工具方法

基于圖數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn),我們可以提供一些工具方法

計(jì)算頂點(diǎn)v的度數(shù) 頂點(diǎn)的度數(shù)就等于與之相連接頂點(diǎn)的個(gè)數(shù)

  1. public static int degree(Graph graph, int v) { 
  2.     int degree = 0; 
  3.     for (int w : graph.adj(v)) { 
  4.         degree++; 
  5.     } 
  6.     return degree; 

計(jì)算所有頂點(diǎn)的最大度數(shù)

  1. public static int maxDegree(Graph graph) { 
  2.     int maxDegree = 0; 
  3.     for (int v = 0; v < graph.V(); v++) { 
  4.         int degree = degree(graph, v); 
  5.         if (maxDegree < degree) { 
  6.             maxDegree = degree; 
  7.         } 
  8.     } 
  9.     return maxDegree; 

計(jì)算所有頂點(diǎn)的平均度數(shù) 每條邊都有兩個(gè)頂點(diǎn),所以圖所有頂點(diǎn)的總度數(shù)是邊的2倍

  1. public static double avgDegree(Graph graph) { 
  2.     return 2.0 * graph.E() / graph.V(); 

計(jì)算圖中的自環(huán)個(gè)數(shù) 對(duì)于頂點(diǎn)v,如果v同時(shí)也出現(xiàn)了在v的鄰接表中,那么表示v存在一個(gè)自環(huán);由于是無(wú)向圖,每條邊都被記錄了兩次(如果不好理解可以把圖的toString打印出來(lái)就可以理解了)

  1. public static int numberOfSelfLoops(Graph graph) { 
  2.     int count = 0; 
  3.     for (int v = 0; v < graph.V(); v++) { 
  4.         for (int w : graph.adj(v)) { 
  5.             if (v == w) { 
  6.                 count++; 
  7.             } 
  8.         } 
  9.     } 
  10.     return count / 2; 

總結(jié)

本篇我們主要學(xué)習(xí)使用何種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一張圖,以及基于這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了幾個(gè)簡(jiǎn)單的工具方法,在下一篇我們將來(lái)學(xué)習(xí)圖的第一個(gè)搜索算法 - 深度優(yōu)先搜索

文中所有源碼已放入到了github倉(cāng)庫(kù):https://github.com/silently9527/JavaCore

 

責(zé)任編輯:武曉燕 來(lái)源: 貝塔學(xué)JAVA
相關(guān)推薦

2021-04-28 07:59:21

深度優(yōu)先搜索

2020-10-17 11:14:19

數(shù)據(jù)結(jié)構(gòu)與算法系列

2023-04-13 08:14:53

數(shù)據(jù)結(jié)構(gòu)算法存儲(chǔ)

2023-04-14 08:07:20

數(shù)據(jù)結(jié)構(gòu)算法搜索

2021-05-10 08:07:40

圖算法路徑頂點(diǎn)

2020-06-28 09:57:24

數(shù)據(jù)結(jié)構(gòu)算法

2011-04-06 08:54:28

CactiRRD

2023-12-22 08:56:01

Java編程語(yǔ)言鏈表

2019-09-18 08:31:47

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

2021-09-06 09:05:58

kafkaZookeeper數(shù)據(jù)

2015-08-06 15:20:21

runtimeIOS開(kāi)發(fā)

2020-10-21 14:57:04

數(shù)據(jù)結(jié)構(gòu)算法圖形

2023-03-08 08:03:09

數(shù)據(jù)結(jié)構(gòu)算法歸并排序

2023-04-27 09:13:20

排序算法數(shù)據(jù)結(jié)構(gòu)

2020-09-18 09:13:46

數(shù)據(jù)結(jié)構(gòu)元素

2023-10-27 07:04:20

2022-02-22 15:27:46

數(shù)據(jù)結(jié)構(gòu)容器算法

2009-08-03 17:38:12

排序算法C#數(shù)據(jù)結(jié)構(gòu)

2023-07-27 13:31:14

Linux語(yǔ)言數(shù)據(jù)

2023-03-07 08:02:07

數(shù)據(jù)結(jié)構(gòu)算法數(shù)列
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)