按邻接矩阵的方法创建图,并分别用深度优先和广度优先两种方法遍历这张图,并提供C语言代码
时间: 2024-05-14 22:15:57 浏览: 73
好的,我明白了。以下是您所提到的问题的答案和相应的C语言代码:
按邻接矩阵的方法创建图:
```c
#define MAX_VERTEX_NUM 100 // 顶点数的最大值
#define INFINITY 65535 // 表示无穷大的值
typedef int Status; // 函数返回值类型
typedef int VRType; // 图中边权值类型
typedef char VertexType; // 图中顶点值类型
// 邻接矩阵的存储结构
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 存储顶点信息
VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
int vexnum, arcnum; // 记录图中顶点数和边数
} MGraph;
// 创建邻接矩阵图
Status CreateGraph(MGraph *G) {
int i, j, k, w;
VertexType v1, v2;
printf("请输入图的顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入图的顶点信息:");
for (i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vexs[i]);
}
// 初始化邻接矩阵
for (i = 0; i < G->vexnum; i++) {
for (j = 0; j < G->vexnum; j++) {
G->arcs[i][j] = INFINITY;
}
}
// 录入边的信息并存储到邻接矩阵中
printf("请按格式输入每条边的信息:\n");
for (k = 0; k < G->arcnum; k++) {
scanf("%c%c%d", &v1, &v2, &w);
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->arcs[i][j] = w;
G->arcs[j][i] = w; // 无向图需要将边的两个方向上的权值都存储
}
return 1;
}
```
深度优先遍历:
```c
typedef struct {
VertexType data[MAX_VERTEX_NUM]; // 存储顶点信息
int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过
int vexnum, arcnum; // 记录图中顶点数和边数
VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边权值
} MGraph_DFS;
// 深度优先遍历核心函数
void DFS(MGraph_DFS *G, int v) {
printf("%c ", G->data[v]); // 输出当前访问的结点的信息
G->visited[v] = 1; // 将该结点标记为已访问
int i;
// 遍历与当前结点相邻的结点
for (i = 0; i < G->vexnum; i++) {
if (G->arcs[v][i] != INFINITY && !G->visited[i]) {
DFS(G, i); // 递归访问邻接结点
}
}
}
// 深度优先遍历
void DFSTraverse(MGraph_DFS *G) {
int i;
// 初始化visited数组
for (i = 0; i < G->vexnum; i++) {
G->visited[i] = 0;
}
// 从未访问过的结点开始遍历
for (i = 0; i < G->vexnum; i++) {
if (!G->visited[i]) {
DFS(G, i);
}
}
}
```
广度优先遍历:
```c
typedef struct {
VertexType data[MAX_VERTEX_NUM]; // 存储顶点信息
int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过
int vexnum, arcnum; // 记录图中顶点数和边数
VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边权值
} MGraph_BFS;
// 广度优先遍历
void BFSTraverse(MGraph_BFS *G) {
int i, j;
int curID = 0, que_front = 0, que_rear = 0, que[MAX_VERTEX_NUM]; //用队列辅助广度优先遍历
// 初始化visited数组和队列
for (i = 0; i < G->vexnum; i++) {
G->visited[i] = 0;
que[i] = -1; // -1表示该位置为空
}
// 从未访问过的结点开始遍历
for (i = 0; i < G->vexnum; i++) {
if (!G->visited[i]) {
printf("%c ", G->data[i]);
G->visited[i] = 1;
que[que_rear++] = i; // 将该结点加入队尾
while (que_front < que_rear) {
curID = que[que_front++]; // 取出队首元素并访问
for (j = 0; j < G->vexnum; j++) {
if (G->arcs[curID][j] != INFINITY && !G->visited[j]) {
printf("%c ", G->data[j]);
G->visited[j] = 1;
que[que_rear++] = j; // 将该结点加入队尾
}
}
}
}
}
}
```
另外需要说明的是,上述代码只是简单的示例代码,并没有经过完整的测试。在实际使用时,还需要考虑一些细节问题,比如输入数据的合法性检查等等。
阅读全文