c语言实现（1）图的基本操作 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 1.以邻接矩阵为存储结构，实现强连通图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 2.以邻接表为存储结构，实现连通图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

[解题思路]

图的基本操作有两种存储结构：邻接矩阵和邻接表。其中，邻接矩阵使用二维数组存储图的边，邻接表则使用链表存储每个顶点的相邻顶点。

深度优先遍历和广度优先遍历都是基于搜索算法实现的。深度优先遍历（DFS）是一种先访问深度较深的节点，再逐步回溯访问其他节点的算法，而广度优先遍历（BFS）则是一种逐层遍历的算法。

对于邻接矩阵存储结构，我们可以使用递归实现深度优先遍历，使用队列实现广度优先遍历。而对于邻接表存储结构，我们同样可以使用递归实现深度优先遍历，使用队列实现广度优先遍历。

[参考代码]

以下是基于邻接矩阵和邻接表的深度优先遍历和广度优先遍历的代码实现。

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接矩阵存储结构
typedef struct {
    char vexs[MAX_VERTEX_NUM]; // 顶点集合
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵，可看作边表
    int vexnum, arcnum; // 图的当前点数和边数
} MatrixGraph;

// 邻接表存储结构
typedef struct ArcNode {
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;

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

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

bool visited[MAX_VERTEX_NUM]; // 记录各个顶点是否被访问过

// 初始化邻接矩阵
void InitMatrixGraph(MatrixGraph *G) {
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    
    printf("请输入图的顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = 0;
        }
    }
    
    printf("请输入图的边信息（格式：vi vj）：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        scanf(" %c %c", &v1, &v2);
        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vexs[i] == v1) break;
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vexs[j] == v2) break;
        }
        G->arc[i][j] = 1;
        G->arc[j][i] = 1;
    }
}

// 深度优先遍历邻接矩阵
void DFSMatrix(MatrixGraph G, int v) {
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arc[v][i] == 1 && !visited[i]) {
            DFSMatrix(G, i);
        }
    }
}

// 广度优先遍历邻接矩阵
void BFSMatrix(MatrixGraph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    printf("%c ", G.vexs[v]);
    queue[rear++] = v;
    while (front < rear) {
        int i = queue[front++];
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arc[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                printf("%c ", G.vexs[j]);
                queue[rear++] = j;
            }
        }
    }
}

// 初始化邻接表
void InitListGraph(ListGraph *G) {
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    
    printf("请输入图的顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    
    printf("请输入图的边信息（格式：vi vj）：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        scanf(" %c %c", &v1, &v2);
        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) break;
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) break;
        }
        ArcNode *e1 = (ArcNode *)malloc(sizeof(ArcNode));
        e1->adjvex = j;
        e1->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = e1;
        
        ArcNode *e2 = (ArcNode *)malloc(sizeof(ArcNode));
        e2->adjvex = i;
        e2->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = e2;
    }
}

// 深度优先遍历邻接表
void DFSList(ListGraph G, int v) {
    visited[v] = true;
    printf("%c ", G.vertices[v].data);
    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        int j = p->adjvex;
        if (!visited[j]) {
            DFSList(G, j);
        }
        p = p->nextarc;
    }
}

// 广度优先遍历邻接表
void BFSList(ListGraph G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = true;
    printf("%c ", G.vertices[v].data);
    queue[rear++] = v;
    while (front < rear) {
        int i = queue[front++];
        ArcNode *p = G.vertices[i].firstarc;
        while (p != NULL) {
            int j = p->adjvex;
            if (!visited[j]) {
                visited[j] = true;
                printf("%c ", G.vertices[j].data);
                queue[rear++] = j;
            }
            p = p->nextarc;
        }
    }
}

int main() {
    MatrixGraph G1;
    InitMatrixGraph(&G1);
    printf("请输入起点（邻接矩阵）：");
    char start1;
    scanf(" %c", &start1);
    int i;
    for (i = 0; i < G1.vexnum; i++) {
        if (G1.vexs[i] == start1) break;
    }
    printf("深度优先遍历结果（邻接矩阵）：");
    DFSMatrix(G1, i);
    printf("\n");
    for (int j = 0; j < G1.vexnum; j++) {
        visited[j] = false;
    }
    printf("广度优先遍历结果（邻接矩阵）：");
    BFSMatrix(G1, i);
    printf("\n");
    
    ListGraph G2;
    InitListGraph(&G2);
    printf("请输入起点（邻接表）：");
    char start2;
    scanf(" %c", &start2);
    for (i = 0; i < G2.vexnum; i++) {
        if (G2.vertices[i].data == start2) break;
    }
    printf("深度优先遍历结果（邻接表）：");
    DFSList(G2, i);
    printf("\n");
    for (int j = 0; j < G2.vexnum; j++) {
        visited[j] = false;
    }
    printf("广度优先遍历结果（邻接表）：");
    BFSList(G2, i);
    printf("\n");
    
    return 0;
}