Tìm kiếm theo chiều rộng (BFS) là kỹ thuật duyệt đồ thị hoặc lưới bắt đầu từ một điểm, mở rộng đều các nút ở cùng một cấp độ trước khi đi sâu hơn. Thực hiện bằng cấu trúc hàng đợi, mỗi đỉnh chỉ được thêm vào một lần nên không cần hoàn tác trạng thái đã duyệt như trong DFS.

Cài đặt BFS tìm đường đi ngắn nhất

Đoạn mã sau minh họa cách tìm đường đi ngắn nhất trên lưới ô vuông sử dụng BFS:

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

#define MAX_SIZE 2500
#define GRID_MAX 51

typedef struct {
    int row;
    int col;
    int parent;
    int distance;
} QueueNode;

int main() {
    QueueNode queue[MAX_SIZE];
    int grid[GRID_MAX][GRID_MAX] = {0};
    int visited[GRID_MAX][GRID_MAX] = {0};
    int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    int rows, cols, startRow, startCol, targetRow, targetCol;
    scanf("%d %d", &rows, &cols);
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    scanf("%d %d %d %d", &startRow, &startCol, &targetRow, &targetCol);
    
    int front = 0, rear = 0;
    queue[rear].row = startRow;
    queue[rear].col = startCol;
    queue[rear].parent = -1;
    queue[rear].distance = 0;
    rear++;
    
    visited[startRow][startCol] = 1;
    
    while (front < rear) {
        int currentRow = queue[front].row;
        int currentCol = queue[front].col;
        
        for (int i = 0; i < 4; i++) {
            int newRow = currentRow + directions[i][0];
            int newCol = currentCol + directions[i][1];
            
            if (newRow < 1 || newRow > rows || newCol < 1 || newCol > cols) {
                continue;
            }
            
            if (grid[newRow][newCol] == 0 && visited[newRow][newCol] == 0) {
                visited[newRow][newCol] = 1;
                queue[rear].row = newRow;
                queue[rear].col = newCol;
                queue[rear].parent = front;
                queue[rear].distance = queue[front].distance + 1;
                rear++;
            }
            
            if (newRow == targetRow && newCol == targetCol) {
                printf("%d\n", queue[rear-1].distance);
                return 0;
            }
        }
        front++;
    }
    
    return 0;
}

Thuật toán sử dụng mảng 4 hướng để kiểm tra các ô lân cận, đánh dấu ô đã duyệt qua mảng visited và lưu khoảng cách từ điểm xuất phát trong mỗi nút hàng đợi.

Ứng dụng DFS tìm đường đi dài nhất

Tìm kiếm theo chiều sâu (DFS) phù hợp để khám phá tất cả các đường đi có thể. Ví dụ sau tìm đường đi có tổng trọng số lớn nhất trong đồ thị vô hướng:

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

#define MAX_NODES 51

int nodeCount, edgeCount;
int graph[MAX_NODES][MAX_NODES];
int visitedNodes[MAX_NODES];
int longestPath = 0;

void explorePath(int currentNode, int currentLength) {
    int hasUnvisitedNeighbor = 0;
    
    for (int neighbor = 1; neighbor <= nodeCount; neighbor++) {
        if (graph[currentNode][neighbor] > 0 && !visitedNodes[neighbor]) {
            hasUnvisitedNeighbor = 1;
            visitedNodes[neighbor] = 1;
            explorePath(neighbor, currentLength + graph[currentNode][neighbor]);
            visitedNodes[neighbor] = 0;
        }
    }
    
    if (!hasUnvisitedNeighbor) {
        if (currentLength > longestPath) {
            longestPath = currentLength;
        }
    }
}

int main() {
    scanf("%d %d", &nodeCount, &edgeCount);
    
    for (int i = 0; i < edgeCount; i++) {
        int u, v, weight;
        scanf("%d %d %d", &u, &v, &weight);
        graph[u][v] = weight;
        graph[v][u] = weight;
    }
    
    for (int startNode = 1; startNode <= nodeCount; startNode++) {
        visitedNodes[startNode] = 1;
        explorePath(startNode, 0);
        visitedNodes[startNode] = 0;
    }
    
    printf("%d\n", longestPath);
    return 0;
}

Chương trình thử mọi đỉnh làm điểm bắt đầu, sử dụng đệ quy để duyệt tất cả đường đi có thể và cập nhật độ dài lớn nhất tìm được. Mảng visitedNodes đảm bảo không quay lại đỉnh đã đi trong cùng một đường.