用c++创建图并用DFS和BFS搜索
时间: 2023-06-11 18:07:59 浏览: 62
好的,下面是C语言实现的图的创建、DFS和BFS搜索的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
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 vexnum, arcnum; // 顶点数和边数
} Graph;
// 创建图
void CreateGraph(Graph *G) {
int i, j, k;
ArcNode *p;
printf("请输入图的顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入各个顶点的数据:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入各个边的两个顶点的下标:(如0 1,表示边<0,1>)\n");
for (k = 0; k < G->arcnum; k++) {
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;
}
}
// DFS搜索
void DFS(Graph G, int v, int visited[]) {
ArcNode *p;
visited[v] = 1;
printf("%d ", G.vertices[v].data);
for (p = G.vertices[v].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
}
}
// BFS搜索
void BFS(Graph G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], front = -1, rear = -1;
ArcNode *p;
visited[v] = 1;
printf("%d ", G.vertices[v].data);
queue[++rear] = v;
while (front != rear) {
v = queue[++front];
for (p = G.vertices[v].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", G.vertices[p->adjvex].data);
queue[++rear] = p->adjvex;
}
}
}
}
int main() {
Graph G;
int visited[MAX_VERTEX_NUM] = {0};
CreateGraph(&G);
printf("DFS搜索结果为:");
DFS(G, 0, visited);
printf("\nBFS搜索结果为:");
BFS(G, 0, visited);
printf("\n");
return 0;
}
```
在上述代码中,我们使用了邻接表来表示图,其中`VNode`表示顶点表节点,`ArcNode`表示边表节点,`AdjList`是一个由`VNode`组成的数组,即邻接表。在创建图时,我们先输入顶点数和边数,然后输入各个顶点的数据和各个边的两个顶点的下标,根据下标构建边表。
接着,我们分别实现了DFS和BFS搜索。在DFS搜索中,我们先访问当前节点,并将其标记为已访问,然后遍历所有邻接点,若邻接点未被访问,则递归访问它。在BFS搜索中,我们使用队列来实现搜索。从起始节点开始,先访问该节点,并将其入队。然后从队列中依次取出节点,遍历其所有邻接点,若邻接点未被访问,则访问它并将其入队。
最后,在`main`函数中,我们调用`CreateGraph`函数创建图,并分别调用`DFS`和`BFS`函数进行搜索。