隨筆札記

先介紹本文章所使用的圖形結構為下:

深度優先搜尋法(Depth-First Search)

1. 先拜訪起始點V。
2. 選擇與V相鄰但尚未被拜訪的頂點W。
3. 再以W為起始點。
4. 重複步驟1到3，直到所有頂點皆被訪問過結束。

可以用Stack或Recursive的方式來實現深度優先搜尋法。

以本文張的圖形結構深度優先搜尋會如下圖:

廣度優先搜尋法(Breadth-First Search)

1. 先拜訪起始點V。
2. 拜訪與V相鄰且未被訪問的頂點。
3. 重複步驟1與2，直到所有與V相鄰的頂點皆被訪問後尋找下一層頂點。

可以用queue來實現廣度優先搜尋法。

以本文張的圖形結構廣度優先搜尋會如下圖:

完整程式碼:

// Depth First Search(DFS) and Breadth First Search(BFS)

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct node_list {
	int vertex;
	struct node_list *list;
}Node;

Node *adjacentlist[MAX + 1];//伴隨List
int isvisited[MAX+1], queen[MAX + 1], totalnum = 0;
//isvisited表示此節點是否曾被訪問過  
Node *searchlast(Node*); //找List中最後一個link
void DFS(int);//以Recursive來實現DFS
void BFS(int);//以queue來實現BFS
void Buildlist();//初始化及將.dat中的adjacent matrix轉換成adjacent list
void Showlist();//顯示adjacent list

int main() {
	Buildlist();
	Showlist();
	printf("--------------------------------\n");
	printf("Depth First Search Path:");
	DFS(0);
	printf("\nBreadth First Search Path:");
	BFS(0);
}

void Buildlist() {
	int connect = 0;
	Node *last;
	FILE *fp = fopen("adjacent_matrix.dat","r");
	if (fp == NULL) {
		perror("adjacent_matrix.dat");
		exit(0);
		
	}
	fscanf(fp, "%d", &totalnum);

	for (int index = 0; index < totalnum; index++) {
		isvisited[index] = 0;
		adjacentlist[index] = (Node*)calloc(1, sizeof(Node));
		adjacentlist[index]->list = NULL;
		adjacentlist[index]->vertex = index+1;
	}//初始化及宣告記憶體空間給adjacent list的head

	for (int i = 0; i < totalnum; i++) {
		for (int j = 0; j < totalnum; j++) {
			if (fscanf(fp, "%d", &connect) != EOF) {
				if (connect == 1) {
					Node *node = (Node*)calloc(1, sizeof(Node));
					node->vertex = j + 1;
					last = searchlast(adjacentlist[i]);
					last->list = node;
				}
			}
		}
	}//將.dat中的adjacent matrix，轉換成adjacent list

}

void Showlist() {//顯示adjacent list
	Node *ptr;
	printf("Adjacnet List\n");
	printf("--------------------------------\n");
	for (int index = 0; index < totalnum; index++) {
		printf("V%2d", index+1);
		ptr = adjacentlist[index]->list;
		while (ptr != NULL) {
			printf(" --> ");
			printf("V%2d", ptr->vertex);
			ptr = ptr->list;
		}
		printf("\n");
	}
}

void DFS(int v) {//以Recursive來實現DFS
	Node *ptr;
	int w;
	printf("V%d ", adjacentlist[v]->vertex); //訪問此頂點
	isvisited[v] = 1;//記錄已被訪問
	ptr = adjacentlist[v]->list;//尋找此頂點的下一個相鄰頂點
	
	do{
		w = ptr->vertex - 1;
		if (!isvisited[w]) {
			DFS(w);//用recursive的方式更深層找未探索過的頂點
		}
		else {
			ptr = ptr->list; //尋找頂點w中的下一個相鄰頂點
		}

	} while (ptr != NULL); //直到頂點w所有的相鄰點都訪問過結束

}

void BFS(int v) {//以queue來實現BFS
	int qufront = 0,qurear=1;
	int *queue = (int*)calloc(MAX+1, sizeof(int));
	for (int cnt = 0; cnt < totalnum; cnt++) isvisited[cnt] = 0;
	//初始化isvisited，因為在DFS中已經使用過了。

	Node *prt = adjacentlist[0];
	isvisited[0] = 1;
	printf("V%d ", prt->vertex);
	//直接從起始點0開始訪問

	do {
		//判斷NULL例外狀況
		if (prt == NULL) {
			prt = adjacentlist[*(queue + qufront)-1];
			qufront++;//front
		}
		else {
			prt = prt->list;
		}

		//紀錄
		if (prt != NULL) {
			if (isvisited[prt->vertex - 1]==0) {
				qurear++;//rear
				*(queue + qurear) = prt->vertex;
				printf("V%d ", prt->vertex);
				isvisited[prt->vertex - 1] = 1;
			}
		}

	}while (qurear<totalnum);//直到所有頂點都被訪問過

}

Node *searchlast(Node* node) {//找這個list的最後一個node
	while (node->list != NULL) {
		node = node->list;
	}
	return node;//將最後一個node的位址回傳回去
}

 

執行結果:

_______________________________________________

我們透過閱讀，拼湊出真實世界的面貌，
並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。