使用C语言设计一个有向图和一个无向图,建立图的邻接矩阵或邻接表的存储结构,完成有向图和无向图的 DFS (深度优先遍历)和BFS(广度优先遍历)的操作。(有向图采用邻接矩阵存储,无向图采用邻接表存储)要求给出完整代码和运行结果
时间: 2024-12-04 08:21:23 浏览: 28
在C语言中,我们可以分别创建有向图和无向图的数据结构,并实现DFS和BFS算法。这里我将提供基本的伪代码和数据结构描述,以及如何在邻接矩阵和邻接表中实现。
首先,我们先定义邻接矩阵用于有向图:
```c
#define ROWS 10 // 图的最大节点数
typedef int Graph[ROWS][ROWS];
// 初始化邻接矩阵
void initializeDirectedAdjMatrix(Graph graph) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < ROWS; j++) {
graph[i][j] = 0; // 如果没有边,则值为0
}
}
}
// 添加有向边
void addEdgeDirected(Graph graph, int src, int dest) {
graph[src][dest] = 1;
}
```
接着,邻接表用于无向图:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct AdjacencyList {
Node* head;
} AdjacencyList;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 添加无向边到邻接表
void addEdgeUndirected(AdjacencyList* adjList, int src, int dest) {
Node* newNode = createNode(dest);
newNode->next = adjList->head;
adjList->head = newNode;
newNode = createNode(src); // 对称操作添加src指向dest
newNode->next = adjList->head;
adjList->head = newNode;
}
```
接下来是DFS和BFS的基本遍历函数:
对于有向图的DFS:
```c
void dfsDirected(Graph graph, int start) {
// ... 实现递归或栈辅助的DFS ...
}
```
对于无向图的DFS:
```c
void dfsUndirected(AdjacencyList* adjList, int start) {
// ... 实现递归或栈辅助的DFS,因为是无向图,需要同时访问两个方向 ...
}
```
BFS同样适用于邻接列表,这里仅展示核心部分:
```c
void bfs Undirected(AdjacencyList* adjList, int start) {
Node** queue = (Node**)malloc(sizeof(Node*) * ROWS); // 队列数组
queue[start] = adjList->head;
while (queue[front] != NULL) {
Node* current = queue[front++];
printf("%d ", current->data);
Node* temp = current->next;
while (temp != NULL) {
if (!visited[temp->data]) { // 更新已访问标志
visited[temp->data] = true;
queue[current->data] = temp;
}
temp = temp->next;
}
}
free(queue);
}
```
请注意,这只是一个基础框架,实际的代码需要考虑内存管理、错误处理以及标记已访问节点的数组`visited[]`。运行结果取决于输入的具体图和开始节点。
阅读全文