資料結構 第七章（學習筆記三（圖的周遊））

圖的周遊

• • 圖的周遊
  • 圖的周遊之深度優先探索
  • • 深度優先探索
    • 具體實作思路
    • 執行個體
    • 參考代碼實作
  • 圖的周遊之廣度優先探索
  • • 廣度優先探索
    • 具體實作思路
    • 執行個體
    • 參考代碼實作
  • DFS&BFS實作圖的周遊完整代碼

圖的周遊

從圖中某一頂點出發，按照某種搜尋方法沿着圖中的邊對圖中的所有頂點通路一次且僅通路一次。

圖的周遊之深度優先探索

深度優先探索

深度優先搜尋(DepthFirstSearch) ，也有稱為深度優先周遊,簡稱為DFS。

拿找鑰匙例子來說, 無論從哪一間房間開始都可以,将房間内的牆角 、床頭櫃、床上、床下、衣櫃、電視櫃等挨個尋找,做到不放過任何一個死角,當所有的抽屜、 儲藏櫃等全部都找遍,接着再尋找下一個房間。

具體實作思路

首先通路起始頂點v；

接着由v出發通路v的任意一個 鄰接且未被通路 的鄰接頂點Wi；

然後再通路與Wi 鄰接且未被通路 的任意頂點 yi；

若w沒有鄰接且未被通路的頂點時, 退回到它的上一層頂點v；

重複上述過程,直到所有頂點被通路為止。

執行個體

遵循右手原則周遊，藍色線為走的線。

參考代碼實作

bool visited[MAX_TREE_SIZE];
void DFSTraverse(Graph G){
    for(int i = 0; i < G.vexnum; i++)
        visited[i] = FALSE;
    for(int i = 0; i < G.vexnum; i++)
        if(!visited[i])
            DFS(G, i);
}
void DFS (Graph G, int v){
    visit(v);
    visited[v] = TRUE;
    for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    	if(!visited[i])        i
            DFS(G, w);
}
           

圖的周遊之廣度優先探索

廣度優先探索

廣度優先搜尋（BreadthFirstSearch)，又稱為廣度優先周遊，簡稱 BFS。

我們還用找鑰匙的例子來講，運用深度優先周遊意味着要先徹底查找完一個房間再開始另一個房間，但我們知道，鑰匙放在沙發地下等特殊角落的可能性極低，是以我們運用新的方親：先看看鑰匙是否放在各個房間的明顯位置，如果沒有，再看看各個房間的抽屜有沒有。這樣逐漸擴大查找的範圍的方式我們稱為廣度優先搜尋 。

具體實作思路

首先通路起始頂點v；

接着由出發依次通路v的各個 未被通路過 的鄰接頂點W1, W2….Wi；

然後依次通路W1, W2…,Wi 的所有 未被通路過 的鄰接頂點；

在從這些通路過的頂點出發，通路它們所有 未被通路過的 鄰接頂點；

以此類推……；

執行個體

參考代碼實作

//鄰接表的廣度優先搜尋
bool visited[MAX_TRUE_SIZE];		//輔助标記數組
void BFSTraverse(Mgraph G){
    int i, j;
    Queue Q;		
    for( i = 0; i < G.vexnum; i++)		//将輔助标記數組全部初始化為FALSE, G.vexnum表示頂點數
    {
        visited[i] = FALSE;
    }
    initQueue( &Q);		//初始化隊列
    for( i = 0; i < G.vexnum; i++){
        if(!visited[i])	{
            printf("%c  ", G.vetices[i].data);	//通路頂點
            visited[i] = TRUE;
            EnQueue(&Q, i);
            while(!QueueEmpty(Q)){
                DeQueue(&Q, i);
                ArcNode P = G.AdjList[i].first;
                while(p != NULL && !visited[i])		// 單連結清單指針為非NULL 且 未被通路
                {
                    printf("%c  ", G.vetices[p.adjvex].data);	//通路頂點
                    visited[j] = TRUE;
                    EnQueue(&Q, j);
                }
            }    
        }
    }
}
           

DFS&BFS實作圖的周遊完整代碼

#include<stdio.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int Boolean;

typedef char VertexType;//頂點類型
typedef int EdgeType;//邊的權值類型

#define MAXSIZE 9
#define MAXEDGE 15
#define MAXVEX 9
#define INFINTY 65535

typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

typedef struct {
	int data[MAXSIZE];
	int front;
	int rear;
}Queue;

Status InitQueue(Queue* Q){
	Q->front = 0;
	Q->rear = 0;
	return  OK;
}

/* 若隊列Q為空隊列,則傳回TRUE,否則傳回FALSE */
Status QueueEmpty(Queue Q){
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}

/* 若隊列未滿，則插入元素e為Q新的隊尾元素 */
Status EnQueue(Queue* Q, int e){
	if ((Q->rear + 1) % MAXSIZE == Q->front)
		return ERROR;
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return  OK;
}

/* 若隊列不空，則删除Q中隊頭元素，用e傳回其值 */
Status DeQueue(Queue* Q, int* e){
	if (Q->front == Q->rear)
		return ERROR;
	*e = Q->data[Q->front];	
	Q->front = (Q->front + 1) % MAXSIZE;
	return  OK;
}

void CreateMGraph(MGraph* G){
	int i, j;
	G->numEdges = 9;
	G->numVertexes = 8;
	G->vexs[0] = 'A';
	G->vexs[1] = 'B';
	G->vexs[2] = 'C';
	G->vexs[3] = 'D';
	G->vexs[4] = 'E';
	G->vexs[5] = 'F';
	G->vexs[6] = 'G';
	G->vexs[7] = 'H';

	for (i = 0; i < G->numVertexes; i++){
		for (j = 0; j < G->numVertexes; j++){
			G->arc[i][j] = 0;
		}
	}

	G->arc[0][1] = 1;
	G->arc[0][2] = 1;

	G->arc[1][3] = 1;
	G->arc[1][4] = 1;

	G->arc[2][5] = 1;
	G->arc[2][6] = 1;

	G->arc[3][7] = 1;

	G->arc[4][7] = 1;

	G->arc[5][6] = 1;

	for (i = 0; i < G->numVertexes; i++){
		for (j = i; j < G->numVertexes; j++){
			G->arc[j][i] = G->arc[i][j];
		}
	}
}

Boolean visited[MAXVEX]; /* 通路标志的數組 */

/* 鄰接矩陣的深度優先遞歸算法 */
void DFS(MGraph G, int i){
	int j;
	visited[i] = TRUE;
	printf("%c ", G.vexs[i]);
	for (j = 0; j < G.numVertexes; j++)
		if (G.arc[i][j] == 1 && !visited[j])
			DFS(G, j);
}

/* 鄰接矩陣的深度周遊操作 */
void DFSTraverse(MGraph G){
	int i;
	for (i = 0; i < G.numVertexes; i++)
		visited[i] = FALSE;
	for (i = 0; i < G.numVertexes; i++)
		if (!visited[i])
			DFS(G, i);
}

/* 鄰接矩陣的廣度周遊算法 */
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for (i = 0; i < G.numVertexes; i++)
		visited[i] = FALSE;
	InitQueue(&Q);
	for (i = 0; i < G.numVertexes; i++){
		if (!visited[i]){
			visited[i] = TRUE;
			printf("%c ", G.vexs[i]);
			EnQueue(&Q, i);
			while (!QueueEmpty(Q)){
				DeQueue(&Q, &i);
				for (j = 0; j < G.numVertexes; j++){
					if (G.arc[i][j] == 1 && !visited[j]){
						visited[j] = TRUE;
						printf("%c ", G.vexs[j]);
						EnQueue(&Q, j);
					}
				}
			}
		}
	}
}

int main(){
	MGraph G;
	CreateMGraph(&G);
	printf("\n深度周遊：");
	DFSTraverse(G);
	printf("\n廣度周遊：");
	BFSTraverse(G);

	return 0;
}