编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。c语言
时间: 2023-12-14 15:39:45 浏览: 32
以下是使用邻接表表示的无向图的深度优先搜索和广度优先搜索的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表结构体
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// 图结构体
typedef struct Graph {
int numVertices;
int numEdges;
Node* adjList[MAX_VERTICES];
} Graph;
// 创建节点
Node* createNode(int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
// 添加从源节点到目标节点的边
Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
// 添加从目标节点到源节点的边
newNode = createNode(src);
newNode->next = graph->adjList[dest];
graph->adjList[dest] = newNode;
}
// 深度优先搜索遍历
void dfsTraversal(Graph* graph, int vertex, int visited[]) {
visited[vertex] = 1;
printf("%d ", vertex);
Node* adjList = graph->adjList[vertex];
while (adjList != NULL) {
int adjVertex = adjList->vertex;
if (!visited[adjVertex]) {
dfsTraversal(graph, adjVertex, visited);
}
adjList = adjList->next;
}
}
// 广度优先搜索遍历
void bfsTraversal(Graph* graph, int startVertex, int visited[]) {
int queue[MAX_VERTICES] = { 0 };
int front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front < rear) {
int vertex = queue[front++];
printf("%d ", vertex);
Node* adjList = graph->adjList[vertex];
while (adjList != NULL) {
int adjVertex = adjList->vertex;
if (!visited[adjVertex]) {
visited[adjVertex] = 1;
queue[rear++] = adjVertex;
}
adjList = adjList->next;
}
}
}
int main() {
Graph* graph = (Graph*)malloc(sizeof(Graph));
// 输入顶点数和边数
printf("Enter the number of vertices: ");
scanf("%d", &graph->numVertices);
printf("Enter the number of edges: ");
scanf("%d", &graph->numEdges);
// 初始化邻接表
for (int i = 0; i < graph->numVertices; i++) {
graph->adjList[i] = NULL;
}
// 添加边
for (int i = 0; i < graph->numEdges; i++) {
int src, dest;
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d%d", &src, &dest);
addEdge(graph, src, dest);
}
// 输出邻接表
printf("\nAdjacency List:\n");
for (int i = 0; i < graph->numVertices; i++) {
printf("Vertex %d: ", i);
Node* adjList = graph->adjList[i];
while (adjList != NULL) {
printf("%d -> ", adjList->vertex);
adjList = adjList->next;
}
printf("NULL\n");
}
// 深度优先搜索遍历
printf("\nDFS Traversal: ");
int visited[MAX_VERTICES] = { 0 };
for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
dfsTraversal(graph, i, visited);
}
}
printf("\n");
// 广度优先搜索遍历
printf("\nBFS Traversal: ");
for (int i = 0; i < graph->numVertices; i++) {
visited[i] = 0;
}
bfsTraversal(graph, 0, visited);
printf("\n");
return 0;
}
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)