用c语言设计一个程序，依次从有向图中的每个顶点深度优先搜索遍历操作；邻接矩阵作为存储结构。算法思想： (1) 定义图的顺序存储结构； (2) 创建有向图，采用邻接矩阵表示（调用CreateDG函数实现），具体实现如下： 输入图的顶点数和边数； 依次输入顶点的信息存入顶点表中； 初始化邻接矩阵，使每个权值初始化为0； 构造邻接矩阵；（需调用LocateVex函数获取顶点在顶点表中的下标） (3) 依次从每个顶点进行深度优先搜索，并输出访问序列（调用DFSTraverse函数实现；另需调用相关函数实现获取第一个和下一个邻接点的操作）。 注意：顶点数据仅为1个数字或1个字符。 输入说明： 第一行输入图的顶点数n和边数m； 第二行依次输入n个顶点的数据； 接下来m行的每行输入一条边的信息。 输出说明： 输出n行，每行输出从第i(0≤i＜n)个顶点深度优先搜索的访问序列，序列中的连通分量用{}括起来，无空格间隔，{}为英文半角的符号。 输入样例： 4 4 1 2 3 4 1 2 1 3 3 4 4 1 输出样例： {1234} {2}{341} {3412} {4123}

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

#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_STACK_SIZE 100 // 栈的最大容量

// 邻接矩阵存储结构
typedef struct {
    char vex[MAX_VERTEX_NUM]; // 顶点表
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 图的顶点数和弧数
} MGraph;

// 栈的结构体
typedef struct {
    int data[MAX_STACK_SIZE]; // 栈的数据数组
    int top; // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_STACK_SIZE - 1;
}

// 入栈操作
void push(Stack *s, int x) {
    if (isFull(s)) {
        printf("Stack is full.\n");
        exit(1);
    }
    s->data[++s->top] = x;
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->data[s->top--];
}

// 获取第一个邻接点
int getFirstNeighbor(MGraph *G, int v) {
    int i;
    for (i = 0; i < G->vexnum; ++i) {
        if (G->arc[v][i] != 0) {
            return i;
        }
    }
    return -1;
}

// 获取下一个邻接点
int getNextNeighbor(MGraph *G, int v, int w) {
    int i;
    for (i = w + 1; i < G->vexnum; ++i) {
        if (G->arc[v][i] != 0) {
            return i;
        }
    }
    return -1;
}

// 深度优先搜索遍历操作
void DFS(MGraph *G, int v, bool visited[]) {
    printf("%c", G->vex[v]);
    visited[v] = true;
    int w = getFirstNeighbor(G, v);
    while (w != -1) {
        if (!visited[w]) {
            DFS(G, w, visited);
        }
        w = getNextNeighbor(G, v, w);
    }
}

// 深度优先搜索遍历图
void DFSTraverse(MGraph *G) {
    int i;
    bool visited[MAX_VERTEX_NUM] = { false };
    for (i = 0; i < G->vexnum; ++i) {
        if (!visited[i]) {
            printf("{");
            DFS(G, i, visited);
            printf("}\n");
        }
    }
}

// 获取顶点在顶点表中的下标
int LocateVex(MGraph *G, char c) {
    int i;
    for (i = 0; i < G->vexnum; ++i) {
        if (G->vex[i] == c) {
            return i;
        }
    }
    return -1;
}

// 创建有向图
void CreateDG(MGraph *G) {
    int i, j, k;
    printf("Enter vertex number and edge number: ");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("Enter vertex data: ");
    for (i = 0; i < G->vexnum; ++i) {
        scanf(" %c", &G->vex[i]);
    }
    for (i = 0; i < G->vexnum; ++i) {
        for (j = 0; j < G->vexnum; ++j) {
            G->arc[i][j] = 0;
        }
    }
    printf("Enter edge data: \n");
    for (k = 0; k < G->arcnum; ++k) {
        char v1, v2;
        int i, j;
        printf("Edge %d: ", k + 1);
        scanf(" %c %c", &v1, &v2);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        if (i == -1 || j == -1) {
            printf("Invalid vertex data.\n");
            exit(1);
        }
        G->arc[i][j] = 1;
    }
}

int main() {
    MGraph G;
    CreateDG(&G);
    DFSTraverse(&G);
    return 0;
}