2018-2019-20172329 《Java软件结构与数据结构》第九周学习总结
2018-2019-20172329 《Java軟件結構與數據結構》第九周學習總結
教材學習內容總結
《Java軟件結構與數據結構》第十五章-圖
一、圖及無向圖
- 1、圖的相關概念：
- （1）一個圖（graph）G=（V，E）由頂點（vertex）的集V和邊（edge）的集E組成。每一條邊就是一幅點對（v，w）。
- （2）如果點對是有序的，那么圖就是有向的。
- （3）假如點對是無序的，那么圖就是無向的。
- （4）如果圖中的兩個頂點之間有一條連通邊，則稱這兩個頂點是銜接的。鄰接頂點有時也稱為鄰居。連通一個頂點及其自身的邊稱為自循環或環。
- （5）邊的條數的計算：對于第一個頂點，需要（n-1）條邊將其與其他頂點連通。而對于第2個頂點，只需要（n-2）條邊，因為第二個頂點已經和第一個頂點連通了。第三個頂點需要（n-3）條邊。繼續向下，直到最后一個頂點，這個末頂點不需要額外的邊，因為所有其他的頂點都已經和它連通了。1～n的求和是：求和（n+1）n/2。
- （6）路徑：路徑是圖中的一系列邊，每條邊連通兩個頂點。
- （7）路徑的長度是該路徑中邊的條數（或者是頂點減去1）
- 2、無向圖：
- （1）如果無向圖擁有最大數目的連通頂點的邊，則認為這個無向圖是完全的。
- （2）如果無向圖中的任意兩個頂點之間都存在一條路徑，則認為這個無向圖是連通的。
- （3）無向樹是一種連通的無環無向圖，其中一個元素被指定為樹根。
二、有向圖
- 1、有向圖有時也稱為雙向圖，它是一種邊為有序頂點對的圖。如下圖：
- 2、有向圖中的路徑是圖中連通兩個頂點的有向邊序列。
- （1）連通：
- （2）沒連通：
- （1）連通：
- 3、拓撲序：
- （1）拓撲排序是對有向無圈圖的頂點的一種排序，使得存在一條從vi到vj的路徑，那么在排序中vi的后面。
- 4、有向圖的屬性：
- （1）不存在其他頂點到樹根的連接。
- （2）每個非樹根元素恰好有一個連接。
- （3）樹根到每個其他頂點都有一條路徑。
三、網絡
- 1、網絡：或稱為加權圖，是一種每條邊都帶有權重或代價的圖。
- 加權圖中的路徑權重是該路徑中各條邊權重的和。
- 對于網絡我們將用一個三元組來表示各條邊。這三元組包括起始起點、終止頂點和權重。注：對于無向網絡來說，起始頂點和終止頂點可以互換。但是在有向圖來說，必須包含每個右相連接的三元組。
四、常用的圖算法
- 1、遍歷
（1）廣度優先遍歷：
- a、廣度優先遍歷類似于樹的前序遍歷；
- b、可以用一個隊列和一個無序列表來構造出結果；
- c、步驟：
- 1、起始頂點進入隊列，同時標記該頂點為已訪問的。
- 2、然后開始循環，該循環一直持續到隊列為空時停止，在這個循環中，從從隊列中取出這個首頂點，并將它添加到列表的末端。
- 3、接著讓所有與當前頂點鄰接且尚未被標記為已訪問的各個頂點依次進入到隊列，同時把他們逐個標記為已訪問，然后重復上述循環。
- 4、對每個已訪問的結點都重復這一過程，直到隊列為空時結束，這意味著我們無法再找到任何新的頂點。
- 5、現在的鏈表即以廣度優先遍歷器。
- d、遍歷實例：從頂點9開始進行廣度優先遍歷的步驟如下（連接如下圖）
1、往隊列中添加9，并且把它標記為已訪問；
2、從隊列中取出9；
3、往鏈表中添加9；
4、從隊列中添加6、7、8，逐個標記為已訪問；
5、從隊列中取出6；
6、往鏈表中添加6；
7、往隊列中添加3、4，逐個標記為已訪問。
8、從隊列中取出7，并將它添加到鏈表中；
9、往隊列中添加5，并且把它標記為已訪問；
10、從隊列中取出8，并將它添加到鏈表中（這時不再往隊列中添加任何新的結點了，因為頂點8再也沒有尚未訪問過的鄰居了）
11、從隊列中取出3，并將它添加到鏈表中；
12、往隊列中添加1，并且把它標記為已訪問；
13、從隊列中取出4，并加它添加到列表中；
14、往隊列中添加2，并且把它標記為已訪問；
15、從隊列中取出5，并將它添加到列表中（由于再沒有未訪問過的鄰居，因此不需再往隊列中添加頂點）
16、從隊列中取出2，并將它添加到鏈表中；
17、從隊列中取出2，并將它添加到列表中。
這樣列表就以廣度優先次序存放了從頂點9開始的如下頂點：9、6、7、8、3、4、5、1和2.
- 2、測試連通性
- （1）定義：如果圖中的任意兩個頂點之間都存在一條路徑，則認為這個圖是連通的。
- （2）該定義對無向圖和有向圖都是成立的。
- （3）判定：在一個含n個頂點的圖中，當且僅當對每個頂點v，從v開始的廣度優先遍歷的列表大小都是n，則該圖就是連通的。
- 舉例：
如下圖：
| A | A,B,C,D |
| B | B,A,D,C |
| C | C,B,A,D |
| D | D,B,A,C |
- 3、最小生成樹
- （1）生成樹是一顆含有圖中所有頂點和部分邊（但有可能不是所有邊）的樹。由于樹也是圖，因此對于某些樹而言，其本身就是一顆生成樹，這是該圖的唯一生成樹包含所有邊。
- 如圖
| A | A,B,C |
| B | B,A,C |
| C | C,B,A |
| D | D |
- （2）生成樹的一個有趣應用是找出加權圖的最小生成樹。最小生成樹，其邊的權重其邊的權重總和小于或等于同一個圖中的其他任何一顆生成樹的權重總和。
- （3）算法介紹：Prim算法
- 1、計算最小生成樹的一種方法是使其連續地一步一步長成。在每一步，都要把一個結點當作根并往上加邊。
- 2、在算法的任意時刻，我們都可以看到一組已經添加到樹上的頂點，而其余頂點尚未加到這棵樹中。此時算法在每一階段都可以通過選擇邊（u，v）使得（u，v）的值是所有u在樹上但v不在樹上的邊的值中的最小者而找到一個新的頂點并把它添加到這課樹中。
- 3、如圖：
- 4、判斷最短路徑
- （1）判斷圖中的最短路徑有兩種情況：
- 1、判定起始頂點與目標頂點之間的字面意義上的最短路徑，也就是兩個頂點之間的最小邊樹。
- 2、尋找加權圖的最便宜路徑。
- （2）第一種：從起始頂點到本頂點的路徑長度，以以路徑中作為本頂點前驅的那個頂點。接著要修改循環，使得當抵達目標頂點時循環將終止，最短路徑的路徑長度就是從起始頂點到目標頂點前驅頂點的路徑長度再加1:如果要輸出這條最短路徑上的頂點，只需沿著前趨鏈回溯即可。
- （3）第三個：新的一個算法：Dijkstra算法，我會在代碼問題中詳細進行描述。
教材學習中的問題和解決過程
- 問題1：在教材308頁中介紹有向圖的時候有這樣兩句話：
有向圖有時也稱為雙向圖。
有向圖中的路徑并不是雙向的。
就這兩句話，我產生了疑問，為什么有向圖不為雙向，但叫做雙向圖，他所謂的雙向是一樣的嗎？
- 問題1解決方案：
（1）因為就有向圖本身而言，為的確可以為雙向的，我們可以在上述的教材內容總結中在網絡一部分可以看到兩張這樣的圖：
在第二張很顯然就是一個雙向的網絡，網絡同樣也是圖的一種，但是我很詳細的看了一下有向圖中的路徑并不是雙向的。這句話出現的地方，這句話后買呢還接著一句話：除非我們添加了額外的邊連通他們倆，也就是這句話介紹是就假如A指向了B，但是在前提中就沒有讓B指向A，當我們有指向返回的那條邊的時候才可以有雙向，所以我覺得書本在這里寫的會誤導第一次學習有向圖的同學。
代碼調試中的問題和解決過程
- 問題1：pp15.7的具體以及我思考的整個過程？
- 問題1解決方案：
（1）這一周假如算看完書開始做pp項目以來，引得我三天茶不思飯不想的一道題就是這個pp15.7，既然將它寫進這個調試，我覺得需要好好記錄一下這一周中三天是如何進行這道題的思考的。
（2）其實這道題想想并不難，它只是要求我們求的最便宜路徑的最便宜價格是多少，所以一開始我的第一個問題就是如何去保存這個我們輸入的權重。因為一開始真的是沒有什么思路，就一直在紙上畫，寫各種各樣的偽代碼。
（3）然后就突然有了自己的第一版想法： - 1、我在看到用鄰接矩陣記錄是否連通的這個數組有了契機，就覺得這個二維數組是個好東西，就覺得是它了。因為我就在添加邊的方法中加了這樣一句語句Weight[getIndex((T) vertex1)][getIndex((T) vertex2)]=weight;,用于對于權重添加到一個二位數組中，同時在無向圖中是有與它對稱的語句Weight[getIndex((T) vertex2)][getIndex((T) vertex1)]=weight;，這樣就講連起來的線給賦予一個權重。
- 2、然后我寫了這樣的一個表格進行明晰
- 3、然后我就想通過兩個或三個循環進行找到T,然后用一個result記錄下來，進行重復的找然后找到一條路走到盡頭，將結果存進一個數組中，重復過程。我的第一版代碼如下
- 4、然后將存進數組的元素找到最小的那個進行輸出
5、為什么我會斃掉第一版，因為存在著很大的問題，首先，假如我插入的元素夠多，我的循環不夠多，（我想過用遞歸實現，但是因為涉及二維數組的橫向判斷，所以我覺得遞歸也不行），然后就是因為涉及到橫向的判斷，舉個例子，假如A和B連了，B和C連了，B和D也連了，這個時候我們就多了一路，因為二維數組移動的位置太不可控，所以位置的增加減少就存在很大的問題，所以就陷入了一直想用連續循環的這個弊病中，一時半會兒一直解決不了這個問題，就想著能不能用我們pp15.1需要實現的方式，也就是用鏈表的方式。
6、（1）首先我們先構建這樣的一個圖：
（2）然后我們需要構建類似鏈地址法繪制出一個如下圖的圖：
（3）我的新的一版思路是：當我們在保存頭結點的數組中找到開始的結點，然后再需要寫循環進行對于是否連接進行判斷，在進行將權重相加，但是我依舊又是斃了這一版，因為在偶爾的一天晚上凌晨，翻到了算法導論圖論的這一部分，看到了里面講解的有一部分叫做單源最短路徑，發現這一部分和這個題目存在著很大的關聯，就仔細的看了看，有一個算法就是針對此類題型設計的，叫做Dijkstra算法，我很感謝我當時買了這本書，讓我從痛苦中走了出來。
（4）Dijkstra算法：
- 1、這個算法被譽為貪婪算法最好的例子。貪婪算法一般分階段求解一個問題，在每個階段他都把出現的當做是最好的例子。貪婪算法主要的問題在于，該算法不是總能夠成功的。
- 2、舉個例子：
（1）第一個選擇的頂點是v1，路徑長是為0；該頂點標記為known。既然v1是known的，那么某些表項就需要調整。鄰接到v1的頂點是v2和v4。這兩個項得到調整。
（2）下一步，選取v4并且標記為known。頂點v3,v5,v6,v7是鄰接的頂點，而它們實際上都需要調整。如圖
（3）接下來選擇v2，v4是鄰接的點，但已經是known的了，因此對它沒有工作要做。v5是鄰接的點但不做調整，因為經過v2的值2+10=12而長為3的路徑已經是已知的。圖
（4）下一個被選擇的頂點是v5，其值為3。v7是唯一的鄰接頂點，但是它不用調整，因為3+6>5.然后選取v5，對v6的距離下調到3+5=8。如圖：
（5）再下一個選取的頂點是v7，v6下調到5+1=6，如圖：
（6）最后，我們選取的頂點是v6。最后的表在下圖中顯示，在如下的圖形顯示算法期間是如何標記為known的以及頂點是如何更新的。
上周考試錯題總結
本周無測試。
結對及互評
- 本周結對學習情況
- 20172316趙乾宸
- 博客中值得學習的或問題：
- 內容詳略得當；
- 代碼調試環節比較詳細；
- 基于評分標準，我給本博客打分：5分。得分情況如下：
代碼調試中的問題和解決過程, 一個問題加1分
- 20172316唐才銘
- 博客中值得學習的或問題：
- 內容詳略得當；
- 代碼調試環節比較詳細；
- 基于評分標準，我給本博客打分：9分。得分情況如下：
感悟
第一次要好好寫寫感悟了：
- 1、我覺得現在班里寫博客呈現出一種我覺得學習java或者學習編程很大的一個弊病，不僅僅是我們學生自己本身，還包括。。。你懂的。我覺得我們學習一門匯編語言應勤于練習，原理是需要了解，但是博客寫的如此之多，難道就為了換個加分？？是這樣么？現在很多人寫博客20小時，敲代碼10分鐘，難道現在不常見么，碼云上，看看，抄抄，多快，很多人自己連腦子都不會動一下，所以我希望不要把有心人的努力慢慢磨的沒有了，我覺得我現在為了寫一篇博客花了太多的時間去完善我的博客，沒有問題，沒有教材，我覺得那個只不過是因為很多人已經對于這樣的形式趨于疲乏。我們大家的時間都很重要，教材總結，我們看了一遍，還得把教材的自己總結一下，我覺得那不如讓我們別敲代碼的了，就寫博客，分不也很高。
- 2、我自己本身對于分數并不是很在意，只不過只是自己期末的分數高低而已，學沒學到真本事誰也不知道，我可以舉個例子，我的結對小伙伴趙乾宸本是一個編碼能力超強，腦子非常聰明的人，很多人真的不知道他有多強，但是現在這種形式，我覺得博客從紀錄分數變成如此的利益化，我覺得本身意義就很弱了，很多人肯定會給我說，那你寫這么多干什么，因為我傻。
學習進度條
| 目標 | 5000行 | 30篇 | 400小時 |
| 第一周 | 0/0 | 1/1 | 6/6 |
| 第二周 | 1313/1313 | 1/2 | 20/26 |
| 第三周 | 901/2214 | 1/3 | 20/46 |
| 第四周 | 3635/5849 | 2/4 | 20/66 |
| 第五周 | 1525/7374 | 1/5 | 20/86 |
| 第六周 | 1542/8869 | 2/5 | 25/111 |
| 第七周 | 1391/10260 | 1/6 | 20/131 |
| 第八周 | 4379/14639 | 2/8 | 25/156 |
| 第九周 | 3155/17794 | 1/9 | 30/186 |
參考資料
藍墨云班課
Java程序設計
算法導論：別點了，是本書
數據結構與算法分析：別點了，是本書
Dijkstra 最短路徑算法 秒懂詳解
轉載于:https://www.cnblogs.com/qh45wangwenbin/p/9977273.html
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的2018-2019-20172329 《Java软件结构与数据结构》第九周学习总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Hadoop的伪分布式安装
- 下一篇： 分类与监督学习，朴素贝叶斯分类算法