用C语言编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-15 15:03:06 浏览: 34
好的,这是一个关于图的算法问题,我可以帮你解答。
以下是用C语言实现该功能的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF 32767 // 无穷大
// 邻接表中的边结构体
typedef struct EdgeNode {
int adjvex; // 邻接点
int weight; // 权值
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 邻接表中的顶点结构体
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 邻接表图结构体
typedef struct {
AdjList adjList; // 邻接表数组
int vexnum, edgenum; // 顶点数和边数
} GraphAdjList;
// 初始化图
void InitGraph(GraphAdjList *G) {
int i;
for (i = 0; i < G->vexnum; i++) {
G->adjList[i].data = i;
G->adjList[i].firstedge = NULL;
}
}
// 添加边
void AddEdge(GraphAdjList *G, int v1, int v2, int w) {
EdgeNode *p1 = (EdgeNode*)malloc(sizeof(EdgeNode));
EdgeNode *p2 = (EdgeNode*)malloc(sizeof(EdgeNode));
p1->adjvex = v2;
p1->weight = w;
p1->next = G->adjList[v1].firstedge;
G->adjList[v1].firstedge = p1;
p2->adjvex = v1;
p2->weight = w;
p2->next = G->adjList[v2].firstedge;
G->adjList[v2].firstedge = p2;
}
// 深度优先搜索
void DFS(GraphAdjList *G, int i, int visited[]) {
EdgeNode *p;
visited[i] = 1;
printf("%d ", G->adjList[i].data);
p = G->adjList[i].firstedge;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先搜索
void BFS(GraphAdjList *G, int i, int visited[]) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
EdgeNode *p;
visited[i] = 1;
printf("%d ", G->adjList[i].data);
queue[rear++] = i;
while (front != rear) {
int j = queue[front++];
p = G->adjList[j].firstedge;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", G->adjList[p->adjvex].data);
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
int main() {
GraphAdjList G;
int i, v1, v2, w, visited[MAX_VERTEX_NUM] = {0};
printf("请输入顶点数和边数:");
scanf("%d %d", &G.vexnum, &G.edgenum);
InitGraph(&G);
printf("请依次输入每条边的两个顶点及它们之间的权值:\n");
for (i = 0; i < G.edgenum; i++) {
scanf("%d %d %d", &v1, &v2, &w);
AddEdge(&G, v1, v2, w);
}
printf("深度优先搜索遍历结果:");
for (i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
printf("\n");
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
printf("广度优先搜索遍历结果:");
for (i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(&G, i, visited);
}
}
printf("\n");
return 0;
}
```
使用方法:
1. 运行程序后,输入顶点数和边数。
2. 然后依次输入每条边的两个顶点及它们之间的权值。
3. 程序将输出深度优先搜索遍历结果和广度优先搜索遍历结果。
希望这个程序能够帮助到你,如果还有什么问题,欢迎随时问我。