【資料結構——圖的遍歷】
- 一、介紹
- 二、深度優先搜索DFS(Depth First Search)
- 1、深度優先搜索遍歷的程序
- 2、深度優先搜索遍歷的演算法實作
- 3、非連通圖的深度優先搜索遍歷
- 三、廣度優先搜索BFS(Breadth First Search)
- 1、介紹
- 2、演算法思想和描述
一、介紹
圖的遍歷：從圖的某個頂點出發，依次訪問圖中所有的頂點，每個頂點被訪問一次且僅訪問一次，
防止多次訪問某一個頂點的思路：設定輔助陣列visited[n],用來標記每個被訪問的頂點，
初始化狀態為visited[n]=0;如果頂點被訪問到，則修改輔助陣列的值 ：visited[i]=1
二、深度優先搜索DFS(Depth First Search)
1、深度優先搜索遍歷的程序
深度優先搜索生成樹： 對于無向連通生成圖，如果將第一次深度優先搜索時前進操作經過的邊保留下來則可以構成一棵深度優先搜索生成樹
2、深度優先搜索遍歷的演算法實作
遞回的搜索演算法：dfs(G,v)
/*圖的深度優先搜索遍歷偽碼*/
dfs(G, v)
{
訪問v，并對v作已訪問標記
訪問v的鄰接點w,若w未被訪問，則繼續呼叫dfs(G,w)
}
/*圖的深度優先搜索遍歷偽碼*/
bool visited[MVNum];//標志訪問陣列，初值為false
void DFS(Graph G, int v)
{//從第v個頂點開始深度優先搜索遍歷圖G
cout << v;visited[v] = true;//訪問第一個頂點v ,訪問標志符置為true
for (w = FirstAdjVex(G,v);w >= 0;w = NextAdjVex(G, v, w))
{
if (!visited[w])
DFS(G, w);//對v的沒有被訪問的頂點遞回遍歷
}
}
//FirstAdjVex(G,v)表示v的第一個鄰接點
//NextAdjVex(G, v, w)表示v相對于w的下一個鄰接點
采用鄰接矩陣表示的圖的DFS:
/*鄰接矩陣的存盤結構*/
typedef struct
{
VerTexType vexs[MVNum];//頂點表
ArcType arcs[MVNum][MVNum];//鄰接矩陣
int vexnum, arcnum;//當前圖的頂點數和邊數
}AMGraph;
/*鄰接矩陣表示的圖的DFS*/
void DFS_AM(AMGraph G, int v)
{//從第v個頂點依次遍歷圖G
cout << v;//訪問第v個頂點
visited[v] = true;//訪問標志符陣列置為true
for (w = 0;w <= G.vexnum;++w)//依次檢查鄰接矩陣v所在行
{
if ((G.arcs[v][w] != 0) && (!visited[w]))
DFS_AM(G, w);//w是v的鄰接點，如果w未被訪問，則呼叫DFS_AM
}
}
用鄰接矩陣表示圖：查找每個結點的鄰接點的時間復雜度為O(n的平方），加上初始化visited陣列時間復雜度O(n),DFS的時間復雜度為O(n的平方）
采用鄰接表表示圖的DFS
/*圖的鄰接表的存盤定義*/
//弧的結點結構
#define MVNum 100 //最大的頂點數
typedef struct ArcNode
{
int adjvex; //該邊所指的頂點的位置
struct ArcNode* nextarc; //指向下一條邊的指標
OtherInfo info; //和邊相關的資訊
}ArcNode;
//頂點的結點結構
typedef struct VNode
{
VertexType data;//頂點資訊
ArcNode* firstarc;//指向第一條依附該頂點的邊
}VNode, AdjList[MVNum];//AdjList表示鄰接表型別
//AdjList v相當于VNode v[MVNum]
//圖的結構定義（鄰接表）
typedef struct
{
AdjList vertices;//vertices是vertex的復數
int vexnum, arcnum;//圖的當前頂點數和邊數
}ALGraph;
/*采用鄰接表表示圖的DFS*/
void DFS_AL(ALGraph G, int v)
{//圖G為鄰接表型別，從第v個結點出發DFS圖G
cout << v;//訪問第v個頂點
visited[v] = true;//置訪問標志符為true
p = G.vertices[v].firstarc;//p指向v的邊鏈表的第一個邊結點
while (p != NULL)//邊結點非空
{
w = p->adjvex;//w是p的鄰接點下標
if (!visited[w])
DFS_AL(G, w);//如果w未訪問，則遞回呼叫DFS_AL
p = p->nextarc;//p指向下一個邊結點
}
}
用鄰接表表示圖：查找每個結點的鄰接點的時間復雜度為O（e),加上初始化visited陣列時間復雜度O(n),DFS的時間復雜度為O(n+e)
3、非連通圖的深度優先搜索遍歷
演算法思想：
1、將圖中每個頂點的訪問標志設為false
2、依次（頂點編號）搜索圖中每個頂點，如果未被訪問，則以該頂點為起點，進行深度優先搜索遍歷，否則繼續檢查下一個頂點，直至圖中所有頂點都被訪問，
/*非連通圖G的深度優先搜索遍歷*/
void DFSTraverse(Graph G)
{
for (v = 0;v < G.vexnum;++v)
visited[v] = false;//訪問標志陣列初始化
for (v = 0;v < G.vexnum;++v)
if (!visited[v])
DFS(G, v);//對尚未訪問的頂點呼叫DFS
}
三、廣度優先搜索BFS(Breadth First Search)
1、介紹
類似于樹的按層次遍歷
1、從圖中某個頂點v出發，訪問v
2、依次訪問v的各個未被訪問過的鄰接點
3、分別從這些鄰接點出發依次訪問他們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點” 被訪問
4、重復3，直到所有已被訪問的頂點的鄰接點都被訪問到，
2、演算法思想和描述
/*按廣度優先非遞回遍歷連通圖G*/
void BFS(Graph G, int v)
{
cout << v;visited[v] = true;//訪問第v個頂點
InitQueue(Q);//輔助佇列Q初始化，置空
EnQueue(Q, v);//v進隊
while (!QueueEmpty(Q))//佇列非空
{
DeQueue(Q, u);//隊頭元素出隊并置為u
for (w = FirstAdjVex(G, u);w>=0;w=NextAdjVex(G,u,w))
if (!visited[w])//w為u的尚未訪問的鄰接頂點
{
cout << w;visited[w] = true;//置訪問標志陣列分量為true
EnQueue(Q, w);//w進隊
}
}
}
對無向連通圖：如果將一次廣度優先搜索時前進操作經過的邊保留下來則可構成一棵廣度優先搜索生成樹，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/216281.html
標籤：其他
上一篇：web爬蟲
下一篇：慢查詢的疑問及應用