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

#define V 6  /* 顶点数 */

/* 邻接矩阵表示的图 */
int graph[V][V] = {
    {0,1,1,0,0,0},  /* 顶点 0 的邻接关系 */
    {1,0,0,1,1,0},  /* 顶点 1 */
    {1,0,0,0,1,0},  /* 顶点 2 */
    {0,1,0,0,0,1},  /* 顶点 3 */
    {0,1,1,0,0,1},  /* 顶点 4 */
    {0,0,0,1,1,0}   /* 顶点 5 */
};
bool visited[V];

/* DFS: 深度优先搜索，递归实现
   特点：沿一条路径走到头再回溯，适合路径搜索和连通性判断 */
void DFS(int v) {
    visited[v] = true;
    printf("%d ", v);         /* 访问当前顶点 */
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i);  /* 递归访问未访问的邻接顶点 */
        }
    }
}

/* BFS: 广度优先搜索，借助队列实现
   特点：按层扩展，天然适合求解最短路径 */
void BFS(int start) {
    bool visited[V] = {false};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = start;  /* 起始顶点入队 */

    while (front < rear) {
        int v = queue[front++];  /* 出队 */
        printf("%d ", v);

        for (int i = 0; i < V; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;  /* 邻接顶点入队 */
            }
        }
    }
}

int main() {
    /* 初始化访问标记 */
    for (int i = 0; i < V; i++) visited[i] = false;

    printf("DFS (从顶点 0 开始): ");
    DFS(0);  /* 输出: 0 1 3 5 4 2 */
    printf("\n");

    printf("BFS (从顶点 0 开始): ");
    BFS(0);  /* 输出: 0 1 2 3 4 5 */
    printf("\n");
    return 0;
}