关于#图广度优先#的问题，如何解决？
#include<stdio.h>
#define MAX 50
#define QElemType int
typedef struct {
QElemType element[MAX];
int front;
int rear;
}SeqQueue;
//初始化
void InitQueue(SeqQueue* Q) {
Q->front = Q->rear = 0;
}
//判满
int Judge_full(SeqQueue Q) {
if ((Q.rear + 1) % MAX == Q.front) {
return 1;
}
else {
return 0;
}
}
//判空
int Judge_empty(SeqQueue *Q) {
if (Q->front == Q->rear) {
return 1;
}
else {
return 0;
}
}
//入队
int EnterQueue(SeqQueue* Q, QElemType x) {
if ((Q->rear + 1) % MAX == Q->front) {
return 0;
}
Q->element[Q->rear] = x;
Q->rear = (Q->rear + 1) % MAX;
return 1;
}
//出队
int DeleteQueue(SeqQueue* Q, QElemType* x) {
if (Q->front == Q->rear) return 0;
*x = Q->element[Q->front];
Q->front = (Q->front + 1) % MAX;
return 1;
}
//出队_1
int pop(SeqQueue* qu) {
int temp;
if (qu->rear == qu->front) {
printf("队列为空无法出队\n");
}
else {
qu->front++;
temp = qu->element[qu->front - 1];
return temp;
}
}
//读取队头元素
int ReadHeadElem(SeqQueue Q, QElemType* x) {
if (Q.front == Q.rear)return 0;
*x = Q.element[Q.front];
return 1;
}
//读取队尾元素
int ReadEndElem(SeqQueue Q, QElemType* x) {
if ((Q.rear + 1) % MAX == Q.front) return 0;
*x = Q.element[Q.rear];
return 1;
}
//////////////////////////////////////////
typedef enum { DG, DN, UDG, UDN }GraphKind;
typedef char VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcNode {
int adjvex;//存放邻接点的数组位置
struct ArcNode* nextarc;//下一条弧
InfoType* info;//存储与边相关信息
}ArcNode;
//顶点结点类型
typedef struct VNode {
VertexType data;//顶点信息
ArcNode* firstarc;//指示链中的第一个结点
}VNode, AdjList[MAX];
//图类型
typedef struct {
AdjList vertices;//顶点列表
int vexnum, arcnum;//顶点数和弧数
GraphKind kind;//图的种类标志
}ALGraph;
//创建有向图(邻接表)
void Create_ALGraph_2(ALGraph* G) {
ArcNode* e;
printf("输入顶点数:");
scanf_s("%d", &G->vexnum);
printf("输入边数:");
scanf_s("%d", &G->arcnum);
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第%d个顶点", i + 1);
scanf_s(" %c", &G->vertices[i].data, 1);
G->vertices[i].firstarc = NULL;
}
int v1, v2;
printf("请输入边之间的关系(例:AB连通->0 1):\n");
for (int i = 0; i < G->arcnum; i++) {
scanf_s(" %d %d", &v1, &v2);
e = (ArcNode*)malloc(sizeof(ArcNode));
if (e == NULL) {
printf("error!内存申请失败！");
return;
}
else {
e->adjvex = v2;
e->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = e;
}
}
}
//创建无向图（邻接表）
void Create_ALGraph_1(ALGraph* G) {
ArcNode* e;
printf("输入顶点数:");
scanf_s("%d", &G->vexnum);
printf("输入边数:");
scanf_s("%d", &G->arcnum);
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第%d个顶点:", i + 1);
scanf_s(" %c", &G->vertices[i].data, 1);
G->vertices[i].firstarc = NULL;
}
int v1, v2;
printf("请输入边之间的关系(例:AB连通->0 1):\n");
for (int i = 0; i < G->arcnum; i++) {
scanf_s(" %d %d", &v1, &v2);
e = (ArcNode*)malloc(sizeof(ArcNode));
if (e == NULL) {
printf("error！内存申请失败!");
return;
}
else {
e->adjvex = v2;
e->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = e;
}
e = (ArcNode*)malloc(sizeof(ArcNode));
if (e == NULL) {
printf("error!内存申请失败!");
return;
}
else {
e->adjvex = v1;
e->nextarc = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = e;
}
}
}
//广度优先遍历（邻接表）
void BFSTraverse_2(ALGraph *G) {
int visited[MAX],temp;
SeqQueue* qu = (SeqQueue*)malloc(sizeof(SeqQueue));
for (int i = 0; i < G->vexnum; i++) {
visited[i] = 0;
}
InitQueue(qu);
for (int i = 0; i < G->vexnum; i++) {
visited[i] = 1;
//visit_2(G, i);
printf("%c\t", G->vertices[i].data);
EnterQueue(qu, i);
while (Judge_empty(qu) != 1) {
pop(qu);
ArcNode* e = G->vertices[i].firstarc;
while (e) {
if (!visited[e->adjvex]) {
visited[e->adjvex] = 1;
//visit_2(G, e->adjvex);
printf("%c\t", G->vertices[e->adjvex].data);
EnterQueue(qu, e->adjvex);
}
e = e->nextarc;
}
}
}
}
int main() {
ALGraph abs_3;
Create_ALGraph_1(&abs_3);
BFSTraverse_2(&abs_3);
return 0;
}
利用队列想实现图（邻接表）的广度优先遍历，能运行，但结果不对，不会调试，求看一眼。
简单的看了下 发现你的问题
- 在遍历过程中,未对顶点入队操作进行判重检查,可能导致同一个顶点入队多次,应添加判重语句解决。
- 未作空图的判断,在空图的情况下,队列qu为空时无法结束遍历,应添加空图判断语句解决。
- 字符串输入未作过长输入的限制,可能导致内存溢出,应添加限制语句解决。
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7797456
- 你也可以参考下这篇文章：你不知道的几种素数判断方法，由浅入深，详解。（附送程序员必读好书）
- 除此之外, 这篇博客: 带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索中的 设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
#define MAX_VERTEX_NUM 20 //图的邻接表存储表示
typedef struct ArcNode{
int adjvex； //该弧所指向的顶点的位置
struct ArcNode *nextarc； //指向下一条弧的指针
InfoType *info； //该弧相关信息的指针
}ArcNode；
typedef struct VNode {
VertexType data； //顶点信息
ArcNode *firstarc； //指向第一条依附该顶点弧的指针
}VNode，AdjList[MAX_VERTEX_NUM]
Typedef struct {
AdjList vertices；
int vexnum，arcnum； //图的当前顶点数和弧数
int kind； //图的种类标志
}ALGraph； - 您还可以看一下 张传波老师的软件设计是怎样炼成的？课程中的 什么是漂亮的软件设计？小节, 巩固相关知识点
- 以下回答来自chatgpt:
我可以提供一些关于使用队列实现图的广度优先遍历的一般步骤和调试方法。
步骤如下：
- 选择合适的数据结构来表示图（如邻接表）。
- 初始化队列和标记数组，将起点放入队列并标记为已访问。
- 循环以下步骤，直到队列为空：
- 取出队首元素 u。
- 遍历 u 所有没有被访问过的邻居 v，将其放入队列并标记为已访问。
- 遍历结束。
调试的方法如下：
- 打印出邻接表和起点。
- 在每个循环迭代的时候，打印出队列中的元素和标记数组的状态。
- 对于不正确的结果，尝试手动按照算法步骤迭代，并检查每个步骤是否和代码逻辑一致。
- 针对具体问题，使用调试工具来单步执行程序，观察变量的值和代码控制流程，找到问题所在。
以下是Python实现队列的示例代码：
class Queue: def __init__(self): self.items = [] def is_empty(self): return not bool(self.items) def enqueue(self, item): self.items.append(item) def dequeue(self): if not self.is_empty(): return self.items.pop(0) def size(self): return len(self.items)代码实现的示例（假设图的邻接表已经实现），请注意其中的队列使用：
def bfs(graph, start): visited = [False] * len(graph) queue = Queue() queue.enqueue(start) visited[start] = True result = [] while not queue.is_empty(): current = queue.dequeue() result.append(current) for neighbor in graph[current]: if not visited[neighbor]: queue.enqueue(neighbor) visited[neighbor] = True return result
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^