typedef struct{ int v; int parent; }QUEUE1; int BFSA(AdjGraph *G,int u,int v){ ArcNode *p; SqQueue *qu; InitQueue(qu); int visited[MAXV]; for(int i=0;i<G->n;i++){ visited[i]=0; } QUEUE1 elem; elem.v=u; elem.parent=-1; enQueue(qu,elem); while(!QueueEmpty(qu)){ deQueue(qu,&elem); if(elem.v==v){ while(!QueueEmpty(qu)){ deQueue(qu,&elem); } break; } p=G->adjlist[elem.v].firstarc; while(p!=NULL){ int w=p->adjvex; if(visited[w]==0){ visited[w]=1; QUEUE1 new_v; new_v.v=w; new_v.parent=elem.v; enQueue(qu,new_v); } p=p->nextarc; } } if(elem.v!=v){ printf("不存在从%d到%d的路径\n",u,v); return -1; }else{ int len=0; while(elem.parent!=-1){ len++; elem=getQueueElem(qu,elem.parent); } printf("从%d到%d的最短路径长度为:%d\n",u,v,len); return len; } }修改上述代码
时间: 2023-12-02 22:02:07 浏览: 46
对于上述代码,建议进行以下修改:
1. 在函数开头加上返回类型和参数类型,如下所示:
```c++
int BFSA(AdjGraph *G,int u,int v){
```
2. 在函数中加上对队列的初始化和销毁操作,如下所示:
```c++
SqQueue *qu;
InitQueue(qu);
// ...
DestroyQueue(qu);
```
3. 将队列元素的结构体定义移到函数外部,如下所示:
```c++
typedef struct {
int v;
int parent;
} QUEUE1;
```
4. 将队列的入队操作和出队操作封装成函数,如下所示:
```c++
void enqueue(SqQueue *qu, QUEUE1 elem) {
enQueue(qu, elem);
}
QUEUE1 dequeue(SqQueue *qu) {
QUEUE1 elem;
deQueue(qu, &elem);
return elem;
}
```
5. 将函数中重复使用的变量提取出来,如下所示:
```c++
int visited[MAXV];
for (int i = 0; i < G->n; i++) {
visited[i] = 0;
}
```
6. 在函数中使用去掉前缀的变量名,如下所示:
```c++
ArcNode *p;
p = G->adjlist[elem.v].firstarc;
```
7. 将函数中的无用代码去掉,如下所示:
```c++
while (!QueueEmpty(qu)) {
deQueue(qu, &elem);
}
```
综上所述,修改后的代码如下所示:
```c++
int BFSA(AdjGraph *G, int u, int v) {
SqQueue *qu;
InitQueue(qu);
int visited[MAXV];
for (int i = 0; i < G->n; i++) {
visited[i] = 0;
}
QUEUE1 elem;
elem.v = u;
elem.parent = -1;
enqueue(qu, elem);
while (!QueueEmpty(qu)) {
elem = dequeue(qu);
if (elem.v == v) {
break;
}
ArcNode *p;
p = G->adjlist[elem.v].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (visited[w] == 0) {
visited[w] = 1;
QUEUE1 new_v;
new_v.v = w;
new_v.parent = elem.v;
enqueue(qu, new_v);
}
p = p->nextarc;
}
}
DestroyQueue(qu);
if (elem.v != v) {
printf("不存在从%d到%d的路径\n", u, v);
return -1;
} else {
int len = 0;
while (elem.parent != -1) {
len++;
elem = getQueueElem(qu, elem.parent);
}
printf("从%d到%d的最短路径长度为:%d\n", u, v, len);
return len;
}
}
```
阅读全文