Flood Fill—DFS和BFS算法的執行個體講解（C）（島嶼數量I）

一、前言：

初學程式設計的小白學習完基礎算法總之不知道有什麼用。是以本篇從一個有趣的leetcode題目講解Flood fill算法，即所熟知的DFS廣度優先和BFS深度優先算法。

二、題目：

三、簡介：

維基百科：Flood fill 算法是從一個區域中提取若幹個連通的點與其他相鄰區域區分開（或分别染成不同顔色）的經典算法。因為其思路類似洪水從一個區域擴散到所有能到達的區域而得名。在 GNU Go 和掃雷中，Flood Fill算法被用來計算需要被清除的區域。

Flood fill算法其實就是：從一個區域中提取若幹個連通的點與其他相鄰區域區分開。從一個點擴散開，通過 “深度優先周遊” 或者 “廣度優先周遊” 找到與其連通的點，進而發現一片連着的區域。

解題：

https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/

本題解題思路就是：

1.從第一個點開始檢索，找到一個為1的數後，“島數”count+1，然從這個點開始對整個島進行“深度搜尋”或者“廣度搜尋”。

2.如果使用的深度搜尋，那麼在遞歸搜尋時将點設定為0或者其他不為1的數（防止重複計算）。

如果使用的廣度搜尋，在入隊時就将該點設定為0或者其他不為1的數（防止重複計算）。

3.然後一個島搜尋完後繼續進行搜尋，找到下一個為1的數後再重複上面步驟，直到周遊完整個二維數組，再無為1的點。最後的count就是“島數”。

四、算法代碼：

首先先看DFS和BFS實作的相關代碼。這裡總共有兩種方式存儲圖的資訊，一種是鄰接表，一種是鄰接矩陣。

當圖為稀疏結構時，也就是邊數遠小于節點數平方時，用鄰接表更加節省空間，鄰接表如：

Flood Fill—DFS和BFS算法的執行個體講解（C）（島嶼數量I）

當圖為稠密圖，也就是節點間連線很多時，用鄰接矩陣更加友善，如更加友善判斷兩點間有無邊：

Flood Fill—DFS和BFS算法的執行個體講解（C）（島嶼數量I）

DFS、BFS（鄰接表）

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#pragma warning(disable:4996)

#define MAX 10
#define INIFINITY 65535
#define TRUE 1
#define FALSE 0

typedef int Boole;  //布爾類型 存儲TRUE FALSE

Boole visited[MAX];    //通路标志數組 
					   //鄰接表結點定義

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

typedef struct EdgeNode  //邊表結點   存儲邊表資訊 
{
	int adjvex;		    //鄰接點域，存儲該頂點對應的下标 
	EdgeType weight;	//權值 
	struct EdgeNode *next;	//鍊域，指向下一個鄰接點 
}EdgeNode;

typedef struct VertexNode   //頂點表結點
{
	VertexType data;      //頂點域，存儲頂點資訊 
	EdgeNode *firstedge;	//邊表頭指針，指向此頂點的第一個鄰接點 
}VertexNode, AdjList[MAX];

typedef struct
{
	AdjList adjList;
	int numVertexes, numEdges;   //圖中目前頂點數和邊數 
}GraphAdjList, *GraphAdj;

typedef struct LoopQueue { //定義循環隊列結構體 
	int data[MAX];
	int front;
	int rear;   //注意每次隊尾标記指向最後一個元素的下一個位置 
}Queue, *LQueue;

void InitQueue(LQueue Q) {  //初始化隊列 
	Q->front = Q->rear = 0;
}

bool QueueisFull(LQueue Q) { //判斷隊列是否滿了
	if ((Q->rear + 1) % MAX == Q->front) {
		return true;  //已滿
	}
	else {
		return false;
	}
}

bool QueueisEmpty(LQueue Q) {//判斷隊列是否為空 
	if (Q->front == Q->rear) {
		return true;
	}
	return false;
}

void EnQueue(LQueue Q, int i) { //入隊列 
	if (!QueueisFull(Q)) {
		Q->data[Q->rear] = i;
		Q->rear = (Q->rear + 1) % MAX;  //隊尾指針後移 
	}
}

void DeQueue(LQueue Q, int *k) { //出隊列 
	if (!QueueisEmpty(Q)) {
		*k = Q->data[Q->front];
		Q->front = (Q->front + 1) % MAX;
	}
}

/*鄰接表建立*/
void create(GraphAdj G)
{
	int i, j, k;
	EdgeNode *e;
	printf("輸入頂點數和邊數:");
	scanf("%d%d", &G->numVertexes, &G->numEdges);
	getchar();  						//注意要清除緩沖 
	for (i = 0; i<G->numVertexes; i++)          //建立頂點表 
	{
		scanf("%c", &G->adjList[i].data);    //輸入頂點的符号 
		G->adjList[i].firstedge = NULL; 		//将邊表置空 
		getchar();
	}
	for (k = 0; k<G->numEdges; k++)             //建立邊表 
	{
		printf("輸入邊(Vi,Vj)上的頂點序号:");
		scanf("%d%d", &i, &j);
		/*使用頭插法加入邊表結點*/
		e = (EdgeNode *)malloc(sizeof(EdgeNode));   //生成結點 
		e->adjvex = j;
		e->next = G->adjList[i].firstedge;
		G->adjList[i].firstedge = e;

		e = (EdgeNode *)malloc(sizeof(EdgeNode));   //生成結點 
		e->adjvex = i;
		e->next = G->adjList[j].firstedge;
		G->adjList[j].firstedge = e;
	}
	printf("\n");
}

/*鄰接表的深度優先遞歸*/
void DFS(GraphAdj G, int i)
{
	EdgeNode *p;
	visited[i] = TRUE;         		//通路過了該頂點，标記為TRUE 
	printf("\t%c", G->adjList[i].data);
	p = G->adjList[i].firstedge;     //讓p指向邊表第一個結點 

	while (p)                      //在邊表内周遊 
	{
		if (!visited[p->adjvex])    //對未通路的鄰接頂點遞歸調用 
			DFS(G, p->adjvex);
		p = p->next;
	}
}

//鄰接表的深度周遊操作

void DFSTraverse(GraphAdj G)
{
	int i;
	for (i = 0; i<G->numVertexes; i++)
		visited[i] = FALSE;       //初始設定為未通路 
	for (i = 0; i<G->numVertexes; i++)
		if (!visited[i])       //對未通路的頂點調用DFS，若是連通圖隻會執行一次 
			DFS(G, i);
}

/*廣度優先周遊*/
void BFS(GraphAdj G) {
	Queue *Q = (LQueue)malloc(sizeof(Queue));
	for (int i = 0; i < G->numVertexes; i++) {
		visited[i] = FALSE;
	}
	InitQueue(Q);  //初始化隊列 
	for (int i = 0; i < G->numVertexes; i++) {
		visited[i] = TRUE;
		printf("\t%c", G->adjList[i].data);
		EnQueue(Q, i);

		while (!QueueisEmpty(Q)) {
			DeQueue(Q, &i);  //這裡不斷的修改i的值！！ 
			EdgeNode *e = G->adjList[i].firstedge;  //i頂點的鄰接連結清單的第一個結點
			while (e) {//e存在時，将e的所有鄰接點加入隊列,也就是周遊i的所有鄰接點 
				if (!visited[e->adjvex]) { // adjvex是e所表示的結點下标 
					visited[e->adjvex] = TRUE;
					printf("\t%c", G->adjList[e->adjvex].data);
					EnQueue(Q, e->adjvex); //将該結點入隊 
				}
				e = e->next; //周遊i的下一個鄰接點 
			}
		}
	}
}

int main()
{
	GraphAdjList G;
	create(&G);
	printf("深度優先周遊為：");
	DFSTraverse(&G);
	printf("\n");
	printf("廣度優先周遊為：");
	BFS(&G);
	printf("\n圖周遊完畢");

	return 0;
}

代碼中有個特别好的就是用getchar()來清空緩沖區，防止幹擾，個人非常喜歡這種處理方式，以前使用scanf前并沒有注意到這點。

DFS、BFS（鄰接矩陣）

#include <stdio.h>

#define MaxVex        100            //最大頂點數
#define INFINITY    65535        //表示∞
#define TRUE        1
#define    FALSE        0

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

typedef int            Bool;
Bool    visited[MaxVex];
 
typedef struct {
    VertexType    vexs[MaxVex];            //頂點數組
    EdgeType    arc[MaxVex][MaxVex];    //鄰接矩陣
    int    numVertexes, numEdges;            //目前圖中的結點數以及邊數
}MGraph;
 
//廣度優先周遊需要的循環隊列
typedef struct {
    int    data[MaxVex];
    int    front, rear;
}Queue;
 
/****************************************/
//隊列的相關操作
//初始化
void InitQueue(Queue *Q)
{
    Q->front = Q->rear = 0;
}
 
//入隊
void EnQueue(Queue *Q, int e)
{
    if ((Q->rear+1)%MaxVex == Q->front)
        return ;
 
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MaxVex;
}
 
//判空
Bool QueueEmpty(Queue *Q)
{
    if (Q->front == Q->rear)
        return TRUE;
    else
        return FALSE;
}
 
//出隊
void DeQueue(Queue *Q, int *e)
{
    if (Q->front == Q->rear)
        return ;
 
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MaxVex;
}

/****************************************/
//建立圖的鄰接矩陣
void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
 
    printf("輸入頂點數和邊數: ");
    scanf("%d%d", &G->numVertexes,&G->numEdges);
    fflush(stdin);
 
    printf("==============================\n");
    printf("輸入各個頂點:\n");
    for (i=0; i<G->numVertexes; ++i)
    {
        printf("頂點%d: ",i+1);
        scanf("%c", &G->vexs[i]);
        fflush(stdin);
    }
 
    for (i=0; i<G->numVertexes; ++i)
    {
        for (j=0; j<G->numVertexes; ++j)
            G->arc[i][j] = INFINITY;
    }
 
    printf("==============================\n");
    for (k=0; k<G->numEdges; ++k)
    {
        printf("輸入邊(vi, vj)中的下标i和j和權W: ");
        scanf("%d%d%d", &i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
}
 
//輸出
void DisMGraph(MGraph *G)
{
    int i, j, k;
    k = G->numVertexes;
    for (i=0; i<k; ++i)
    {
        for (j=0; j<k; ++j)
        {
            printf("%5d ", G->arc[i][j]);
        }
        putchar('\n');
    }
}
 
/****************************************/
//圖的深度優先周遊
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]!=INFINITY  &&  !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 (!visited[j] && G->arc[i][j]!=INFINITY)
                    {
                        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);
 
    printf("\n");
 
    return 0;
}

此題解答代碼（深度搜尋）：

void _numIslands(char** grid, int rowSize, int colSize, int i, int j){
    if(i < 0 || i >= rowSize || j < 0 || j >= colSize){
        return ;
    }
    
    if(grid[i][j] == '1'){
        grid[i][j] = '0';
        _numIslands(grid, rowSize, colSize, i-1, j);
        _numIslands(grid, rowSize, colSize, i+1, j);
        _numIslands(grid, rowSize, colSize, i, j-1);
        _numIslands(grid, rowSize, colSize, i, j+1);
    }
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    int cnt = 0;
    for(int i = 0; i < gridSize; i++){
        for(int j = 0; j < gridColSize[0]; j++){
            if(grid[i][j] == '1'){
                cnt++;
                _numIslands(grid, gridSize, gridColSize[0], i, j);
            }
        }
    }
    
    return cnt;
}

Flood Fill—DFS和BFS算法的執行個體講解（C）（島嶼數量I）

繼續閱讀

C語言DFS(4)____棋盤問題

POJ 1321棋盤問題（dfs）

前序周遊/二叉樹/LeetCode 5418

POJ_2481（樹狀數組）

Bloxorz I bfs

另類樹形結構的周遊題目--員工的重要性題目：題解：DFS和BFS

POJ - 2488 A Knight's Journey解題報告

HDU 1253 勝利大逃亡

第一次CSP模測第一題第二題第三題

LeetCode-Python-102. 二叉樹的層次周遊

Math類和Random類（Java）一、Math類3.141592653589793 2.718281828459045 0.8509035245341184 1.5707963267948966 90.0 3.141592653589793 1.0 2.718281828459045 8.0 1 2 1 0.6334082307247847 1 二、java.util.Random類

HDU 1067（HASH + BFS）

hdu 5487 Difference of Languages BFS Difference of Languages

Space Station Shielding(洪泛算法)

Leetcode——653. 兩數之和 IV - 輸入 BST

dfs深度優先搜尋_圖的深度優先搜尋（DFS）