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

以下是C语言实现的代码，其中采用邻接表存储有向图，使用DFS和BFS算法求解其遍历序列：

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

#define MAX_VERTEX 8 // 顶点数的最大值

// 边表结点
typedef struct ArcNode {
    int adjvex; // 邻接点在数组中的下标
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct VexNode {
    int data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VexNode;

// 有向图
typedef struct {
    VexNode vexs[MAX_VERTEX]; // 顶点表
    int vexnum; // 顶点数
    int arcnum; // 边数
} Graph;

// 初始化有向图
void initGraph(Graph *G, int (*arcs)[2], int n, int m) {
    G->vexnum = n;
    G->arcnum = m;
    // 初始化各顶点
    for (int i = 0; i < n; i++) {
        G->vexs[i].data = i;
        G->vexs[i].firstarc = NULL;
    }
    // 添加各边
    for (int i = 0; i < m; i++) {
        int v1 = arcs[i][0], v2 = arcs[i][1];
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = v2;
        p->next = G->vexs[v1].firstarc;
        G->vexs[v1].firstarc = p;
    }
}

// DFS遍历
void DFS(Graph *G, int v, int *visited) {
    visited[v] = 1; // 标记当前顶点为已访问
    printf("%d ", v); // 输出当前顶点
    ArcNode *p = G->vexs[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (visited[w] == 0) { // 如果邻接点未被访问，则递归访问它
            DFS(G, w, visited);
        }
        p = p->next; // 继续访问下一个邻接点
    }
}

// BFS遍历
void BFS(Graph *G, int v, int *visited) {
    int queue[MAX_VERTEX], front = 0, rear = 0;
    visited[v] = 1; // 标记当前顶点为已访问
    printf("%d ", v); // 输出当前顶点
    queue[rear++] = v; // 将当前顶点入队
    while (front != rear) {
        int u = queue[front++]; // 取出队首顶点
        ArcNode *p = G->vexs[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (visited[w] == 0) { // 如果邻接点未被访问，则标记为已访问并入队
                visited[w] = 1;
                printf("%d ", w);
                queue[rear++] = w;
            }
            p = p->next; // 继续访问下一个邻接点
        }
    }
}

int main() {
    int arcs[][2] = {{0, 3}, {1, 6}, {1, 7}, {2, 0}, {2, 1},
                     {2, 5}, {3, 7}, {4, 0}, {4, 3}, {4, 6},
                     {5, 2}, {5, 4}, {6, 2}, {6, 5}, {7, 4}};
    Graph G;
    initGraph(&G, arcs, MAX_VERTEX, 15);

    int visited[MAX_VERTEX] = {0}; // 初始化所有顶点为未访问状态

    printf("DFS序列：");
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (visited[i] == 0) {
            DFS(&G, i, visited);
        }
    }
    printf("\n");

    for (int i = 0; i < MAX_VERTEX; i++) {
        visited[i] = 0; // 重置所有顶点的访问状态
    }

    printf("BFS序列：");
    for (int i = 0; i < MAX_VERTEX; i++) {
        if (visited[i] == 0) {
            BFS(&G, i, visited);
        }
    }
    printf("\n");

    return 0;
}

输出结果如下：

DFS序列：0 3 7 4 6 5 2 1 
BFS序列：0 3 4 6 7 1 2 5