這篇文章主要講解了“基本的視覺(jué)化方法有哪些”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“基本的視覺(jué)化方法有哪些”吧！

十多年建站經(jīng)驗(yàn)， 網(wǎng)站制作、網(wǎng)站建設(shè)客戶(hù)的見(jiàn)證與正確選擇。成都創(chuàng)新互聯(lián)公司提供完善的營(yíng)銷(xiāo)型網(wǎng)頁(yè)建站明細(xì)報(bào)價(jià)表。后期開(kāi)發(fā)更加便捷高效，我們致力于追求更美、更快、更規(guī)范。

首先，圖表是什么?

圖表由一組有限頂點(diǎn)或節(jié)點(diǎn)和一組連接這些頂點(diǎn)的邊組成，如果兩個(gè)頂點(diǎn)通過(guò)同一條邊互相連接，則稱(chēng)之為鄰接。下面是一些與圖表相關(guān)的基本定義，可以參考圖中示例。

• 順序：圖表中的頂點(diǎn)數(shù)

• 大小：圖表中的邊數(shù)

• 頂點(diǎn)度：入射到頂點(diǎn)的邊數(shù)

• 孤立頂點(diǎn)：未連接到圖中任何其它頂點(diǎn)的頂點(diǎn)

• 自循環(huán)：從頂點(diǎn)到自身的一條邊

• 有向圖：圖中所有的邊都有方向，來(lái)表示起點(diǎn)和終點(diǎn)

• 無(wú)向圖：圖的邊無(wú)方向

• 加權(quán)圖：圖的邊有權(quán)值

• 未加權(quán)圖：圖的邊無(wú)權(quán)值

圖1：圖表術(shù)語(yǔ)的可視化

1.廣度優(yōu)先搜索

圖2 ：廣度優(yōu)先搜索(BFS)遍歷動(dòng)畫(huà)

遍歷或搜索是圖表上執(zhí)行的基本操作之一。在廣度優(yōu)先搜索(BFS)中，從特定某個(gè)頂點(diǎn)開(kāi)始，在進(jìn)入下一層的頂點(diǎn)前先探索它當(dāng)前深度的所有相關(guān)信息。與樹(shù)不同，圖表可以包含循環(huán)(第一個(gè)和最后一個(gè)頂點(diǎn)是相同的路徑)。因此，必須跟蹤訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。在實(shí)現(xiàn)BFS時(shí)，應(yīng)使用隊(duì)列數(shù)據(jù)結(jié)構(gòu)。

圖2是一個(gè)示例圖的BFS遍歷的動(dòng)畫(huà)，注意一下頂點(diǎn)如何被發(fā)現(xiàn)(黃色)和被訪(fǎng)問(wèn)(紅色)。

應(yīng)用：

• 用于社交網(wǎng)絡(luò)搜索

• 用于確定最短路徑和最小生成樹(shù)

• 被搜索引擎爬網(wǎng)程序用于構(gòu)建網(wǎng)頁(yè)索引

• 用于查找對(duì)等網(wǎng)絡(luò)(如BitTorrent)中的可用鄰近節(jié)點(diǎn)

2.深度優(yōu)先搜索

圖3：為深度優(yōu)先搜索(DFS)的遍歷動(dòng)畫(huà)

在深度優(yōu)先搜索(DFS)中，從某個(gè)特定頂點(diǎn)開(kāi)始，回溯(backtracking)前，沿著每個(gè)分支盡可能搜索。DFS中，還需跟蹤訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。實(shí)現(xiàn)DFS時(shí)，使用堆棧數(shù)據(jù)結(jié)構(gòu)來(lái)支持回溯。

圖3對(duì)圖2中使用的同一個(gè)示例圖進(jìn)行DFS遍歷的動(dòng)畫(huà)，注意它如何遍歷到深度和回溯。

應(yīng)用：

• 用于查找兩個(gè)頂點(diǎn)之間的路徑

• 用于檢測(cè)圖中的循環(huán)

• 用于拓?fù)渑判?/p>

• 用于解決只有一種解決方案的難題(例如迷宮)

3.最短路徑

圖4動(dòng)畫(huà)顯示了從頂點(diǎn)1到頂點(diǎn)6的最短路徑

從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑是圖形中的路徑，因此應(yīng)使移動(dòng)邊的權(quán)重之和最小。圖4顯示了一個(gè)動(dòng)畫(huà)，其中確定了圖中頂點(diǎn)1到頂點(diǎn)6的最短路徑。

算法：

• Dijkstra的最短路徑算法

• 貝爾曼福特(Bellman–Ford)算法

應(yīng)用：

• 用于網(wǎng)絡(luò)中最小延遲路徑問(wèn)題的解決。

• 用于在Google或Apple地圖等軟件中查找一個(gè)位置到另一位置的路線(xiàn)。

• 用于抽象機(jī)器中，通過(guò)不同狀態(tài)之間的轉(zhuǎn)換來(lái)確定達(dá)到某一目標(biāo)狀態(tài)的方法。例如，可以用來(lái)確定如何用最少走法贏得一場(chǎng)比賽。

4.循環(huán)檢測(cè)

圖5：一個(gè)循環(huán)

循環(huán)是指圖中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。如果從一個(gè)頂點(diǎn)出發(fā)，沿著一條路徑，最后到達(dá)起始點(diǎn)，那么這條路徑就是一個(gè)循環(huán)。循環(huán)檢測(cè)是檢測(cè)這些循環(huán)的過(guò)程。圖5展示了遍歷一個(gè)循環(huán)的動(dòng)畫(huà)。

算法：

• 弗洛伊德循環(huán)檢測(cè)算法

• 布倫特算法

應(yīng)用：

• 用于基于消息的分布式算法

• 用于使用集群上的分布式處理系統(tǒng)處理大規(guī)模圖表

• 用于檢測(cè)并發(fā)系統(tǒng)中的僵局

• 在加密應(yīng)用程序中用于確定能夠?qū)⑾⒂成涞较嗤用苤迪⒌拿荑€

5.最小生成樹(shù)

圖6.顯示最小生成樹(shù)的動(dòng)畫(huà)

最小生成樹(shù)是圖表邊的子集，它連接所有邊權(quán)值最小和的頂點(diǎn)，不包含任何循環(huán)。圖6是一個(gè)獲得最小生成樹(shù)過(guò)程的動(dòng)畫(huà)。

算法：

• 普林演算法

• 克魯斯卡爾算法

應(yīng)用：

• 用于在計(jì)算機(jī)網(wǎng)絡(luò)中構(gòu)建廣播樹(shù)

• 用于基于圖表的聚類(lèi)分析

• 用于圖像分割

• 用于社會(huì)地理領(lǐng)域的區(qū)域化，將區(qū)域劃分為相鄰區(qū)域。

6.強(qiáng)連通分量

圖7：強(qiáng)連通分量

如果圖表中的每個(gè)頂點(diǎn)都能通過(guò)其他頂點(diǎn)到達(dá)，那么這個(gè)圖就是強(qiáng)連通的。圖7包含三個(gè)強(qiáng)連接分量，頂點(diǎn)分別用紅色、綠色和黃色表示。

算法：

• Kosaraju算法

• Tarjan強(qiáng)連通分量算法

應(yīng)用：

• 用于計(jì)算Dulmage Mendelsohn分解，是二分圖表邊的一種分類(lèi)。

• 用于社交網(wǎng)絡(luò)中，根據(jù)共同愛(ài)好，發(fā)現(xiàn)并推薦具有密切聯(lián)系的人。

7.拓?fù)渑判?/strong>

圖8：圖中頂點(diǎn)的拓?fù)渑判?/p>

圖表的拓?fù)渑判蚴菍?duì)其頂點(diǎn)進(jìn)行線(xiàn)性排序，因此對(duì)于排序中的每條有向邊(u,  v)，頂點(diǎn)u都在v之前。圖8顯示了頂點(diǎn)(1、2、3、5、4、6、7、8)的拓?fù)渑判蚴纠？梢钥吹剑旤c(diǎn)5應(yīng)在頂點(diǎn)2和3之后。同樣，頂點(diǎn)6應(yīng)該在頂點(diǎn)4和5之后。

算法：

• 卡恩算法

• 基于深度優(yōu)先算法

應(yīng)用：

• 用于指令調(diào)度

• 用于數(shù)據(jù)序列化

• 用于確定要在生成文件中執(zhí)行的編譯任務(wù)的順序

• 用于解析鏈接器中的符號(hào)依賴(lài)關(guān)系

8.圖著色

圖9：頂點(diǎn)著色

圖著色指的是在保證一定條件下給圖的元素分配顏色，頂點(diǎn)著色是最常用的圖形著色技術(shù)。在頂點(diǎn)著色中，我們嘗試用k種顏色給圖的頂點(diǎn)著色，任何兩個(gè)相鄰的頂點(diǎn)顏色都不相同。其他著色技術(shù)包括邊緣著色和面部著色。圖的色數(shù)是為圖著色所需顏色的最小數(shù)目。圖9顯示了用4種顏色為頂點(diǎn)著色。

算法：

• 使用廣度優(yōu)先搜索或深度優(yōu)先搜索的算法

• 貪婪著色

應(yīng)用：

• 用于制定時(shí)間表

• 用于分配移動(dòng)無(wú)線(xiàn)電頻率

• 用于建模和求解數(shù)獨(dú)游戲

• 用于檢查圖是否為二部圖

• 用于在相鄰國(guó)家或州的地圖上用不同顏色著色

9.最大流量

圖10：確定最大流量

可以將一個(gè)圖建模為以邊權(quán)值作為流量容量的流網(wǎng)絡(luò)。在最大流量問(wèn)題中，必須找到能獲得最大可能流量速率的流動(dòng)路徑。圖10是一個(gè)確定網(wǎng)絡(luò)的最大流量和最終流量值的動(dòng)畫(huà)示例。

算法：

• Ford-Fulkerson算法

• Edmonds–Karp算法

• Dinic算法

應(yīng)用：

• 用于航空公司調(diào)度，安排航班機(jī)組人員。

• 用于圖像分割，查找圖像中的背景和前景。

• 用來(lái)淘汰那些無(wú)法贏得比賽、無(wú)法與當(dāng)前隊(duì)伍優(yōu)秀者相匹敵的隊(duì)員。

10.匹配

圖11：二部圖匹配

圖表中的匹配是一組沒(méi)有共同頂點(diǎn)的邊(也就是說(shuō)，任何兩條都沒(méi)有共同頂點(diǎn))。如果一個(gè)匹配包含盡可能多頂點(diǎn)匹配的邊的最大數(shù)量，那么這個(gè)匹配被稱(chēng)為最大匹配。圖11顯示了獲得二部圖的完全匹配動(dòng)畫(huà)，該二部圖有兩組頂點(diǎn)，分別用橙色和藍(lán)色表示。

算法：

• 霍普克洛夫特-卡普(Hopcroft–Karp)算法

• 匈牙利(Hungarian)算法

• 開(kāi)花算法

應(yīng)用：

• 用于為新娘和新郎牽線(xiàn)搭橋(婚姻的穩(wěn)定問(wèn)題)

• 用于確定頂點(diǎn)覆蓋率

• 用于交通理論中解決出行資源配置和優(yōu)化問(wèn)題

感謝各位的閱讀，以上就是“基本的視覺(jué)化方法有哪些”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)基本的視覺(jué)化方法有哪些這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！