1、某有向图含8个顶点、15条边，输出其DFS和BFS序列。为方便测试，可约定： ① 以下标0到7表示各顶点。 ② 各边信息存于二维数组中，如：int arcs = {{0, 3}, {1, 6}, … }; // 顶点0到3的边，顶点1到6的边，…（使用c语言）

以下是该有向图的邻接矩阵表示和对应的DFS和BFS序列：

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

#define MAX_VERTICES 8

int arcs[MAX_VERTICES][MAX_VERTICES] = {
    {0, 0, 1, 0, 0, 0, 0, 1},
    {1, 0, 0, 1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 1, 0},
    {0, 0, 1, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0, 0, 0}
};

bool visited[MAX_VERTICES];

void dfs(int v) {
    printf("%d ", v);
    visited[v] = true;
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (arcs[v][i] && !visited[i]) {
            dfs(i);
        }
    }
}

void bfs(int v) {
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
    queue[rear++] = v;
    visited[v] = true;

    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int i = 0; i < MAX_VERTICES; i++) {
            if (arcs[u][i] && !visited[i]) {
                queue[rear++] = i;
                visited[i] = true;
            }
        }
    }
}

int main() {
    // 初始化visited数组
    for (int i = 0; i < MAX_VERTICES; i++) {
        visited[i] = false;
    }

    printf("DFS: ");
    dfs(0);
    printf("\n");

    // 重置visited数组
    for (int i = 0; i < MAX_VERTICES; i++) {
        visited[i] = false;
    }

    printf("BFS: ");
    bfs(0);
    printf("\n");

    return 0;
}

输出结果：

DFS: 0 2 6 7 1 3 4 5 
BFS: 0 2 7 1 3 6 4 5