C语言数据结构图的创建与遍历实验示例

下面是“C语言数据结构图的创建与遍历实验示例”的完整攻略。

1. 创建数据结构图

1.1 创建图对象

首先需要创建一个图对象，可以使用邻接矩阵或邻接表来表示图。使用邻接矩阵表示时，将所有顶点的编号按照一定顺序排列在矩阵的行和列上，使用0或1表示两个顶点之间是否有边。使用邻接表表示时，需要一个array存储所有的顶点，数组中的每个元素包含一个链表，链表中存储与该顶点相连的所有边的信息。

下面是使用邻接矩阵创建图对象的示例：

#define MAX_VERTEX_NUM 100 // 最多顶点数
typedef struct {
    char vexs[MAX_VERTEX_NUM]; // 存储顶点信息
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的信息
    int vexnum, arcnum; // 图的当前顶点数和边数
} GraphMatrix;

1.2 添加顶点和边

在图对象中添加顶点和边。如果使用邻接矩阵表示，可以直接在矩阵中设置边的信息。如果使用邻接表表示，需要先找到对应的顶点，然后在其链表中添加边的信息。

下面是使用邻接矩阵添加顶点和边的示例：

GraphMatrix graph;
initGraphMatrix(&graph); // 初始化图
addEdgeGraphMatrix(&graph, 'A', 'B'); // 添加边
addVertexGraphMatrix(&graph, 'C'); // 添加顶点

1.3 遍历图

可以使用深度优先遍历和广度优先遍历两种算法来遍历图。

1.3.1 深度优先遍历

深度优先遍历使用递归的方式来实现。从起始顶点开始遍历，首先访问该顶点，然后依次访问与之相邻的顶点，直到所有与之相邻的顶点都被访问过为止。

下面是使用邻接矩阵实现深度优先遍历的示例：

void DFS_GraphMatrix(GraphMatrix *graph, char v, int visited[]) {
    int i;
    int w = indexOfVertex(graph, v); // 找到该顶点在矩阵中的下标
    visited[w] = 1; // 标记该顶点已被访问
    printf("%c ", graph->vexs[w]); // 输出该顶点的信息
    for (i = 0; i < graph->vexnum; i++) {
        if (graph->arcs[w][i] == 1 && visited[i] == 0) { // 如果与该顶点相邻的顶点未被访问
            DFS_GraphMatrix(graph, graph->vexs[i], visited); // 递归访问该顶点
        }
    }
}

void traverseDFS_GraphMatrix(GraphMatrix *graph) {
    int visited[MAX_VERTEX_NUM] = { 0 }; // 初始化visited数组
    int i;
    for (i = 0; i < graph->vexnum; i++) {
        if (visited[i] == 0) { // 如果该顶点未被访问
            DFS_GraphMatrix(graph, graph->vexs[i], visited); // 使用深度优先遍历访问该顶点及其相邻的顶点
        }
    }
}

1.3.2 广度优先遍历

广度优先遍历使用队列的方式来实现。首先访问起始顶点，然后依次访问与之相邻的顶点，将其压入队列，并标记为已访问。然后从队列中弹出一个顶点，访问与之相邻的未访问的顶点，并将其压入队列，重复该过程直到队列为空。

下面是使用邻接矩阵实现广度优先遍历的示例：

void traverseBFS_GraphMatrix(GraphMatrix *graph) {
    int visited[MAX_VERTEX_NUM] = { 0 }; // 初始化visited数组
    int i, j;
    SqQueue q; // 定义队列
    initSqQueue(&q); // 初始化队列
    for (i = 0; i < graph->vexnum; i++) {
        if (visited[i] == 0) { // 如果该顶点未被访问
            visited[i] = 1; // 标记该顶点已被访问
            printf("%c ", graph->vexs[i]); // 输出该顶点的信息
            enSqQueue(&q, i); // 将该顶点加入队列
            while (!isSqQueueEmpty(q)) {
                int u;
                deSqQueue(&q, &u); // 从队列中弹出一个顶点
                for (j = 0; j < graph->vexnum; j++) {
                    if (graph->arcs[u][j] == 1 && visited[j] == 0) { // 如果与该顶点相邻的顶点未被访问
                        visited[j] = 1; // 标记该顶点已被访问
                        printf("%c ", graph->vexs[j]); // 输出该顶点的信息
                        enSqQueue(&q, j); // 将该顶点加入队列
                    }
                }
            }
        }
    }
}

2. 示例说明

2.1 示例1

创建一个7个顶点的无向图，顶点信息分别为A、B、C、D、E、F、G，边的信息如下：

A-B、A-C、B-D、B-E、C-F、D-F、E-G、F-G

使用邻接矩阵表示，创建图对象，添加顶点和边，然后使用深度优先遍历和广度优先遍历分别遍历该图。

GraphMatrix graph;
initGraphMatrix(&graph); // 初始化图
addEdgeGraphMatrix(&graph, 'A', 'B');
addEdgeGraphMatrix(&graph, 'A', 'C');
addEdgeGraphMatrix(&graph, 'B', 'D');
addEdgeGraphMatrix(&graph, 'B', 'E');
addEdgeGraphMatrix(&graph, 'C', 'F');
addEdgeGraphMatrix(&graph, 'D', 'F');
addEdgeGraphMatrix(&graph, 'E', 'G');
addEdgeGraphMatrix(&graph, 'F', 'G');
traverseDFS_GraphMatrix(&graph); // 深度优先遍历
printf("\n");
traverseBFS_GraphMatrix(&graph); // 广度优先遍历
printf("\n");

输出结果：

A B D F E G C 
A B C D E F G 

2.2 示例2

创建一个5个顶点的有向图，顶点信息分别为V0、V1、V2、V3、V4，边的信息如下：

V0->V1、V0->V2、V0->V3、V1->V4、V4->V3、V4->V2

使用邻接表表示，创建图对象，添加顶点和边，然后使用深度优先遍历和广度优先遍历分别遍历该图。

GraphAdjList graph;
initGraphAdjList(&graph); // 初始化图
addVertexGraphAdjList(&graph, "V0");
addVertexGraphAdjList(&graph, "V1");
addVertexGraphAdjList(&graph, "V2");
addVertexGraphAdjList(&graph, "V3");
addVertexGraphAdjList(&graph, "V4");
addEdgeGraphAdjList(&graph, "V0", "V1");
addEdgeGraphAdjList(&graph, "V0", "V2");
addEdgeGraphAdjList(&graph, "V0", "V3");
addEdgeGraphAdjList(&graph, "V1", "V4");
addEdgeGraphAdjList(&graph, "V4", "V3");
addEdgeGraphAdjList(&graph, "V4", "V2");
traverseDFS_GraphAdjList(&graph); // 深度优先遍历
printf("\n");
traverseBFS_GraphAdjList(&graph); // 广度优先遍历
printf("\n");

输出结果：

V0->V3->V4->V2->V1
V0 V1 V2 V3 V4 

以上是“C语言数据结构图的创建与遍历实验示例”的完整攻略，希望有所帮助。