C语言实现图的遍历

王小二° · 发表于 2024-6-5 23:31:07

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct Node
{
        int elem;
        struct Node *next;
}Node,*QNode;
typedef struct
{
        QNode front;
        QNode rear;
}Queue;
#define MAX 20

typedef struct ArcNode       //表结点
{
        int adjvex;              //该边所指向的顶点的位置
        struct ArcNode *nextarc; //指向下一条边
}ArcNode;

typedef struct VNode           //头结点
{
        int data;                //顶点信息
        ArcNode *firstarc;       //指向第一条依附该结点的边的指针
}VNode,AdjList[MAX];

typedef struct
{
        AdjList vertices;     //一维数组（头结点）
        int vexnum;           //结点的个数
        int arcnum;           //边的条数
}Graph;
Queue* InitQueue(Queue *Q)
{
        Q->front=(QNode)malloc(sizeof(Node));
        if(Q->front!=NULL)  
        {
                Q->rear=Q->front;
                Q->front->next=NULL;
                return Q;
        }

        else return NULL;
}
Status EnQueue(Queue *Q,int e)
{
        
        QNode newnode;
        newnode=(QNode)malloc(sizeof(Node));
        if(newnode!=NULL)
        {
                newnode->elem=e;
                newnode->next=NULL;
                Q->rear->next=newnode;
                Q->rear=newnode;
                return OK;
        }
        else return FALSE;
}
Status DeQueue(Queue *Q,int *e)
{
        QNode p;
        if(Q->front==Q->rear)
        {
                return 0;
        }
        p=Q->front->next;
        Q->front->next=p->next;
        if(Q->rear==p)
                Q->rear=Q->front;
        *e=p->elem;
        free(p);
        return 1;
}

int LocateVex(Graph *G,int index)
{
        int i;
        for(i=0;i<G->vexnum;i++)
        {
                if(G->vertices[i].data==index)
                        return i;
        }
}

Status CreateGraph(Graph *G)//Status CreateGraph(Graph &G)(引用参数）
{//以邻接表形式创建无向图G
        int m,n,i,j,k,v1,v2,flag=0;
        ArcNode *p1,*q1,*p,*q;
        printf("请输入VNode的编号: ");
        scanf("%d",&m);
        printf("请输入ArcNode的编号");
        scanf("%d",&n);
        G->vexnum=m;            //顶点数目
        G->arcnum=n;            //边的数目
        for(i=0;i<G->vexnum;++i)
        {
                G->vertices[i].data=i+1;      //顶点信息
                G->vertices[i].firstarc=NULL;
        }
        //顶点信息
        printf("输出VNode的消息:\n");
        for(i=0;i<G->vexnum;++i)
                printf("v%d\n",G->vertices[i].data);
        
        for(k=0;k<G->arcnum;++k)
        {
                printf("请输入%d边起始点和端点: ",k+1);
                scanf("%d%d",&v1,&v2);
                i=LocateVex(G,v1);
                j=LocateVex(G,v2);
                
                if(i>=0&&j>=0)
                {
                        ++flag;
                        p=(ArcNode *)malloc(sizeof(ArcNode));
                        p->adjvex=j;
                        p->nextarc=NULL;
                        if(!G->vertices[i].firstarc)
                                G->vertices[i].firstarc=p;
                        else
                        {
                                for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc);
                                p1->nextarc=p;
                        }
                        
                        q=(ArcNode *)malloc(sizeof(ArcNode));
                        q->adjvex=i;
                        q->nextarc=NULL;
                        if(!G->vertices[j].firstarc)
                                G->vertices[j].firstarc=q;
                        else
                        {
                                for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc);
                                q1->nextarc=q;
                        }
                }
                else
                {
                        printf("没有这个优势!\n");
                        k=flag-1;
                }
                
        }
        
        printf("邻接表为:\n"); //输出邻接表
        for(i=0;i<G->vexnum;++i)
        {
                printf("\t%d v%d->",i,G->vertices[i].data);
                p=G->vertices[i].firstarc;
                while(p->nextarc)
                {
                        printf("%d->",p->adjvex);
                        p=p->nextarc;
                }
                printf("%d\n",p->adjvex);
        }
        return OK;
}

int FirstAdjVex(Graph G,int v)
{//返回v的第一个邻接顶点
        ArcNode *p;
        p=G.vertices[v].firstarc;
        if(p)
                return (p->adjvex);
        else
                return -1;
}


int NextAdjVex(Graph G,int v,int w)
{//返回v中相对于w的下一个邻接顶点
        int flag=0;
        ArcNode *p;
        p=G.vertices[v].firstarc;
        while(p)
        {
                if(p->adjvex==w)
                {
                        flag=1;
                        break;
                }
                p=p->nextarc;
        }
        if(flag && p->nextarc)
                return p->nextarc->adjvex;
        else
                return -1;
}

int Visited[MAX];

void DFS(Graph G,int v)
{//深度优先遍历
        
        ArcNode *p;
        p=G.vertices[v].firstarc;
        printf("%d ",G.vertices[v].data);
        Visited[v]=TRUE;
        while(p)
        {
                if(!Visited[p->adjvex])
                {
                
                        DFS(G,p->adjvex);
                }
                p=p->nextarc;
                
        }
}

void DFSTraverse(Graph G)
{
        int i;//递归
        for(i=0;i<G.vexnum;i++)
        {
                Visited[i]=FALSE;
        }
        for(i=0;i<G.vexnum;i++)
        {
                if(!Visited[i])
                        DFS(G,i);
        }
}

void BFSTraverse(Graph G)
{//广度优先遍历
        int i,index;
        ArcNode *temp;
        Queue* que=InitQueue(que);
        
        for(i=0;i<G.vexnum;i++)
        {
                Visited[i]=0;
        }
        index=G.vertices[0].data;
        if(!Visited[index])
        {
                EnQueue(que,index);
                Visited[index]=1;
                while(que->rear!=que->front)
                {
                        DeQueue(que,&index);
                        
                        printf("%d ",G.vertices[index].data);
                        temp=G.vertices[index].firstarc;
                        while(temp)
                        {
                                index=LocateVex(&G,G.vertices[index].data);
                                if(!Visited[index])
                                {
                                        EnQueue(que,index);
                                        Visited[index]=1;
                                }
                                temp=temp->nextarc;
                                
                        }
                }
        }
        
}

void main()
                        {
                                Graph G;
                                CreateGraph(&G);
                                printf("深度优先搜索:\n");
                                DFSTraverse(G);
                                printf("\n广度优先搜索:\n");
                                BFSTraverse(G);
                                printf("\n");
                                system("pause");
                        }

能不能帮忙看看为什么广度遍历不成功啊，急

小甲鱼的二师兄 · 发表于 2024-6-5 23:31:08

本帖最后由小甲鱼的二师兄于 2024-6-5 23:45 编辑

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef struct Node {
    int elem;
    struct Node *next;
} Node, *QNode;

typedef struct {
    QNode front;
    QNode rear;
} Queue;

#define MAX 20

typedef struct ArcNode {       // 表结点
    int adjvex;                // 该边所指向的顶点的位置
    struct ArcNode *nextarc;   // 指向下一条边
} ArcNode;

typedef struct VNode {         // 头结点
    int data;                  // 顶点信息
    ArcNode *firstarc;         // 指向第一条依附该结点的边的指针
} VNode, AdjList[MAX];

typedef struct {
    AdjList vertices;          // 一维数组（头结点）
    int vexnum;                // 结点的个数
    int arcnum;                // 边的条数
} Graph;

// 初始化队列
Queue* InitQueue(Queue *Q) {
    Q->front = (QNode)malloc(sizeof(Node));
    if (Q->front != NULL) {
        Q->rear = Q->front;
        Q->front->next = NULL;
        return Q;
    } else {
        return NULL;
    }
}

// 入队
Status EnQueue(Queue *Q, int e) {
    QNode newnode;
    newnode = (QNode)malloc(sizeof(Node));
    if (newnode != NULL) {
        newnode->elem = e;
        newnode->next = NULL;
        Q->rear->next = newnode;
        Q->rear = newnode;
        return OK;
    } else {
        return FALSE;
    }
}

// 出队
Status DeQueue(Queue *Q, int *e) {
    QNode p;
    if (Q->front == Q->rear) {
        return 0;
    }
    p = Q->front->next;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    *e = p->elem;
    free(p);
    return 1;
}

// 查找顶点位置
int LocateVex(Graph *G, int index) {
    int i;
    for (i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].data == index)
            return i;
    }
    return -1;  // 如果找不到顶点，返回-1
}

// 创建图
Status CreateGraph(Graph *G) {
    int m, n, i, j, k, v1, v2;
    ArcNode *p1, *q1, *p, *q;
    printf("请输入VNode的编号: ");
    scanf("%d", &m);
    printf("请输入ArcNode的编号: ");
    scanf("%d", &n);
    G->vexnum = m;            // 顶点数目
    G->arcnum = n;            // 边的数目

    for (i = 0; i < G->vexnum; ++i) {
        G->vertices[i].data = i + 1;      // 顶点信息
        G->vertices[i].firstarc = NULL;
    }

    printf("输出VNode的信息:\n");
    for (i = 0; i < G->vexnum; ++i)
        printf("v%d\n", G->vertices[i].data);

    for (k = 0; k < G->arcnum; ++k) {
        printf("请输入第%d条边的起始点和终点: ", k + 1);
        scanf("%d%d", &v1, &v2);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);

        if (i >= 0 && j >= 0) {
            p = (ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex = j;
            p->nextarc = NULL;
            if (!G->vertices[i].firstarc)
                G->vertices[i].firstarc = p;
            else {
                for (p1 = G->vertices[i].firstarc; p1->nextarc; p1 = p1->nextarc);
                p1->nextarc = p;
            }

            q = (ArcNode *)malloc(sizeof(ArcNode));
            q->adjvex = i;
            q->nextarc = NULL;
            if (!G->vertices[j].firstarc)
                G->vertices[j].firstarc = q;
            else {
                for (q1 = G->vertices[j].firstarc; q1->nextarc; q1 = q1->nextarc);
                q1->nextarc = q;
            }
        } else {
            printf("没有这个顶点!\n");
            --k;  // 如果顶点不存在，重新输入这条边
        }
    }

    printf("邻接表为:\n");  // 输出邻接表
    for (i = 0; i < G->vexnum; ++i) {
        printf("\t%d v%d->", i, G->vertices[i].data);
        p = G->vertices[i].firstarc;
        while (p) {
            printf("%d->", p->adjvex);
            p = p->nextarc;
        }
        printf("NULL\n");
    }
    return OK;
}

int Visited[MAX];  // 访问标志数组

// 广度优先遍历
void BFSTraverse(Graph G) {
    int i, index;
    ArcNode *temp;
    Queue que;
    InitQueue(&que);

    for (i = 0; i < G.vexnum; i++) {
        Visited[i] = 0;  // 初始化访问标志数组
    }

    for (i = 0; i < G.vexnum; i++) {
        if (!Visited[i]) {
            EnQueue(&que, i);
            Visited[i] = 1;
            while (que.rear != que.front) {
                DeQueue(&que, &index);
                printf("%d ", G.vertices[index].data);
                temp = G.vertices[index].firstarc;
                while (temp) {
                    if (!Visited[temp->adjvex]) {
                        EnQueue(&que, temp->adjvex);
                        Visited[temp->adjvex] = 1;
                    }
                    temp = temp->nextarc;
                }
            }
        }
    }
    printf("\n");
}

int main() {
    Graph G;
    CreateGraph(&G);
    printf("广度优先遍历结果：\n");
    BFSTraverse(G);
    return 0;
}

王小二° · 发表于 2024-6-6 00:02:31

小甲鱼的二师兄发表于 2024-6-5 23:44

感谢感谢

王小二° · 发表于 2024-6-6 00:03:56

小甲鱼的二师兄发表于 2024-6-5 23:31

麻烦问一下，我的bfs函数问题出在哪里啊？

账号		自动登录	找回密码
密码			立即注册

[C\C++] C语言实现图的遍历

最佳答案