【自考】數據結構第五章圖,期末不掛科指南,第9篇

来源:https://www.cnblogs.com/happymeng/archive/2020/01/10/shujujiegou_9.html

圖的基本概念 首先,你要明確圖是什麼樣子的,就是下麵這個樣子的 圖的定義與術語 有向圖和無向圖 直接對比圖就可以看出來,有向圖和無向圖的區別了,這個沒有什麼難的。 有向圖和無向圖的表示法有略微的區別,註意看 G1有箭頭,有向圖,表示方法是 G2無箭頭,無向圖,表示方法是 弧、弧頭、弧尾:有向圖的邊稱 ...


圖的基本概念

首先,你要明確圖是什麼樣子的,就是下麵這個樣子的
數據結構自考

圖的定義與術語

有向圖和無向圖

直接對比圖就可以看出來,有向圖和無向圖的區別了,這個沒有什麼難的。
數據結構自考 數據結構自考

有向圖和無向圖的表示法有略微的區別,註意看
G1有箭頭,有向圖,表示方法是 V={V~0~,V~1~,V~2~,V~3~} E = {<V~0~,V~1~>,<V~1~,V~2~>,<V~1~,V~0~>,<V~2~,V~0~>,<V~2~,V~3~>}
G2無箭頭,無向圖,表示方法是 V={V~0~,V~1~,V~2~,V~3~} E = {(V~0~,V~1~),(V~1~,V~2~),(V~0~,V~2~),(V~2~,V~3~)}

弧、弧頭、弧尾:有向圖的邊稱為弧。無向圖叫做邊。有序偶對<v,w>表示有向圖從v到w的一條弧,v稱為弧尾或始點,w稱為弧頭或終點。

任何兩點之間都有邊的無向圖稱為無向完全圖。
任何兩點之間都有弧的有向圖稱為有向完全圖。

權、帶權圖:圖的邊附帶數值,這個數值叫權。每條邊都帶權的圖稱為帶權圖。

頂點的度、入度、出度:

  1. 無向圖中頂點v的度是與該頂點相關聯的邊的數目,記為D(v)。
  2. 有向圖中,把以頂點v為終點的弧的數目稱為v的入度,記為ID(v);把以頂點v為始點的弧的數目稱為v的出度,記為OD(v)。有向圖頂點v的度為入度和出度之和,即D(v) = ID(v)+ OD(v)。

簡單路徑、迴路、簡單迴路:序列中頂點不重覆出現的路徑稱為簡單路徑。第一個頂點和最後一個頂點相同的路徑稱為迴路。除了第一個頂點和最後一個頂點外,其餘頂點不重覆的迴路,稱為簡單迴路或簡單環。

下麵還有一些需要瞭解的術語

連通、連通圖、連通分量、極大連通子圖、強連通、強連通圖、強連通分量、生成樹、生成森林

如果精力足夠,都看看吧

圖的存儲結構

圖的存儲結構有很多中,例如 鄰接矩陣、鄰接表、十字鏈表和鄰接多重表

鄰接矩陣

矩陣中標記1,有邊,標記0,沒有邊

註意:無向圖的鄰接矩陣是一個對稱矩陣

數據結構自考 數據結構自考 數據結構自考

帶權圖的鄰接矩陣
數據結構自考 數據結構自考 數據結構自考

鄰接矩陣自考/期末考試真題

數據結構自考

嘗試著,畫出無向圖吧!

鄰接表

鄰接表是順序存儲與鏈式存儲相結合的存儲方法。

下圖中,左側是無向圖,右側是該無向圖的鄰接表,註意看,該符號,表示結束,沒有連接的頂點了。

數據結構自考

有向圖及其類似,這個就不在做圖擴充

圖的遍歷

圖的遍歷是指從圖的某個頂點出發,系統地訪問圖的每個頂點,並且每個頂點只被訪問一次。
遍歷圖的基本方法有兩種:深度優先搜索和廣度優先搜索。

連通圖的深度優先搜索

深度優先,就是往下走,走不動了,返回上一級在走
數據結構自考

連通圖的廣度優先搜索

順著一個頂點,然後都遍歷完。

數據結構自考,自考

圖的應用

最小生成樹的概念

概念:一個圖的最小生成樹是圖所有生成樹中權總和最小的生成樹

構造最小生成樹的Prim演算法

每次都找權值最小的

看案例
數據結構自考,自考

構造最小生成樹的克魯斯卡爾演算法單源最短路徑 這兩種演算法,自己看一下吧。

拓撲排序

  1. AOV網

    工程或者某種流程可以分為若幹個小的工程或階段,這些小的工程或階段就稱為活動。
    如果以圖中的頂點來表示活動,有向邊表示活動之間的優先關係,這種用頂點表示活動的有向圖稱為AOV網。

數據結構自考,自考

  1. 拓撲排序
    設G=(V,E) 是一個具有n個頂點的有向圖,V中頂點的序列v~1~,v~2~,...,v~n~稱為一個拓撲序列,當且僅當該頂點序列滿足下列條件:若在有向圖G中,從頂點v~i~ ~ v~j~ 有一條路徑,則在拓撲序列中頂點v~i~必須排在v~j~之前。找到一個有向圖的一個拓撲序列的過程稱為拓撲排序。完成拓撲排序的前提條件是AOV網中不允許出現迴路。

拓撲排序演算法的時間複雜度為O(n+e),n是圖的頂點個數,e是圖的弧的數目。

拓撲排序演算法的基本步驟如下:

  1. 圖中選擇一個入度為0的頂點,輸出該頂點
  2. 從圖中刪除該頂點及相關聯的弧,調整被刪弧的弧頭結點的入度(入度減1);
  3. 重覆執行上述兩個步驟,直到所有的入度為0

好好理解一下拓撲排序演算法吧

自考/數據結構期末考試真題

數據結構自考,自考 數據結構期末考試真題

畫圖說明步驟
更多圖示: https://dwz.cn/r4lCXEuL
數據結構期末考試真題

拓撲排序不唯一~


您的分享是我們最大的動力!

更多相關文章
  • 學了一些linux下的網路相關的命令,但是網路本身是啥,不知道啊, 所以只好找個ccna的網路知識,學一學,太難了我 網路種類: 乙太網 ARPA FR幀中繼 frame relay ATM交換機 網路範圍: 區域網 廣域網(也就俗稱的網際網路) 網路定義:通過物理線路將所有的終端設備連接到一起,並實 ...
  • linux學習 看完了基礎篇,下麵來看進階篇 我好想哭看這的時候,好多只是聽說過,但完全沒有試過,感覺自己懂得有點少,就是缺乏一些知識儲備,也就是必須知道了某些或學過了某些知識才適合來看這一部分,看得太早了,不過看看也好,以後再見到就不陌生了。這篇主要就是在linux編寫程式,調試程式,優化性能,這 ...
  • OJ 全名 online judge 線上判題系統,對於從事編程競賽的人來說一點都不陌生,今天我們討論的是怎麼樣自定義搭建 推薦的開源的OJ有hustOJ,JNOJ 因為hustOJ 是一鍵安裝腳本,對於安裝前的要求比較高,所以這一次我們使用jnoj 源代碼和自定義的安裝過程都在 倉庫地址 配置LA ...
  • MRAM是一種以電阻為存儲方式結合非易失性及隨機訪問兩種特性,可以兼做記憶體和硬碟的新型存儲介質。寫入速度可達NAND快閃記憶體的數千倍,此外,其製作工藝要求低,良品率高,可以很好的控製成本。在壽命方面,由於MRAM特殊的存儲方式,產品的壽命耐久性也遠超傳統RAM。大規模普及仍面臨挑戰 毫無疑問,MRAM因 ...
  • 學習使用linux 偶然間看到一篇介紹linux的使用,於是看了看,整體看完,雖然看的有些懵✒,但還是堅持看完了基礎部分,並做了一些摘要。 man頁面所屬的分類標識 常用的是分類1和分類3 (1)、用戶可以操作的命令或者是可執行文件 (2)、系統核心可調用的函數與工具等 (3)、一些常用的函數與數據 ...
  • Linux的預設管理員名即是root,只需要知道ROOT密碼即可直接登錄SSH。禁止Root從SSH直接登錄可以提高伺服器安全性。經過以下操作後即可實現。本文適用於CentOS、Debian等Linux系統。 新建用戶 配置密碼 配置不允許root用戶直接登錄 修改相關文件 禁止root登陸 重啟s ...
  • 前言:學習的課程來自極客時間的專欄《趣談 Linux 操作系統》,作者用形象化的比喻和豐富的圖片讓課程變得比較易懂,為了避免知識看過就忘,打算通過寫學習筆記的形式記錄自己的學習過程。Linux 系統的相關介紹不再贅述,目前比較熱門的技術,比如雲計算、虛擬化、容器、大數據、人工智慧,幾乎都是基於 Li ...
  • 數據定義 資料庫 表 擴展 函數 索引 許可權控制 運行分析 運行維護 配置 備份還原 其他 時間處理 psql ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...