使用C语言设计一个有向图和一个无向图,建立图的邻接矩阵或邻接表的存储结构,完成有句图和无向图的 DFS (深度优先遍历)和BFS(广度优先遍历)的操作。(有向图采用邻接矩阵存储,无向图采用邻接表存储)要求给出示例和运行结果
时间: 2024-11-29 19:16:40 浏览: 1
在C语言中,我们可以分别使用邻接矩阵和邻接表来表示有向图和无向图。以下是基本的实现:
### 邻接矩阵存储结构 - 有向图
```c
typedef struct {
int size; // 图的顶点数
int **adjMatrix; // 邻接矩阵
} DirectedGraph;
void initDirectedGraph(DirectedGraph *graph, int vertices) {
graph->size = vertices;
graph->adjMatrix = (int **)malloc(sizeof(int *) * vertices);
for (int i = 0; i < vertices; i++) {
graph->adjMatrix[i] = (int *)malloc(sizeof(int) * vertices);
for (int j = 0; j < vertices; j++)
graph->adjMatrix[i][j] = 0; // 初始化为0,表示无边
}
}
// 深度优先遍历(DFS)
void dfsDirectedGraph(DirectedGraph *graph, int start) {
int visited[] = {0}; // 初始化已访问数组
dfsHelper(graph, start, visited);
}
void dfsHelper(DirectedGraph *graph, int node, int *visited) {
visited[node] = 1; // 标记已访问
printf("%d ", node); // 输出节点
// 访问所有从当前节点出发的邻居
for (int i = 0; i < graph->size; i++) {
if (graph->adjMatrix[node][i] && !visited[i]) {
dfsHelper(graph, i, visited);
}
}
}
// 广度优先遍历(BFS)
void bfsDirectedGraph(DirectedGraph *graph, int start) {
int queue[graph->size], front = 0, rear = 0;
queue[rear++] = start; // 入队
while (front < rear) {
int node = queue[front++];
printf("%d ", node);
// 将未访问过的邻居入队
for (int i = 0; i < graph->size; i++) {
if (graph->adjMatrix[node][i]) {
queue[rear++] = i;
}
}
}
}
```
### 邻接表存储结构 - 无向图
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node** adjList; // 邻接表
int vertices;
} UndirectedGraph;
void initUndirectedGraph(UndirectedGraph *graph, int vertices) {
graph->vertices = vertices;
graph->adjList = (Node**)malloc(sizeof(Node*) * vertices);
for (int i = 0; i < vertices; i++) {
graph->adjList[i] = NULL;
}
}
// 同样的DFS和BFS函数,只是邻接列表的形式需要改变
// ... (使用链表而非二维数组)
```
示例运行结果会因输入的初始图而异,但一般包括两个部分:先展示每个节点经过DFS或BFS遍历的顺序。注意,在实际应用中,DFS和BFS的具体输出取决于给定的图结构。
阅读全文