經典算法題:連通圖的最大生成樹的權和(Gogole筆試題)

2021-02-13 腳本之家

參與答題互動有驚喜

算法能力的考察，向來是頂級科研機構和IT公司面試時最具備區分度的成分，算法功夫紮實，提升面試效率。

這種想法其實也不無道理，從小接受系統化訓練，參加過信息學競賽或ACM，肯定會對算法問題反應更快一些。可是這樣的人畢竟是極少數，而且即使是他們，也無一不是長期大量地訓練才會不斷進步。這至少說明，算法並非天外之學，而是一種能夠通過訓練掌握的技能。換言之，對於5%的真正難題，也許真的是只為5%的天才而存在的。但是其餘的95%，卻是95%像你我一樣的普通人自學可以達成的目標。

提升算法能力，小編帶來了一份高效入門書單。

 01  趣學算法

編輯推薦：

本書從算法之美娓娓道來，沒有高深的原理，也沒有枯燥的公式，通過趣味故事引出算法問題，包含50多個實例及完美圖解，結合學生提問，分析算法本質，並給出代碼實現的詳細過程和運行結果。

本書可作為程式設計師的學習用書，也適合從未有過編程經驗但又對算法有強烈興趣的初學者使用，同時也可作為高等院校計算機、數學及相關專業的師生用書和培訓學校的教材。

 02  算法詳解（卷1）——算法基礎

編輯推薦：

這本書在美亞評分4.7，在作者在線算法課程的基礎之上編寫的，是四卷本系列的第1卷。這個在線課程2012年起就定期更新，它建立在作者在史丹福大學教授多年的本科課程的基礎之上。也許你有所耳聞，這本書就是《算法詳解（卷1）——算法基礎》。如果你更喜歡聽和看，可以在YouTobe上搜索這本書的主題課程，免費觀看。

《算法詳解（卷1）——算法基礎》作者蒂姆·拉夫加登（Tim Roughgarden）是史丹福大學計算機科學系的教授,也是該校管理科學和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷。

這本書詳細講解算法基礎，展現算法本質 ,是一本囊括基本算法知識的詳解指南。集史丹福大學教授多年教學經驗，深入淺出，通俗易懂。 

 03  Python算法詳解

編輯推薦：

本書循序漸進、由淺入深地講解Python算法的核心技術，並通過具體實例的實現過程演練各個知識點的具體使用流程。全書共13章，包括算法，數據結構，常用的算法思想、線性表、隊列和棧，樹，圖，查找算法，內部排序算法，經典的數據結構問題，數學問題的解決，經典算法問題的解決，圖像問題的解決，遊戲和算法等內容。

本書不但適合研究和學習算法的初學者，也適合有一定算法基礎的讀者，還可以作為大中專院校相關專業師生的學習用書和培訓學校的教材。

來看看今天的經典算法題：

來自：Google 2012筆試卷

題目：一個有n個結點的連通圖的生成樹是原圖的最小連通子圖，且包含原圖中所有n個結點，並且有保持圖聯通的最少的邊。最大生成樹就是權和最大生成樹，現在給出一個無向帶權圖的鄰接矩陣，權為0表示沒有邊。｛{0，4，5，0，3}，{4，0，4，2，3}，{5，4，0，2，0}，{0，2，2，0，1}，{3，3，0，1，0}｝，求這個圖的最大生成樹的權和。

A、11

B、12

C、13

D、14

E、15

Google谷歌

《算法題 85：用二進位來編碼字符串（2013年Google校招）》

《算法題 129：哈夫曼樹的帶權路徑長度（創新工場筆試題）》

小貼士：返回上一級搜索「算法題」挑戰更多題目。

備註：

1、不定期將從留言區選出認真答題的1名朋友，贈與書籍《算法詳解（卷1）》一本（兌獎方法跟獲獎者私下溝通）

請留言，說出你的解題思路。不定期整理相關的問題答案分享。

更多精彩

在公眾號後臺對話框輸入以下關鍵詞

查看更多優質內容！

女朋友 | 大數據 | 運維 | 書單 | 算法

大數據 | JavaScript | Python | 黑客

AI | 人工智慧 | 5G | 區塊鏈

機器學習 | 數學 | 留言送書

相關焦點

  • 經典算法題:全連通圖去邊構成樹(Google筆試題)
    ，向來是頂級科研機構和IT公司面試時最具備區分度的成分，算法功夫紮實，提升面試效率。如果你更喜歡聽和看，可以在YouTobe上搜索這本書的主題課程，免費觀看。《算法詳解（卷1）——算法基礎》作者蒂姆·拉夫加登（Tim Roughgarden）是史丹福大學計算機科學系的教授,也是該校管理科學和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷。這本書詳細講解算法基礎，展現算法本質 ,是一本囊括基本算法知識的詳解指南。
  • 經典算法題:懂二進位(小米筆試題)
    輸入例子:1999 2299輸出例子:7經典算法題：《算法題 ：貪心算法（大眾點評筆試題）》《算法題 ：所有String2的字母在String1裡是否存在（大眾點評筆試題）》《算法題 ：順序表插入新元素（迅雷筆試題）》
  • 數據結構與算法——最小生成樹
    生成樹：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環。  最小生成樹：在連通網的所有生成樹中，所有邊的代價和最小的生成樹，稱為最小生成樹。
  • 最小生成樹的兩種方法:Kruskal 算法和 Prim 算法
    /article/details/51908175關於圖的幾個概念定義：連通圖：在無向圖中，若任意兩個頂點vivi與vjvj都有路徑相通，則稱該無向圖為連通圖。強連通圖：在有向圖中，若任意兩個頂點vivi與vjvj都有路徑相通，則稱該有向圖為強連通圖。連通網：在連通圖中，若圖的邊具有一定的意義，每一條邊都對應著一個數，稱為權；權代表著連接連個頂點的代價，稱這種連通圖叫做連通網。生成樹：一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構成一棵樹的n-1條邊。
  • 經典算法題:猜數(360軟體測試工程師筆試題)
    又假設學生Ａ和Ｂ的結論是正確的，則這兩個數字是：（）經典算法題：《算法題 ：貪心算法（大眾點評筆試題）》《算法題 ：所有String2的字母在String1裡是否存在（大眾點評筆試題）》《算法題 ：順序表插入新元素（迅雷筆試題）》《算法題 ：迅雷2016研發工程師5道筆試題
  • 經典算法題 :刪數(華為筆試題)
    留言說出你的答案和理由。華為經典算法題：最高分是多少（華為筆試題）經典算法題：代碼的調用次數（華為筆試題）來挑戰！華為四道筆試算法題小貼士：返回上一級搜索「算法題」挑戰更多題目。本書可作為程式設計師的學習用書，也適合從未有過編程經驗但又對算法有強烈興趣的初學者使用，同時也可作為高等院校計算機、數學及相關專業的師生用書和培訓學校的教材。
  • 經典算法題:一串數字是否是迴文數(小米筆試題)
    >  bool isPalindromeNumber(long num)Java:  boolean isPalindromeNumber(long num)示例：12321 ->  true      3     ->  true       133434->  false經典算法題
  • 經典算法題 :貪心算法(大眾點評筆試題)
    來自：大眾點評2016研發工程師筆試題小貼士：返回上一級搜索「算法題」挑戰更多題目。備註：1、不定期將從留言區選出認真答題的1名朋友，贈與書籍《算法詳解（卷1）》一本（兌獎方法跟獲獎者私下溝通）不定期整理相關的問題答案分享。
  • 最小生成樹(Kruskal算法和Prim算法)
    上一篇文章，我們講了圖的創建和遍歷，其中遍歷的算法主要有BFS（廣度優先算法）和DFS（深度優先算法）兩種，並且DFS算法對很多問題都有很好的啟示！而今天我們要說一個非常實用的算法——最小生成樹的建立！這是圖論中一個經典問題，可以使用Kruskal和Prim兩種算法來進行實現！
  • 貪心算法:最小生成樹
    設G = (V,E)是無向連通帶權圖，即一個網絡。E中的每一條邊（v,w）的權為c[v][w]。如果G的子圖G』是一棵包含G的所有頂點的樹，則稱G』為G的生成樹。生成樹上各邊權的總和稱為生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。構造最小生成樹的兩種方法：Prim算法和Kruskal算法。一、最小生成樹的性質設G = (V,E)是連通帶權圖，U是V的真子集。
  • 經典算法題:二叉樹與前序、中序、後序遍歷(微軟筆試題)
    ，向來是頂級科研機構和IT公司面試時最具備區分度的成分，算法功夫紮實，提升面試效率。如果你更喜歡聽和看，可以在YouTobe上搜索這本書的主題課程，免費觀看。《算法詳解（卷1）——算法基礎》作者蒂姆·拉夫加登（Tim Roughgarden）是史丹福大學計算機科學系的教授,也是該校管理科學和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷。這本書詳細講解算法基礎，展現算法本質 ,是一本囊括基本算法知識的詳解指南。
  • 數據結構圖的最小生成樹的算法和應用舉例
    一、最小生成樹介紹圖結構是一種非常重要的非線性數據結構，帶權圖的最小生成樹在工程技術，科學管理的最優解問題中有著廣泛的應用。最小生成樹：權值和最小的生成樹最小生成樹的性質：假設G=(V,E)是個連通圖，U是頂點V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。
  • 經典算法題 :矩陣元素相乘(搜狗筆試題)
    小貼士：返回上一級搜索「算法題」挑戰更多題目。提升算法能力，小編帶來了一份高效入門書單。 01  趣學算法編輯推薦：本書從算法之美娓娓道來，沒有高深的原理，也沒有枯燥的公式，通過趣味故事引出算法問題，包含50多個實例及完美圖解，結合學生提問，分析算法本質，並給出代碼實現的詳細過程和運行結果。
  • 最小生成樹
    在生活中，圖的應用非常廣泛，比如通信編解碼、最優路徑規劃、分配問題，在生產管理、軍事、交通運輸等方面有大量實際需要。
  • 經典算法題 :廣義表(迅雷筆試題)
    小貼士：返回上一級搜索「算法題」挑戰更多題目。提升算法能力，小編帶來了一份高效入門書單。 01  趣學算法編輯推薦：本書從算法之美娓娓道來，沒有高深的原理，也沒有枯燥的公式，通過趣味故事引出算法問題，包含50多個實例及完美圖解，結合學生提問，分析算法本質，並給出代碼實現的詳細過程和運行結果。
  • 今晚7:30論文解讀直播 | 二樹網絡生成樹算法與DeepWalk經典算法
    今晚（8月19日）19:30-20:30，我們邀請到青海師範大學趙海興老師和冶忠林老師作客集智學園直播間，在線解讀二樹網絡生成樹算法的論文，與DeepWalk
  • 圖像處理十大經典算法
    隨著現代社會的發展，信息的形式和數量正在迅猛增長。其中很大一部分是圖像，圖像可以把事物生動地呈現在我們面前，讓我們更直觀地接受信息。下面簡單介紹下數字圖像處理領域中的經典算法。七、Prim算法圖論的一種算法，可在加權連通圖裡搜索最小生成樹。由此算法搜索到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。
  • 圖論最小生成樹
    前言推出一個新系列，《看圖輕鬆理解數據結構和算法》，主要使用圖片來描述常見的數據結構和算法，輕鬆閱讀並理解掌握。本系列包括各種堆、各種隊列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。最小生成樹最小生成樹(Minimum Spanning Tree)，簡稱MST，更詳細點叫最小權重生成樹，是一副連通加權無向圖中一棵權值最小的生成樹。
  • 《算法》筆記 11 - 最小生成樹
    最小生成樹就是用於在加權無向圖中解決這類問題的。最小生成樹相關的算法在通信、電子、水利、網絡、交通燈行業具有廣泛的應用。圖的生成樹是它的一顆含有其所有頂點的無環連通子圖，一副加權無向圖的最小生成樹(Minimum spanning tree)是它的一顆權值（樹中所有邊的權值之和）最小的生成樹。
  • 圖解Kruskal生成樹算法
    1 Kruskal算法簡介 求解最小代價生成樹的Kruskal算法採用了貪心方法。該算法將圖視為一個森林，圖中的每個節點都是獨立的樹。在整個過程中，將繼續檢查生成屬性是否保持不變。在這種情況下，通過添加一條邊，生成樹的性質不成立，那麼將考慮不包括邊在圖中。