C语言用栈实现无向图邻接矩阵广度优先遍历

Question

C语言用栈实现无向图邻接矩阵广度优先遍历(是的，广度。不是深度)目前已经写了如下代码，如图初步的构想是：用数组或结构体记录每个顶点所在层数，从顶点1开始遍历，栈空代表某顶点下一层的邻接顶点已全部输出。这个构想对吗？不对的话，有没有什么方法实现？还是说只能用两个栈做成一个队列？

//定义邻接矩阵
typedef struct {
    int Edges[MAX][MAX];//邻接矩阵
    int vexnum;//当前顶点个数
}MGraph;

//邻接矩阵函数
int CreatMGraph(MGraph &G)//从文件读取并输出邻接矩阵
{
    FILE *fp;
    if((fp=fopen("graph.txt","r"))==NULL)
    {
      printf("文件打开失败\n");
      return 0;
    }
 
    fscanf(fp,"%d",&G.vexnum);
    int i,j;
 
    for(i=1;i<=G.vexnum;i++)
    {
     for(j=1;j<=G.vexnum;j++)
       fscanf(fp,"%d",&G.Edges[i][j]);
    }
    fclose(fp);
   
        //输出边矩阵
    printf("创建无向图G1邻接矩阵如下：\n");
    printf("G1顶点个数%d\n",G.vexnum);
    for(i=1;i<=G.vexnum;i++)
    {
        for(j=1;j<=G.vexnum;j++)
        {
         printf("%d ",G.Edges[i][j]);
        }
        printf("\n");
    }
    return 1;
}
int FirstAdjvex(MGraph G,int i)//寻找邻接矩阵顶点i的第一个邻接顶点
{
    int k;
    for(k=1;k<=G.vexnum;k++)//遍历第i行的各列
    {
      if(G.Edges[i][k]==1)
          return k;//找到第一个邻接顶点
    }
    return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}
int NextAdjvex(MGraph G,int i,int j)//寻找邻接矩阵顶点i继其邻接点j后的第一个邻接点
{
    int k;
    for(k=j+1;k<=G.vexnum;k++)//遍历第i行的各列
    {
      if(G.Edges[i][k]==1)
          return k;//找到第一个邻接顶点
    }
    return 0;//若循环没有中间跳出,即循环中没有返回值,说明顶点i没有邻接点
}

void StackBFStraverse(MGraph G)//利用栈进行广度优先遍历并判断连通性
{
    printf("G1栈广度优先遍历序列如下\n");
    int i,j,k,count=0;Sqstack S;int visited[MAX];
    for(i=1;i<=G.vexnum;++i)
        visited[i]=0;
    InitStack(S);
    while(层数是1)
    {
        k=1;
        printf("%d",1);
        for(k=;k;k=)
        {
            
        }
        
    }
    
printf("\n");
    if(count==1) printf("G1是连通图\n");
    else printf("G1不是连通图,联通分量%d个\n",count);
}

供参考：队列广度优先遍历

void SqueueBFStraverse(MGraph G)//利用队列进行广度优先遍历并判断连通性
{
    printf("G1队列广度优先遍历如下\n");
 int i,j,k,count=0;Squeue Q;int visited[MAX];
 for(i=1;i<=G.vexnum;++i)
     visited[i]=0;
 InitQueue(Q);
 for(i=1;i<=G.vexnum;++i)
 {
     if(!visited[i])
     {
         visited[i]=1;
         count++;
         printf("%d",i);
         Enqueue(Q,i);
         while(!QueueEmpty(Q))
         {
             Dequeue(Q,j);//出队的队头元素设为j
             for(k=FirstAdjvex(G,j);k;k=NextAdjvex(G,j,k))
             {
                  if(!visited[k])
                 {
                     visited[k]=1;
                     printf("%d",k);
                     Enqueue(Q,k);
                 }

             }
                
         }
     }
 }
 printf("\n");
    if(count==1) printf("G1是连通图\n");
    else printf("G1不是连通图,连通分量%d个\n",count);
}

邻接矩阵文件
8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
自定义栈的头文件

#include <stdio.h>
#include <stdlib.h>
#define MAX 11
typedef struct{
    int data[MAX];//栈中元素
    int top;//栈顶指针
}Sqstack;
int InitStack(Sqstack &S)
{
    S.top=-1;//数组下标从0开始,空栈顶指针指向栈底部-1
    return 1;
}
int StackEmpty(Sqstack &S)
{
    if(S.top==-1) return 1;
    else return 0;
}
int Push(Sqstack &S,int e)//进栈
{
    if(S.top==MAX-1) return 0;
    S.top++;
    S.data[S.top]=e;
    return 1;
}
int Pop(Sqstack &S,int &e)//出栈
{
    if(S.top==-1) return 0;
    e=S.data[S.top];
    S.top--;
    return 1;
}
int GetTop(Sqstack S,int &e)//取栈顶元素
{
    if(S.top==-1) return 0;
    e=S.data[S.top];
    return 1;
}

Answer 1

该回答引用ChatGPT，望对题主有所帮助/启发；若有帮助，还望采纳。

---

你的构想是用栈来实现广度优先遍历，但是广度优先遍历通常需要使用队列来实现，而不是用栈。栈通常用于深度优先遍历。所以你可以采用两个栈来实现一个队列，或者直接使用队列来实现广度优先遍历。

这里给出使用队列实现广度优先遍历的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义队列结构
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

// 入队操作
void enqueue(Queue* q, int value) {
    q->data[q->rear++] = value;
}

// 出队操作
int dequeue(Queue* q) {
    return q->data[q->front++];
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 广度优先遍历
void BFS(MGraph G) {
    int visited[MAX] = {0}; // 标记顶点是否被访问
    Queue queue;
    initQueue(&queue);

    visited[1] = 1; // 从顶点1开始遍历
    enqueue(&queue, 1);

    while (!isEmpty(&queue)) {
        int vertex = dequeue(&queue);
        printf("%d ", vertex);

        for (int i = 1; i <= G.vexnum; i++) {
            if (G.Edges[vertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(&queue, i);
            }
        }
    }
}

int main() {
    MGraph G;
    CreatMGraph(G);
    printf("BFS traversal: ");
    BFS(G);
    printf("\n");
    return 0;
}

上述代码中，我们使用一个队列来存储待你的构想基本是正确的，使用栈实现广度优先遍历图的邻接矩阵。你可以使用数组或结构体记录每个顶点所在的层数。从顶点1开始遍历，将其加入栈中，并将其层数设置为1。然后在循环中，从栈中取出一个顶点，将其周围未访问过的邻接顶点加入栈，并将它们的层数设置为当前顶点的层数加1。重复这个过程，直到栈为空。

以下是基于你提供的代码进行修改的一个示例：

// 定义栈
typedef struct {
    int data[MAX]; // 栈中元素
    int top; // 栈顶指针
} Sqstack;

// 初始化栈
int InitStack(Sqstack *S) {
    S->top = -1;
    return 1;
}

// 判断栈是否为空
int StackEmpty(Sqstack *S) {
    return (S->top == -1);
}

// 入栈
int Push(Sqstack *S, int e) {
    if (S->top == MAX - 1)
        return 0; // 栈满
    S->top++;
    S->data[S->top] = e;
    return 1;
}

// 出栈
int Pop(Sqstack *S, int *e) {
    if (S->top == -1)
        return 0; // 栈空
    *e = S->data[S->top];
    S->top--;
    return 1;
}

// 获取栈顶元素
int GetTop(Sqstack *S, int *e) {
    if (S->top == -1)
        return 0; // 栈空
    *e = S->data[S->top];
    return 1;
}

// 广度优先遍历图的邻接矩阵
void StackBFStraverse(MGraph G) {
    printf("邻接矩阵广你的初步构想有一些问题，广度优先遍历通常使用队列而不是栈。在广度优先遍历中，你需要按层次访问顶点，而栈是先进后出的数据结构，不符合广度优先的要求。所以，你的思路中应该使用队列来实现广度优先遍历。

以下是使用队列实现无向图邻接矩阵的广度优先遍历的示例代码：

```c
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    int Edges[MAX][MAX]; // 邻接矩阵
    int vexnum;          // 当前顶点个数
} MGraph;

typedef struct {
    int data[MAX];
    int front, rear;
} Squeue;

int InitQueue(Squeue &Q) {
    Q.front = Q.rear = -1;
    return 1;
}

int QueueEmpty(Squeue Q) {
    return Q.front == Q.rear;
}

int Enqueue(Squeue &Q, int e) {
    if (Q.rear == MAX - 1) {
        return 0; // 队列已满
    }
    Q.data[++Q.rear] = e;
    return 1;
}

int Dequeue(Squeue &Q, int &e) {
    if (QueueEmpty(Q)) {
        return 0; // 队列为空
    }
    e = Q.data[++Q.front];
    return 1;
}

void BFS(MGraph G, int start) {
    printf("广度优先遍历序列如下:\n");

    int visited[MAX];
    for (int i = 1; i <= G.vexnum; ++i) {
        visited[i] = 0;
    }

    Squeue Q;
    InitQueue(Q);

    int count = 0;
    for (int i = start; i <= G.vexnum; ++i) {
        if (!visited[i]) {
            visited[i] = 1;
            count++;
            printf("%d ", i);
            Enqueue(Q, i);
            while (!QueueEmpty(Q)) {
                int j;
                Dequeue(Q, j);
                for (int k = 1; k <= G.vexnum; ++k) {
                    if (G.Edges[j][k] == 1 && !visited[k]) {
                        visited[k] = 1;
                        printf("%d ", k);
                        Enqueue(Q, k);
                    }
                }
            }
        }
    }

    printf("\n");
    if (count == 1) {
        printf("图是连通图\n");
    } else {
        printf("图不是连通图，连通分量%d个\n", count);
    }
}

int main() {
    MGraph G;
    if (CreatMGraph(G)) {
        BFS(G, 1); // 从顶点1开始广度优先遍历
    }

    return 0;
}

在这个代码中，Squeue是一个简单的队列结构，使用数组实现。BFS函数使用队列实现广度优先遍历，从指定的起始顶点开始。在遍历过程中，使用一个数组 visited 记录每个顶点是否被访问过。

请注意，在实际应用中，你可能需要根据具体的问题来选择遍历的起始顶点。上述代码中，默认从顶点1开始遍历。