给出一段C语言代码,实现以下功能,创建图的邻接矩阵和邻接表,依据图的邻接矩阵完成图的深度遍历,依据图的邻接表完成图的广度遍历
时间: 2024-05-01 09:23:05 浏览: 123
以下是一个基本的实现,仅作参考,具体实现还需要根据具体情况进行调整。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接矩阵存储结构
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num, arc_num; // 顶点数和边数
} MGraph;
// 邻接表存储结构
typedef struct ArcNode {
int adjvex; // 邻接点的下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表数组
int vertex_num, arc_num; // 顶点数和边数
} ALGraph;
// 创建图的邻接矩阵
void CreateMGraph(MGraph *G) {
int i, j, k;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vertex_num, &G->arc_num);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->arc[i][j] = 0;
}
}
printf("请输入边的信息:\n");
for (k = 0; k < G->arc_num; k++) {
printf("请输入第%d条边(vi,vj)的下标i和j:", k + 1);
scanf("%d%d", &i, &j);
G->arc[i][j] = 1; // 有向图
// G->arc[j][i] = 1; // 无向图
}
}
// 创建图的邻接表
void CreateALGraph(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vertex_num, &G->arc_num);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入边的信息:\n");
for (k = 0; k < G->arc_num; k++) {
printf("请输入第%d条边(vi,vj)的下标i和j:", k + 1);
scanf("%d%d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
// 若为无向图,则需要将下面的代码也加上
// p = (ArcNode *)malloc(sizeof(ArcNode));
// p->adjvex = i;
// p->next = G->vertices[j].firstarc;
// G->vertices[j].firstarc = p;
}
}
int visited[MAX_VERTEX_NUM]; // 记录顶点是否被访问过
// 邻接矩阵深度优先搜索算法
void DFS(MGraph G, int i) {
int j;
visited[i] = 1;
printf("%d ", G.vertex[i]); // 访问顶点i
for (j = 0; j < G.vertex_num; j++) {
if (G.arc[i][j] == 1 && !visited[j]) { // 若存在边(i,j)且顶点j未被访问
DFS(G, j); // 递归访问顶点j
}
}
}
// 邻接表广度优先搜索算法
void BFS(ALGraph G, int i) {
int j;
ArcNode *p;
int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 队列
printf("%d ", G.vertices[i].data); // 访问顶点i
visited[i] = 1;
queue[rear++] = i; // 将i入队
while (front != rear) { // 队列非空
i = queue[front++]; // 出队一个顶点
for (p = G.vertices[i].firstarc; p != NULL; p = p->next) { // 遍历顶点i的所有邻接点
j = p->adjvex;
if (!visited[j]) { // 若顶点j未被访问
printf("%d ", G.vertices[j].data); // 访问顶点j
visited[j] = 1;
queue[rear++] = j; // 将j入队
}
}
}
}
int main() {
MGraph G1;
ALGraph G2;
int i;
CreateMGraph(&G1);
CreateALGraph(&G2);
printf("邻接矩阵深度优先搜索结果:\n");
for (i = 0; i < G1.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < G1.vertex_num; i++) {
if (!visited[i]) { // 若顶点i未被访问,则从顶点i开始深度优先搜索
DFS(G1, i);
}
}
printf("\n邻接表广度优先搜索结果:\n");
for (i = 0; i < G2.vertex_num; i++) {
visited[i] = 0;
}
for (i = 0; i < G2.vertex_num; i++) {
if (!visited[i]) { // 若顶点i未被访问,则从顶点i开始广度优先搜索
BFS(G2, i);
}
}
return 0;
}
```
阅读全文