论坛 › 数据结构与算法 › 图的遍历：深度和广度

一位朋友 发表于 2023-3-26 19:38:28

支持{:5_108:}

贪吃蛇2 发表于 2023-3-28 17:57:06

育碧

贪吃蛇2 发表于 2023-3-28 17:57:39

鱼币

sfqxx_小 发表于 2023-5-13 11:22:53

鱼币

jZj123 发表于 2023-6-7 00:25:01

1

lhz369 发表于 2023-6-7 17:57:10

领个币

完熟マンゴー 发表于 2023-7-13 11:07:24

{:10_254:}

完熟マンゴー 发表于 2023-8-14 22:28:26

{:10_254:}

yx565656 发表于 2023-8-17 23:53:33

{:5_109:}

zhangyangyyds 发表于 2023-10-17 16:36:38

1

1613551 发表于 2023-12-10 21:27:05

{:10_254:}

1613551 发表于 2023-12-12 21:10:25

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

下面这个是我在基础你程序的基础上我自己做的一点小改进
#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 = (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 = 0;
      ch->stack = 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));
      }
    }
}
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 = 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 == 1 && ch->v == 0)
            {
                ch->v = 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 = 1;
    ch->stack = nn;
    printf("%c", 'A' + nn - 1);

    while (top > 0)
    {
      found = 0;
      while (j <= n)
      {
            if (ch->p == 1 && ch->v == 0)
            {
                ch->v = 1;
                ch->stack = j;
                printf("->%c", 'A' + j - 1);
                node = j;
                found = 1;
                break;
            }
            j++;
      }
      j = 1;
      if (!found)
      {
            top--;
            if (top > 0)
            {
                node = ch->stack;
                j = ch->stack;
            }
      }
    }
    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);
    }
    free(ch->p);
    free(ch->v);
    free(ch->stack);
}

某一个“天” 发表于 2024-2-4 07:46:49

{:10_256:}

某一个“天” 发表于 2024-2-6 22:58:07

{:10_256:}

三体人的智子 发表于 2024-2-20 17:28:23

好

三体人的智子 发表于 2024-2-20 17:29:06

懂

三体人的智子 发表于 2024-2-20 17:29:44

懂了

ZZxxccvvbbnnmm 发表于 2024-5-14 18:54:20

MMnnbbvvccxxzz 发表于 2024-5-14 18:54:42

MMnnbbvvccxxzz 发表于 2024-5-14 18:55:25

查看完整版本: 图的遍历：深度和广度