用c语言写出图的表示和深度优先搜索

图的表示可以使用邻接矩阵或邻接表两种方式，下面分别给出代码示例：

邻接矩阵表示图的代码示例：

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INFINITY 65535 // 无穷大
typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点表
    EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵，可看作边表
    int vexnum, arcnum; // 图的当前顶点数和边数
} MGraph;

// 创建无向网图的邻接矩阵
void CreateMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数: ");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    for (i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点值: ", i + 1);
        scanf("%c", &G->vexs[i]); // 输入顶点信息
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = INFINITY; // 初始化邻接矩阵
        }
    }
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入边(vi, vj)上的下标i, 下标j和权值w: ");
        scanf("%d%d%d", &i, &j, &w);
        G->arc[i][j] = w; // 无向图，矩阵对称
        G->arc[j][i] = G->arc[i][j];
    }
}

// 深度优先遍历
void DFS(MGraph G, int v, bool visited[]) {
    int i;
    visited[v] = true; // 标记该顶点已被访问
    printf("%c ", G.vexs[v]); // 输出顶点信息
    for (i = 0; i < G.vexnum; i++) {
        if (G.arc[v][i] != INFINITY && !visited[i]) { // 该顶点与当前顶点之间有边且未被访问过
            DFS(G, i, visited);
        }
    }
}

// 邻接矩阵方式深度优先遍历
void DFSTraverse(MGraph G) {
    int i;
    bool visited[MAX_VERTEX_NUM]; // 访问标记数组，初始值为false
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) { // 若该顶点未被访问，从该顶点开始深度优先遍历
            DFS(G, i, visited);
        }
    }
}

int main() {
    MGraph G;
    CreateMGraph(&G);
    DFSTraverse(G); // 深度优先遍历
    return 0;
}

邻接表表示图的代码示例：

#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边权值类型

// 边表节点
typedef struct ArcNode {
    int adjvex; // 该边所指向的顶点的位置
    EdgeType weight; // 边权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 顶点表节点
typedef struct VNode {
    VertexType data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;

// 创建无向网图的邻接表
void CreateALGraph(ALGraph *G) {
    int i, j, k, w;
    ArcNode *p;
    printf("请输入顶点数和边数: ");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    for (i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点值: ", i + 1);
        scanf("%c", &G->vertices[i].data); // 输入顶点信息
        G->vertices[i].firstarc = NULL; // 初始化表头节点指针
    }
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入边(vi, vj)上的下标i, 下标j和权值w: ");
        scanf("%d%d%d", &i, &j, &w);
        // 添加边节点
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->next = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        // 无向图，添加对称边节点
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->weight = w;
        p->next = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

// 深度优先遍历
void DFS(ALGraph G, int v, bool visited[]) {
    ArcNode *p;
    visited[v] = true; // 标记该顶点已被访问
    printf("%c ", G.vertices[v].data); // 输出顶点信息
    p = G.vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) { // 该顶点与当前顶点之间有边且未被访问过
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 邻接表方式深度优先遍历
void DFSTraverse(ALGraph G) {
    int i;
    bool visited[MAX_VERTEX_NUM]; // 访问标记数组，初始值为false
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) { // 若该顶点未被访问，从该顶点开始深度优先遍历
            DFS(G, i, visited);
        }
    }
}

int main() {
    ALGraph G;
    CreateALGraph(&G);
    DFSTraverse(G); // 深度优先遍历
    return 0;
}