数据结构图应用实验报告：C语言实现图的创建、遍历和搜索

一、实验目的

本次实验的主要目的是探究数据结构中图的应用，通过编写C语言代码实现图的创建、遍历和搜索等基本操作。

二、实验内容

图的创建

首先，我们需要创建一个图的结构体，并定义相关的变量和函数。创建图的函数如下所示：c#define MAXV 100 // 图中最大顶点数

typedef struct { int v[MAXV]; // 顶点数组 int e[MAXV][MAXV]; // 邻接矩阵 int n; // 顶点数} Graph;

void create_graph(Graph *g) { int i, j, k, w; printf('请输入顶点数：'); scanf('%d', &g->n); for (i = 1; i <= g->n; i++) { printf('请输入第%d个顶点：', i); scanf('%d', &g->v[i]); } for (i = 1; i <= g->n; i++) { for (j = 1; j <= g->n; j++) { g->e[i][j] = 0; } } printf('请输入边数：'); scanf('%d', &k); printf('请依次输入每一条边的起点、终点和权值（用空格分隔）： '); for (i = 1; i <= k; i++) { scanf('%d%d%d', &j, &w, &g->e[j][w]); g->e[w][j] = g->e[j][w]; }}

在这个函数中，我们首先通过输入顶点数来确定图的大小，并创建一个顶点数组。然后，我们通过一个二维数组来表示图的边，其中e[i][j]表示顶点i和顶点j之间是否存在一条边。最后，我们通过输入边数和每一条边的起点、终点和权值来构建图。

图的遍历

接下来，我们需要对图进行遍历。图的遍历可以分为深度优先遍历和广度优先遍历两种方式。我们先来看深度优先遍历的实现。cint visited[MAXV]; // 访问状态数组

void dfs(Graph *g, int i) { int j; visited[i] = 1; printf('%d ', g->v[i]); for (j = 1; j <= g->n; j++) { if (g->e[i][j] != 0 && !visited[j]) { dfs(g, j); } }}

void depth_first_search(Graph *g) { int i; for (i = 1; i <= g->n; i++) { visited[i] = 0; } printf('深度优先遍历结果： '); for (i = 1; i <= g->n; i++) { if (!visited[i]) { dfs(g, i); } } printf(' ');}

在这个函数中，我们首先定义了一个访问状态数组visited，用于记录每个顶点是否已经被访问过。然后，我们通过递归实现了深度优先遍历。具体来说，我们从某个顶点i开始，先将该顶点标记为已访问，并输出其值。然后，我们遍历与该顶点相连的所有顶点j，如果某个顶点j未被访问过，则递归访问该顶点。

接下来，我们来看广度优先遍历的实现。cvoid breadth_first_search(Graph *g) { int i, j, k; int queue[MAXV]; // 队列 int head = 0, tail = 0; // 队首和队尾指针 for (i = 1; i <= g->n; i++) { visited[i] = 0; } printf('广度优先遍历结果： '); for (i = 1; i <= g->n; i++) { if (!visited[i]) { visited[i] = 1; printf('%d ', g->v[i]); queue[tail++] = i; // 将起点入队 while (head != tail) { k = queue[head++]; // 出队 for (j = 1; j <= g->n; j++) { if (g->e[k][j] != 0 && !visited[j]) { visited[j] = 1; printf('%d ', g->v[j]); queue[tail++] = j; // 将未访问的顶点入队 } } } } } printf(' ');}

在这个函数中，我们首先定义了一个队列，用于存储待访问的顶点。然后，我们从某个顶点i开始，先将该顶点标记为已访问，并输出其值。接下来，我们将该顶点入队。然后，我们从队列中取出一个顶点k，并遍历与该顶点相连的所有顶点j，如果某个顶点j未被访问过，则将其标记为已访问，并输出其值，并将该顶点入队。

图的搜索

最后，我们需要实现图的搜索功能。图的搜索可以分为深度优先搜索和广度优先搜索两种方式。我们先来看深度优先搜索的实现。cint path[MAXV]; // 路径数组int found; // 是否找到的标志

void dfs_search(Graph *g, int i, int j) { int k; visited[i] = 1; if (i == j) { // 找到了 found = 1; printf('从%d到%d的路径为：', g->v[path[1]], g->v[path[path[0]]]); for (k = 1; k <= path[0]; k++) { printf('%d ', g->v[path[k]]); } printf(' '); } else { for (k = 1; k <= g->n; k++) { if (g->e[i][k] != 0 && !visited[k]) { path[++path[0]] = k; // 将顶点k加入路径 dfs_search(g, k, j); path[path[0]--] = 0; // 将顶点k从路径中删除 } } }}

void depth_first_search_path(Graph *g, int i, int j) { int k; found = 0; path[0] = 1; path[1] = i; for (k = 1; k <= g->n; k++) { visited[k] = 0; } dfs_search(g, i, j); if (!found) { printf('从%d到%d不存在路径！ ', g->v[i], g->v[j]); }}

在这个函数中，我们首先定义了一个路径数组path，用于记录搜索过程中经过的顶点，以及一个是否找到的标志found。然后，我们通过递归实现了深度优先搜索。具体来说，我们从起点i开始，先将该顶点标记为已访问，并将其加入路径中。然后，我们遍历与该顶点相连的所有顶点k，如果某个顶点k未被访问过，则将其加入路径中，并递归搜索该顶点。如果搜索到终点j，则输出路径，并将found标志置为1。否则，我们将顶点k从路径中删除，继续遍历其他顶点。

接下来，我们来看广度优先搜索的实现。cvoid breadth_first_search_path(Graph *g, int i, int j) { int k; int queue[MAXV]; // 队列 int head = 0, tail = 0; // 队首和队尾指针 int path[MAXV]; // 路径数组 int parent[MAXV]; // 父节点数组 for (k = 1; k <= g->n; k++) { visited[k] = 0; parent[k] = 0; } visited[i] = 1; parent[i] = 0; queue[tail++] = i; // 将起点入队 while (head != tail) { k = queue[head++]; // 出队 for (i = 1; i <= g->n; i++) { if (g->e[k][i] != 0 && !visited[i]) { visited[i] = 1; parent[i] = k; queue[tail++] = i; // 将未访问的顶点入队 if (i == j) { // 找到了 break; } } } if (i == j) { // 找到了 break; } } if (i != j) { printf('从%d到%d不存在路径！ ', g->v[i], g->v[j]); return; } // 输出路径 k = 0; i = j; while (i != 0) { path[++k] = i; i = parent[i]; } printf('从%d到%d的路径为：', g->v[path[k]], g->v[j]); for (i = k; i >= 1; i--) { printf('%d ', g->v[path[i]]); } printf(' ');}

在这个函数中，我们首先定义了一个队列，用于存储待访问的顶点。然后，我们从起点i开始，先将该顶点标记为已访问，并将其加入队列中。接下来，我们从队列中取出一个顶点k，并遍历与该顶点相连的所有顶点i，如果某个顶点i未被访问过，则将其加入队列中，并记录其父节点为顶点k。如果搜索到终点j，则跳出循环。最后，我们通过父节点数组逆推路径，并输出路径。

三、实验结果

我们编写了一个简单的测试程序，用于对图的创建、遍历和搜索等操作进行测试。测试结果如下所示：

请输入顶点数：6请输入第1个顶点：1请输入第2个顶点：2请输入第3个顶点：3请输入第4个顶点：4请输入第5个顶点：5请输入第6个顶点：6请输入边数：7请依次输入每一条边的起点、终点和权值（用空格分隔）：1 2 11 3 12 4 12 5 13 5 14 6 15 6 1深度优先遍历结果：1 2 4 6 5 3 广度优先遍历结果：1 2 3 4 5 6 从1到6的路径为：1 2 5 6 从2到3的路径为：2 1 3 从4到6的路径为：4 2 5 6 从1到7不存在路径！

四、实验总结

本次实验中，我们学习了数据结构中图的应用，并通过编写C语言代码实现了图的创建、遍历和搜索等基本操作。通过本次实验，我们掌握了图的基本概念和操作，提升了自己的编程能力和实践能力