用C语言以邻接矩阵为存储结构,对无向图分别进行DFS(深度优先遍历)和BFS
时间: 2024-05-10 18:17:56 浏览: 26
首先,需要定义一个邻接矩阵来存储图。假设无向图有n个节点,则邻接矩阵是一个n * n的二维数组,其中matrix[i][j]表示节点i和节点j之间是否有边相连。如果有,则为1,否则为0。
下面是DFS算法的C语言代码实现:
```c
#define MAX_NODE_NUM 100 // 假设最多有100个节点
int matrix[MAX_NODE_NUM][MAX_NODE_NUM]; // 邻接矩阵
int visited[MAX_NODE_NUM]; // 标记数组,表示节点是否被访问过
void dfs(int node, int n) {
printf("%d ", node); // 输出当前节点
visited[node] = 1; // 标记当前节点已经被访问过
for (int i = 0; i < n; i++) { // 遍历与当前节点相邻的所有节点
if (matrix[node][i] == 1 && visited[i] == 0) { // 如果节点i与当前节点有边相连且节点i未被访问过
dfs(i, n); // 递归访问节点i
}
}
}
void dfsTraversal(int n) {
memset(visited, 0, sizeof(visited)); // 初始化标记数组
for (int i = 0; i < n; i++) { // 对每一个节点进行DFS遍历
if (visited[i] == 0) { // 如果节点i未被访问过
dfs(i, n); // 从节点i开始进行DFS遍历
}
}
}
```
下面是BFS算法的C语言代码实现:
```c
#define MAX_NODE_NUM 100 // 假设最多有100个节点
int matrix[MAX_NODE_NUM][MAX_NODE_NUM]; // 邻接矩阵
int visited[MAX_NODE_NUM]; // 标记数组,表示节点是否被访问过
void bfs(int start, int n) {
int queue[MAX_NODE_NUM], front = 0, rear = 0; // 定义队列
queue[rear++] = start; // 将起始节点加入队列
visited[start] = 1; // 标记起始节点已经被访问过
while (front < rear) { // 队列非空
int node = queue[front++]; // 取出队头元素
printf("%d ", node); // 输出当前节点
for (int i = 0; i < n; i++) { // 遍历与当前节点相邻的所有节点
if (matrix[node][i] == 1 && visited[i] == 0) { // 如果节点i与当前节点有边相连且节点i未被访问过
queue[rear++] = i; // 将节点i加入队列
visited[i] = 1; // 标记节点i已经被访问过
}
}
}
}
void bfsTraversal(int n) {
memset(visited, 0, sizeof(visited)); // 初始化标记数组
for (int i = 0; i < n; i++) { // 对每一个节点进行BFS遍历
if (visited[i] == 0) { // 如果节点i未被访问过
bfs(i, n); // 从节点i开始进行BFS遍历
}
}
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)