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

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

圖的基本概念 首先,你要明確圖是什麼樣子的,就是下麵這個樣子的 圖的定義與術語 有向圖和無向圖 直接對比圖就可以看出來,有向圖和無向圖的區別了,這個沒有什麼難的。 有向圖和無向圖的表示法有略微的區別,註意看 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
數據結構期末考試真題

拓撲排序不唯一~


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

-Advertisement-
Play Games
更多相關文章
  • 學了一些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 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...