图的遍历：深度和广度

追梦少年啊

鱼币

一位朋友

支持

贪吃蛇2

育碧

贪吃蛇2

鱼币

sfqxx_小

鱼币

jZj123

1

lhz369

领个币

完熟マンゴー

完熟マンゴー

yx565656

zhangyangyyds

1

1613551

1613551

老哥谢谢你，之前在网上看了半天网课，没看懂图到底讲啥，要怎么编，直到看到了你的程序，醍醐灌顶。

下面这个是我在基础你程序的基础上我自己做的一点小改进

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Queue
{
    ElemType data;
    Queue *Qnode;
} Queue;
typedef struct graph
{
    ElemType *v;
    ElemType **p;
    ElemType *stack;
    Queue *Qhead;
    Queue *Qtail;
} graph;
void Initialization(graph *ch, ElemType n);
void create(graph *ch, ElemType n);
void enqueue(graph *ch, int nn);
int outqueue(graph *ch);
void widevisit(graph *ch, ElemType nn, ElemType n);
void depthvisit(graph *ch, ElemType nn, ElemType n);
void input(int *n, int *nn, int *option);
void freeG(graph *ch, int n);
int main(void)
{
    int n, nn, option;
    graph p;
    input(&n, &nn, &option);
    Initialization(&p, n);
    create(&p, n);
    option ? widevisit(&p, nn, n) : depthvisit(&p, nn, n);
    freeG(&p, n);
    system("pause");
    return 0;
}
void Initialization(graph *ch, ElemType n)
{
    ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    }
    ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    for (int i = 0; i <= n; i++)
    {
        ch->v[i] = 0;
        ch->stack[i] = 0;
    }
    ch->Qhead = ch->Qtail = NULL;
}
void create(graph *ch, ElemType n)
{
    printf("请输入邻接矩阵\n");
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &(ch->p[i][j]));
        }
    }
}
void enqueue(graph *ch, int nn)
{
    Queue *p = (Queue *)malloc(sizeof(Queue));
    p->Qnode = NULL;
    p->data = nn;
    if (ch->Qhead == NULL)
    {
        ch->Qhead = ch->Qtail = p;
    }
    else
    {
        ch->Qtail->Qnode = p;
        ch->Qtail = p;
    }
}
int outqueue(graph *ch)
{
    if (ch->Qhead == NULL)
    {
        return -1;
    }
    Queue *Q = ch->Qhead;
    int temp = Q->data;
    ch->Qhead = ch->Qhead->Qnode;
    if (ch->Qhead == NULL)
    {
        ch->Qtail = NULL;
    }
    free(Q);
    return temp;
}
void widevisit(graph *ch, ElemType nn, ElemType n)
{
    printf("下面进行图的广度优先遍历\n");
    int node = nn;
    ch->v[nn] = 1;
    enqueue(ch, nn);
    while (ch->Qhead != NULL)
    {
        node = outqueue(ch);
        if (node != nn)
        {
            printf("->");
        }
        printf("%c", 'A' + node - 1);
        for (int i = 1; i <= n; i++)
        {
            if (ch->p[node][i] == 1 && ch->v[i] == 0)
            {
                ch->v[i] = 1;
                enqueue(ch, i);
            }
        }
    }
    putchar('\n');
}
void depthvisit(graph *ch, ElemType nn, ElemType n)
{
    printf("下面进行图的深度优先遍历\n");
    int node = nn, j = 1, top = 0, found;
    ch->v[nn] = 1;
    ch->stack[top++] = nn;
    printf("%c", 'A' + nn - 1);

    while (top > 0)
    {
        found = 0;
        while (j <= n)
        {
            if (ch->p[node][j] == 1 && ch->v[j] == 0)
            {
                ch->v[j] = 1;
                ch->stack[top++] = j;
                printf("->%c", 'A' + j - 1);
                node = j;
                found = 1;
                break;
            }
            j++;
        }
        j = 1;
        if (!found)
        {
            top--;
            if (top > 0)
            {
                node = ch->stack[top - 1];
                j = ch->stack[top];
            }
        }
    }
    putchar('\n');
}

void input(int *n, int *nn, int *option)
{
    while (1)
    {
        printf("下面将进行图的遍历，请选择深度优先遍历（输入0）或广度优先遍历（输入1）：");
        scanf("%d", &(*option));
        if (*option == 0 || *option == 1)
        {
            break;
        }
        else
        {
            printf("您的输入有误！\n\n");
        }
    }
    do
    {
        printf("请输入结点数：");
        scanf("%d", &(*n));

        if (*n <= 0)
        {
            printf("结点数不得小于等于0！\n");
        }
    } while (*n <= 0);
    do
    {
        printf("请选择从哪个结点开始遍历:");
        scanf("%d", &(*nn));

        if (*nn < 1 || *nn > *n)
        {
            printf("您的输入不正确！\n");
        }
    } while (*nn < 1 || *nn > *n);
}
void freeG(graph *ch, int n)
{
    Queue *current = ch->Qhead;
    Queue *next;
    while (current != NULL)
    {
        next = current->Qnode;
        free(current);
        current = next;
    }
    for (int i = 0; i <= n; i++)
    {
        free(ch->p[i]);
    }
    free(ch->p);
    free(ch->v);
    free(ch->stack);
}

某一个“天”

某一个“天”

三体人的智子

好

三体人的智子

懂

三体人的智子

懂了