算法系列15天速成 第十四天 圖【上】
今天來分享一下圖，這是一種比較復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，之所以復(fù)雜是因?yàn)樗麄兊臄?shù)據(jù)元素之間的關(guān)系是任意的，而不像樹那樣 被幾個(gè)性質(zhì)定理框住了，元素之間的關(guān)系還是比較明顯的，圖的使用范圍很廣的，比如網(wǎng)絡(luò)爬蟲，求最短路徑等等，不過大家也不要膽怯，
越是復(fù)雜的東西越能體現(xiàn)我們碼農(nóng)的核心競(jìng)爭(zhēng)力。
既然要學(xué)習(xí)圖，得要遵守一下圖的游戲規(guī)則。
一： 概念
圖是由“頂點(diǎn)”的集合和“邊”的集合組成。記作：G=（V,E)；
<1> 無向圖
就是“圖”中的邊沒有方向，那么（V1,V2)這條邊自然跟（V2，V1）是等價(jià)的，無向圖的表示一般用”圓括號(hào)“。
<2> 有向圖
“圖“中的邊有方向，自然<V1,V2>這條邊跟<V2,V1>不是等價(jià)的，有向圖的表示一般用"尖括號(hào)"表示。
<3> 鄰接點(diǎn)
一條邊上的兩個(gè)頂點(diǎn)叫做鄰接點(diǎn)，比如（V1，V2），（V1，V3），（V1，V5），只是在有向圖中有一個(gè)“入邊，出邊“的
概念，比如V3的入邊為V5，V3的出邊為V2，V1，V4。
<4> 頂點(diǎn)的度
這個(gè)跟“樹”中的度的意思一樣。不過有向圖中也分為“入度”和“出度”兩種，這個(gè)相信大家懂的。
<5> 完全圖
每?jī)蓚€(gè)頂點(diǎn)都存在一條邊，這是一種完美的表現(xiàn)，自然可以求出邊的數(shù)量。
無向圖：edges=n(n-1)/2;
有向圖：edges=n(n-1); //因?yàn)橛邢驁D是有邊的，所以必須在原來的基礎(chǔ)上"X2"。
<6> 子圖
如果G1的所有頂點(diǎn)和邊都在G2中，則G1是G2的子圖，具體不說了。
<7> 路徑，路徑長(zhǎng)度和回路（這些概念還是比較重要的）
路徑： 如果Vm到Vn之間存在一個(gè)頂點(diǎn)序列。則表示Vm到Vn是一條路徑。
路徑長(zhǎng)度： 一條路徑中“邊的數(shù)量”。
簡(jiǎn)單路徑： 若一條路徑上頂點(diǎn)不重復(fù)出現(xiàn)，則是簡(jiǎn)單路徑。
回路： 若路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則是回路。
簡(jiǎn)單回路： 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其它各頂點(diǎn)都不重復(fù)的回路則是簡(jiǎn)單回路。
<8> 連通圖和連通分量（針對(duì)無向圖而言的）
連通圖： 無向圖中，任意兩個(gè)頂點(diǎn)都是連通的則是連通圖，比如V1，V2，V4之間。
連通分量： 無向圖的極大連通子圖就是連通分量，一般”連通分量“就是”圖“本身，除非是“非連通圖”，
如下圖就是兩個(gè)連通分量。
<9> 強(qiáng)連通圖和強(qiáng)連通分量（針對(duì)有向圖而言）
這里主要注意的是“方向性“，V4可以到V3，但是V3無法到V4，所以不能稱為強(qiáng)連通圖。
<10> 網(wǎng)
邊上帶有”權(quán)值“的圖被稱為網(wǎng)。很有意思啊，呵呵。
二：存儲(chǔ)
圖的存儲(chǔ)常用的是”鄰接矩陣”和“鄰接表”。
鄰接矩陣： 手法是采用兩個(gè)數(shù)組，一個(gè)一維數(shù)組用來保存頂點(diǎn)信息，一個(gè)二維數(shù)組來用保存邊的信息，
缺點(diǎn)就是比較耗費(fèi)空間。
鄰接表： 改進(jìn)后的“鄰接矩陣”，缺點(diǎn)是不方便判斷兩個(gè)頂點(diǎn)之間是否有邊，但是相比節(jié)省空間。
三： 創(chuàng)建圖
這里我們就用鄰接矩陣來保存圖，一般的操作也就是：①創(chuàng)建，②遍歷
#region 鄰接矩陣的結(jié)構(gòu)圖
/// <summary>
/// 鄰接矩陣的結(jié)構(gòu)圖
/// </summary>
public class MatrixGraph
{
//保存頂點(diǎn)信息
public string[] vertex;
//保存邊信息
public int[,] edges;
//深搜和廣搜的遍歷標(biāo)志
public bool[] isTrav;
//頂點(diǎn)數(shù)量
public int vertexNum;
//邊數(shù)量
public int edgeNum;
//圖類型
public int graphType;
/// <summary>
/// 存儲(chǔ)容量的初始化
/// </summary>
/// <param name="vertexNum"></param>
/// <param name="edgeNum"></param>
/// <param name="graphType"></param>
public MatrixGraph(int vertexNum, int edgeNum, int graphType)
{
this.vertexNum = vertexNum;
this.edgeNum = edgeNum;
this.graphType = graphType;
vertex = new string[vertexNum];
edges = new int[vertexNum, vertexNum];
isTrav = new bool[vertexNum];
}
}
#endregion
<1> 創(chuàng)建圖很簡(jiǎn)單，讓用戶輸入一些“邊，點(diǎn)，權(quán)值"來構(gòu)建一下圖
#region 圖的創(chuàng)建
/// <summary>
/// 圖的創(chuàng)建
/// </summary>
/// <param name="g"></param>
public MatrixGraph CreateMatrixGraph()
{
Console.WriteLine("請(qǐng)輸入創(chuàng)建圖的頂點(diǎn)個(gè)數(shù)，邊個(gè)數(shù)，是否為無向圖(0,1來表示)，已逗號(hào)隔開。");
var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);
Console.WriteLine("請(qǐng)輸入各頂點(diǎn)信息：");
for (int i = 0; i < graph.vertexNum; i++)
{
Console.Write("\n第" + (i + 1) + "個(gè)頂點(diǎn)為:");
var single = Console.ReadLine();
//頂點(diǎn)信息加入集合中
graph.vertex[i] = single;
}
Console.WriteLine("\n請(qǐng)輸入構(gòu)成兩個(gè)頂點(diǎn)的邊和權(quán)值，以逗號(hào)隔開。\n");
for (int i = 0; i < graph.edgeNum; i++)
{
Console.Write("第" + (i + 1) + "條邊:\t");
initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();
int start = initData[0];
int end = initData[1];
int weight = initData[2];
//給矩陣指定坐標(biāo)位置賦值
graph.edges[start - 1, end - 1] = weight;
//如果是無向圖，則數(shù)據(jù)呈“二，四”象限對(duì)稱
if (graph.graphType == 1)
{
graph.edges[end - 1, start - 1] = weight;
}
}
return graph;
}
#endregion
<2>廣度優(yōu)先
針對(duì)下面的“圖型結(jié)構(gòu)”，我們?nèi)绾螐V度優(yōu)先呢？其實(shí)我們只要深刻理解"廣搜“給我們定義的條條框框就行了。 為了避免同一個(gè)頂點(diǎn)在遍歷時(shí)被多
次訪問，可以將”頂點(diǎn)的下標(biāo)”存放在sTrav[]的bool數(shù)組，用來標(biāo)識(shí)是否已經(jīng)訪問過該節(jié)點(diǎn)。
第一步：首先我們從isTrav數(shù)組中選出一個(gè)未被訪問的節(jié)點(diǎn)，如V1。
第二步：訪問V1的鄰接點(diǎn)V2，V3，V5，并將這三個(gè)節(jié)點(diǎn)標(biāo)記為true。
第三步：第二步結(jié)束后，我們開始訪問V2的鄰接點(diǎn)V1，V3，但是他們都是被訪問過的。
第四步：我們從第二步結(jié)束的V3出發(fā)訪問他的鄰接點(diǎn)V2，V1，V5，V4，還好V4是未被訪問的，此時(shí)標(biāo)記一下。
第五步：我們?cè)L問V5的鄰接點(diǎn)V1，V3，V4，不過都是已經(jīng)訪問過的。
第六步：有的圖中通過一個(gè)頂點(diǎn)的“廣度優(yōu)先”不能遍歷所有的頂點(diǎn)，此時(shí)我們重復(fù)（1-5）的步驟就可以最終完成廣度優(yōu)先遍歷。
#region 廣度優(yōu)先
/// <summary>
/// 廣度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void BFSTraverse(MatrixGraph graph)
{
//訪問標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問過的頂點(diǎn)
if (!graph.isTrav[i])
{
BFSM(ref graph, i);
}
}
}
/// <summary>
/// 廣度遍歷具體算法
/// </summary>
/// <param name="graph"></param>
public void BFSM(ref MatrixGraph graph, int vertex)
{
//這里就用系統(tǒng)的隊(duì)列
Queue<int> queue = new Queue<int>();
//先把頂點(diǎn)入隊(duì)
queue.Enqueue(vertex);
//標(biāo)記此頂點(diǎn)已經(jīng)被訪問
graph.isTrav[vertex] = true;
//輸出頂點(diǎn)
Console.Write(" ->" + graph.vertex[vertex]);
//廣度遍歷頂點(diǎn)的鄰接點(diǎn)
while (queue.Count != 0)
{
var temp = queue.Dequeue();
//遍歷矩陣的橫坐標(biāo)
for (int i = 0; i < graph.vertexNum; i++)
{
if (!graph.isTrav[i] && graph.edges[temp, i] != 0)
{
graph.isTrav[i] = true;
queue.Enqueue(i);
//輸出未被訪問的頂點(diǎn)
Console.Write(" ->" + graph.vertex[i]);
}
}
}
}
#endregion
<3> 深度優(yōu)先
同樣是這個(gè)圖，大家看看如何實(shí)現(xiàn)深度優(yōu)先，深度優(yōu)先就像鐵骨錚錚的好漢，遵循“能進(jìn)則進(jìn)，不進(jìn)則退”的原則。
第一步：同樣也是從isTrav數(shù)組中選出一個(gè)未被訪問的節(jié)點(diǎn)，如V1。
第二步：然后一直訪問V1的鄰接點(diǎn)，一直到走頭無路的時(shí)候“回溯”，路線為V1,V2,V3,V4,V5，到V5的時(shí)候訪問鄰接點(diǎn)V1，發(fā)現(xiàn)V1是訪問過的，
此時(shí)一直回溯的訪問直到V1。
第三步： 同樣有的圖中通過一個(gè)頂點(diǎn)的“深度優(yōu)先”不能遍歷所有的頂點(diǎn)，此時(shí)我們重復(fù)（1-2）的步驟就可以最終完成深度優(yōu)先遍歷。
#region 深度優(yōu)先
/// <summary>
/// 深度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void DFSTraverse(MatrixGraph graph)
{
//訪問標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問過的頂點(diǎn)
if (!graph.isTrav[i])
{
DFSM(ref graph, i);
}
}
}
#region 深度遞歸的具體算法
/// <summary>
/// 深度遞歸的具體算法
/// </summary>
/// <param name="graph"></param>
/// <param name="vertex"></param>
public void DFSM(ref MatrixGraph graph, int vertex)
{
Console.Write("->" + graph.vertex[vertex]);
//標(biāo)記為已訪問
graph.isTrav[vertex] = true;
//要遍歷的六個(gè)點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
if (graph.isTrav[i] == false && graph.edges[vertex, i] != 0)
{
//深度遞歸
DFSM(ref graph, i);
}
}
}
#endregion
#endregion
最后上一下總的代碼
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MatrixGraph
{
public class Program
{
static void Main(string[] args)
{
MatrixGraphManager manager = new MatrixGraphManager();
//創(chuàng)建圖
MatrixGraph graph = manager.CreateMatrixGraph();
manager.OutMatrix(graph);
Console.Write("廣度遞歸:\t");
manager.BFSTraverse(graph);
Console.Write("\n深度遞歸:\t");
manager.DFSTraverse(graph);
Console.ReadLine();
}
}
#region 鄰接矩陣的結(jié)構(gòu)圖
/// <summary>
/// 鄰接矩陣的結(jié)構(gòu)圖
/// </summary>
public class MatrixGraph
{
//保存頂點(diǎn)信息
public string[] vertex;
//保存邊信息
public int[,] edges;
//深搜和廣搜的遍歷標(biāo)志
public bool[] isTrav;
//頂點(diǎn)數(shù)量
public int vertexNum;
//邊數(shù)量
public int edgeNum;
//圖類型
public int graphType;
/// <summary>
/// 存儲(chǔ)容量的初始化
/// </summary>
/// <param name="vertexNum"></param>
/// <param name="edgeNum"></param>
/// <param name="graphType"></param>
public MatrixGraph(int vertexNum, int edgeNum, int graphType)
{
this.vertexNum = vertexNum;
this.edgeNum = edgeNum;
this.graphType = graphType;
vertex = new string[vertexNum];
edges = new int[vertexNum, vertexNum];
isTrav = new bool[vertexNum];
}
}
#endregion
/// <summary>
/// 圖的操作類
/// </summary>
public class MatrixGraphManager
{
#region 圖的創(chuàng)建
/// <summary>
/// 圖的創(chuàng)建
/// </summary>
/// <param name="g"></param>
public MatrixGraph CreateMatrixGraph()
{
Console.WriteLine("請(qǐng)輸入創(chuàng)建圖的頂點(diǎn)個(gè)數(shù)，邊個(gè)數(shù)，是否為無向圖(0,1來表示)，已逗號(hào)隔開。");
var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);
Console.WriteLine("請(qǐng)輸入各頂點(diǎn)信息：");
for (int i = 0; i < graph.vertexNum; i++)
{
Console.Write("\n第" + (i + 1) + "個(gè)頂點(diǎn)為:");
var single = Console.ReadLine();
//頂點(diǎn)信息加入集合中
graph.vertex[i] = single;
}
Console.WriteLine("\n請(qǐng)輸入構(gòu)成兩個(gè)頂點(diǎn)的邊和權(quán)值，以逗號(hào)隔開。\n");
for (int i = 0; i < graph.edgeNum; i++)
{
Console.Write("第" + (i + 1) + "條邊:\t");
initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();
int start = initData[0];
int end = initData[1];
int weight = initData[2];
//給矩陣指定坐標(biāo)位置賦值
graph.edges[start - 1, end - 1] = weight;
//如果是無向圖，則數(shù)據(jù)呈“二，四”象限對(duì)稱
if (graph.graphType == 1)
{
graph.edges[end - 1, start - 1] = weight;
}
}
return graph;
}
#endregion
#region 輸出矩陣數(shù)據(jù)
/// <summary>
/// 輸出矩陣數(shù)據(jù)
/// </summary>
/// <param name="graph"></param>
public void OutMatrix(MatrixGraph graph)
{
for (int i = 0; i < graph.vertexNum; i++)
{
for (int j = 0; j < graph.vertexNum; j++)
{
Console.Write(graph.edges[i, j] + "\t");
}
//換行
Console.WriteLine();
}
}
#endregion
#region 廣度優(yōu)先
/// <summary>
/// 廣度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void BFSTraverse(MatrixGraph graph)
{
//訪問標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問過的頂點(diǎn)
if (!graph.isTrav[i])
{
BFSM(ref graph, i);
}
}
}
/// <summary>
/// 廣度遍歷具體算法
/// </summary>
/// <param name="graph"></param>
public void BFSM(ref MatrixGraph graph, int vertex)
{
//這里就用系統(tǒng)的隊(duì)列
Queue<int> queue = new Queue<int>();
//先把頂點(diǎn)入隊(duì)
queue.Enqueue(vertex);
//標(biāo)記此頂點(diǎn)已經(jīng)被訪問
graph.isTrav[vertex] = true;
//輸出頂點(diǎn)
Console.Write(" ->" + graph.vertex[vertex]);
//廣度遍歷頂點(diǎn)的鄰接點(diǎn)
while (queue.Count != 0)
{
var temp = queue.Dequeue();
//遍歷矩陣的橫坐標(biāo)
for (int i = 0; i < graph.vertexNum; i++)
{
if (!graph.isTrav[i] && graph.edges[temp, i] != 0)
{
graph.isTrav[i] = true;
queue.Enqueue(i);
//輸出未被訪問的頂點(diǎn)
Console.Write(" ->" + graph.vertex[i]);
}
}
}
}
#endregion
#region 深度優(yōu)先
/// <summary>
/// 深度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void DFSTraverse(MatrixGraph graph)
{
//訪問標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問過的頂點(diǎn)
if (!graph.isTrav[i])
{
DFSM(ref graph, i);
}
}
}
#region 深度遞歸的具體算法
/// <summary>
/// 深度遞歸的具體算法
/// </summary>
/// <param name="graph"></param>
/// <param name="vertex"></param>
public void DFSM(ref MatrixGraph graph, int vertex)
{
Console.Write("->" + graph.vertex[vertex]);
//標(biāo)記為已訪問
graph.isTrav[vertex] = true;
//要遍歷的六個(gè)點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
if (graph.isTrav[i] == false && graph.edges[vertex, i] != 0)
{
//深度遞歸
DFSM(ref graph, i);
}
}
}
#endregion
#endregion
}
}
代碼中我們構(gòu)建了如下的“圖”。
- 算法系列15天速成——第十三天 樹操作【下】
- 算法系列15天速成 第十二天 樹操作【中】
- 算法系列15天速成 第十一天 樹操作（上）
- 算法系列15天速成 第十天 棧
- 算法系列15天速成 第八天 線性表【下】
- 算法系列15天速成 第九天 隊(duì)列
- 算法系列15天速成 第七天 線性表【上】
- 算法系列15天速成 第六天 五大經(jīng)典查找【下】
- 算法系列15天速成 第五天 五大經(jīng)典查找【中】
- 算法系列15天速成 第四天 五大經(jīng)典查找【上】
- 算法系列15天速成 第三天 七大經(jīng)典排序【下】
- 算法系列15天速成 第二天 七大經(jīng)典排序【中】
- 算法系列15天速成 第一天 七大經(jīng)典排序【上】
- 算法系列15天速成——第十五天 圖【下】（大結(jié)局）
相關(guān)文章
Telnet協(xié)議是TCP/IP協(xié)議族中的一員，是Internet遠(yuǎn)程登錄服務(wù)的標(biāo)準(zhǔn)協(xié)議和主要方式，Telnet是常用的遠(yuǎn)程控制Web服務(wù)器的方法，本文給大家分享yum安裝telnet的步驟，感興趣的朋友一起看看吧2020-05-05
git分支(branch)操作相關(guān)命令及分支命令的使用
這篇文章主要介紹了git分支(branch)操作相關(guān)命令及分支命令的使用的相關(guān)資料,需要的朋友可以參考下2017-10-10
本文詳細(xì)講解了git?stash(儲(chǔ)藏)的用法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
php/asp/asp.net中判斷百度移動(dòng)和PC蜘蛛的實(shí)現(xiàn)代碼
這篇文章主要介紹了php/asp/asp.net中判斷百度移動(dòng)和PC蜘蛛的實(shí)現(xiàn)代碼,需要的朋友可以參考下2015-09-09
提高github下載速度的方法可達(dá)到2MB/s(100%有效)
這篇文章主要介紹了提高github下載速度的方法可達(dá)到2MB/s(100%有效),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
學(xué)習(xí)編程的人對(duì)Get方法和Post方法并不陌生吧，GET是從服務(wù)器上獲取數(shù)據(jù)，POST是向服務(wù)器傳送數(shù)據(jù)，不了解的朋友可以詳細(xì)參考下2013-10-10
搭建websocket消息推送服務(wù),必須要考慮的幾個(gè)問題
面對(duì)各種新場(chǎng)景對(duì)websocket功能和性能越來越高的需求，不同的團(tuán)隊(duì)有不同的選擇，下面給大家分享構(gòu)建websocket服務(wù)時(shí)必須要考慮的一些技術(shù)特性以及能顯著提高用戶體驗(yàn)的功能，感興趣的朋友跟隨小編一起看看吧2020-04-04
瀏覽器的后退按鈕使得我們能夠方便地返回以前訪問過的頁(yè)面，它無疑非常有用。但有時(shí)候我們不得不關(guān)閉這個(gè)功能，以防止用戶打亂預(yù)定的頁(yè)面訪問次序。2014-09-09
vscode使用markdown無法預(yù)覽網(wǎng)絡(luò)圖片的解決方法
本文主要介紹了vscode使用markdown無法預(yù)覽網(wǎng)絡(luò)圖片的解決方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
自定義?Github?Action?庫(kù)實(shí)戰(zhàn)詳解
這篇文章主要為大家介紹了自定義?Github?Action?庫(kù)實(shí)戰(zhàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09