使用C++,编写具体函数实现对无向图的创建,并进行DFS和BFS操作
时间: 2024-05-30 07:13:39 浏览: 96
好的,下面是对于无向图的创建、DFS、BFS的C语言实现代码:
// 定义无向图结构体
typedef struct _UndirectedGraph {
int vertexNum; // 顶点个数
int **edgeMatrix; // 邻接矩阵
} UndirectedGraph;
// 创建无向图
UndirectedGraph *createUndirectedGraph(int vertexNum) {
UndirectedGraph *graph = (UndirectedGraph *) malloc(sizeof(UndirectedGraph));
graph->vertexNum = vertexNum;
// 初始化邻接矩阵
graph->edgeMatrix = (int **) malloc(vertexNum * sizeof(int *));
for (int i = 0; i < vertexNum; i++) {
graph->edgeMatrix[i] = (int *) malloc(vertexNum * sizeof(int));
memset(graph->edgeMatrix[i], 0, vertexNum * sizeof(int));
}
return graph;
}
// 添加边
void addEdge(UndirectedGraph *graph, int vertex1, int vertex2) {
graph->edgeMatrix[vertex1][vertex2] = 1;
graph->edgeMatrix[vertex2][vertex1] = 1;
}
// DFS遍历
void DFS(UndirectedGraph *graph, int startVertex, int *visited) {
visited[startVertex] = 1;
printf("%d ", startVertex);
for (int i = 0; i < graph->vertexNum; i++) {
if (graph->edgeMatrix[startVertex][i] == 1 && !visited[i]) {
DFS(graph, i, visited);
}
}
}
// BFS遍历
void BFS(UndirectedGraph *graph, int startVertex, int *visited) {
int queue[graph->vertexNum];
int front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front < rear) {
int vertex = queue[front++];
printf("%d ", vertex);
for (int i = 0; i < graph->vertexNum; i++) {
if (graph->edgeMatrix[vertex][i] == 1 && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
// 示例程序
int main() {
UndirectedGraph *graph = createUndirectedGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
int visited[graph->vertexNum];
memset(visited, 0, graph->vertexNum * sizeof(int));
printf("DFS: ");
DFS(graph, 0, visited);
printf("\n");
memset(visited, 0, graph->vertexNum * sizeof(int));
printf("BFS: ");
BFS(graph, 0, visited);
return 0;
}
阅读全文