2.先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出; 4.在2中建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列; 5.在2中建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现
时间: 2024-02-11 15:05:47 浏览: 23
好的,我会尽力回答你的问题。
针对你的问题,我可以提供以下代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode* nextarc; // 下一条边
} ArcNode;
// 顶点表结点
typedef struct VNode {
char data; // 顶点信息
ArcNode* firstarc; // 第一条边
} VNode, AdjList[MAX_VERTEX_NUM];
// 图
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} Graph;
// 定义一个栈
typedef struct Stack {
int top;
int data[MAX_VERTEX_NUM];
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->top = -1;
}
// 栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 入栈
void push(Stack* s, int x) {
if (s->top == MAX_VERTEX_NUM - 1) {
printf("栈已满!\n");
return;
}
s->data[++s->top] = x;
}
// 出栈
int pop(Stack* s) {
if (isEmpty(s)) {
printf("栈已空!\n");
return -1;
}
return s->data[s->top--];
}
// 初始化图
void initGraph(Graph* g) {
int i;
g->vexnum = g->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
g->vertices[i].data = '\0';
g->vertices[i].firstarc = NULL;
}
}
// 添加顶点
void addVertex(Graph* g, char data) {
g->vertices[g->vexnum].data = data;
g->vexnum++;
}
// 添加边
void addArc(Graph* g, int v, int w) {
ArcNode* p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = w;
p->nextarc = g->vertices[v].firstarc;
g->vertices[v].firstarc = p;
g->arcnum++;
}
// 输出邻接表
void printGraph(Graph* g) {
int i;
ArcNode* p;
printf("邻接表:\n");
for (i = 0; i < g->vexnum; i++) {
printf("%c -> ", g->vertices[i].data);
p = g->vertices[i].firstarc;
while (p) {
printf("%c ", g->vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
}
// 非递归深度优先遍历
void DFS(Graph* g, int v) {
int visited[MAX_VERTEX_NUM] = { 0 }; // 标记数组
Stack s;
ArcNode* p;
initStack(&s);
push(&s, v);
while (!isEmpty(&s)) {
int i = pop(&s);
if (!visited[i]) {
visited[i] = 1;
printf("%c ", g->vertices[i].data);
p = g->vertices[i].firstarc;
while (p) {
if (!visited[p->adjvex]) {
push(&s, p->adjvex);
}
p = p->nextarc;
}
}
}
}
// 广度优先遍历
void BFS(Graph* g, int v) {
int visited[MAX_VERTEX_NUM] = { 0 }; // 标记数组
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
ArcNode* p;
printf("%c ", g->vertices[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int i = queue[front++];
p = g->vertices[i].firstarc;
while (p) {
if (!visited[p->adjvex]) {
printf("%c ", g->vertices[p->adjvex].data);
visited[p->adjvex] = 1;
queue[rear++] = p->adjvex;
}
p = p->nextarc;
}
}
}
int main() {
Graph g;
initGraph(&g);
int n, i, v, w;
char data;
printf("请输入顶点数:");
scanf("%d", &n);
printf("请输入顶点信息(用单个字符表示):");
for (i = 0; i < n; i++) {
scanf(" %c", &data);
addVertex(&g, data);
}
printf("请输入边数:");
scanf("%d", &n);
printf("请输入边信息(用两个字符表示,如 'ab' 表示从 a 到 b):\n");
for (i = 0; i < n; i++) {
scanf(" %c %c", &data, &data);
v = data - 'a';
scanf(" %c %c", &data, &data);
w = data - 'a';
addArc(&g, v, w);
}
printGraph(&g);
printf("非递归深度优先遍历结果:");
DFS(&g, 0);
printf("\n广度优先遍历结果:");
BFS(&g, 0);
printf("\n");
return 0;
}
```
这段代码实现了图的邻接表存储结构的建立、打印输出、非递归深度优先遍历和广度优先遍历。在代码中,我们使用了栈来实现非递归深度优先遍历,使用了队列来实现广度优先遍历。在输入顶点和边的信息时,我们使用了字符来表示顶点,如 'a' 表示第一个顶点,'b' 表示第二个顶点,以此类推。你可以根据自己的需要修改代码中的信息。