一个无向图 V(G1)={0,1,2,3,4,5,6,7,8,9,10} 边集合 E(G1)={(0,1),(0,2),(0,3),(1,4),(1,5),(2,5),(2,6),(3,7),(6,8),(6,9),(7,10)}由用户输入一个结点的值,输出该结点的深度优先遍历和广度优先遍历序列,用c语言完成上述代码
时间: 2023-06-19 22:05:38 浏览: 115
以下是使用 C 语言实现给定无向图的深度优先遍历(DFS)和广度优先遍历(BFS)序列的代码。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 11
int adjacency_matrix[MAX_NODES][MAX_NODES];
int visited[MAX_NODES];
int queue[MAX_NODES];
int front = -1, rear = -1;
void DFS(int node) {
visited[node] = 1;
printf("%d ", node);
for(int i=0; i<MAX_NODES; i++) {
if(adjacency_matrix[node][i] && !visited[i]) {
DFS(i);
}
}
}
void BFS(int start_node) {
visited[start_node] = 1;
queue[++rear] = start_node;
while(front != rear) {
int current_node = queue[++front];
printf("%d ", current_node);
for(int i=0; i<MAX_NODES; i++) {
if(adjacency_matrix[current_node][i] && !visited[i]) {
visited[i] = 1;
queue[++rear] = i;
}
}
}
}
int main() {
int node;
printf("Enter a node: ");
scanf("%d", &node);
// Initialize adjacency matrix
for(int i=0; i<MAX_NODES; i++) {
for(int j=0; j<MAX_NODES; j++) {
adjacency_matrix[i][j] = 0;
}
}
adjacency_matrix[0][1] = adjacency_matrix[1][0] = 1;
adjacency_matrix[0][2] = adjacency_matrix[2][0] = 1;
adjacency_matrix[0][3] = adjacency_matrix[3][0] = 1;
adjacency_matrix[1][4] = adjacency_matrix[4][1] = 1;
adjacency_matrix[1][5] = adjacency_matrix[5][1] = 1;
adjacency_matrix[2][5] = adjacency_matrix[5][2] = 1;
adjacency_matrix[2][6] = adjacency_matrix[6][2] = 1;
adjacency_matrix[3][7] = adjacency_matrix[7][3] = 1;
adjacency_matrix[6][8] = adjacency_matrix[8][6] = 1;
adjacency_matrix[6][9] = adjacency_matrix[9][6] = 1;
adjacency_matrix[7][10] = adjacency_matrix[10][7] = 1;
// Initialize visited array
for(int i=0; i<MAX_NODES; i++) {
visited[i] = 0;
}
printf("DFS sequence: ");
DFS(node);
printf("\n");
// Reset visited array
for(int i=0; i<MAX_NODES; i++) {
visited[i] = 0;
}
printf("BFS sequence: ");
BFS(node);
printf("\n");
return 0;
}
```
注意:这个代码假定输入的节点值是合法的,即在给定的节点集合中。如果输入的节点值不合法,程序可能会导致崩溃或意外行为。
阅读全文