图的遍历：深度和广度

一位朋友

支持

贪吃蛇2

育碧

贪吃蛇2

鱼币

sfqxx_小

鱼币

jZj123

1

lhz369

领个币

完熟マンゴー

完熟マンゴー

yx565656

zhangyangyyds

1

1613551

1613551

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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. typedef int ElemType;
   
4. typedef struct Queue
   
5. {
   
6.     ElemType data;
   
7.     Queue *Qnode;
   
8. } Queue;
   
9. typedef struct graph
   
10. {
    
11.     ElemType *v;
    
12.     ElemType **p;
    
13.     ElemType *stack;
    
14.     Queue *Qhead;
    
15.     Queue *Qtail;
    
16. } graph;
    
17. void Initialization(graph *ch, ElemType n);
    
18. void create(graph *ch, ElemType n);
    
19. void enqueue(graph *ch, int nn);
    
20. int outqueue(graph *ch);
    
21. void widevisit(graph *ch, ElemType nn, ElemType n);
    
22. void depthvisit(graph *ch, ElemType nn, ElemType n);
    
23. void input(int *n, int *nn, int *option);
    
24. void freeG(graph *ch, int n);
    
25. int main(void)
    
26. {
    
27.     int n, nn, option;
    
28.     graph p;
    
29.     input(&n, &nn, &option);
    
30.     Initialization(&p, n);
    
31.     create(&p, n);
    
32.     option ? widevisit(&p, nn, n) : depthvisit(&p, nn, n);
    
33.     freeG(&p, n);
    
34.     system("pause");
    
35.     return 0;
    
36. }
    
37. void Initialization(graph *ch, ElemType n)
    
38. {
    
39.     ch->p = (ElemType **)malloc(sizeof(ElemType *) * (n + 1));
    
40.     for (int i = 0; i <= n; i++)
    
41.     {
    
42.         ch->p[i] = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    
43.     }
    
44.     ch->v = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    
45.     ch->stack = (ElemType *)malloc(sizeof(ElemType) * (n + 1));
    
46.     for (int i = 0; i <= n; i++)
    
47.     {
    
48.         ch->v[i] = 0;
    
49.         ch->stack[i] = 0;
    
50.     }
    
51.     ch->Qhead = ch->Qtail = NULL;
    
52. }
    
53. void create(graph *ch, ElemType n)
    
54. {
    
55.     printf("请输入邻接矩阵\n");
    
56.     for (int i = 1; i <= n; i++)
    
57.     {
    
58.         for (int j = 1; j <= n; j++)
    
59.         {
    
60.             scanf("%d", &(ch->p[i][j]));
    
61.         }
    
62.     }
    
63. }
    
64. void enqueue(graph *ch, int nn)
    
65. {
    
66.     Queue *p = (Queue *)malloc(sizeof(Queue));
    
67.     p->Qnode = NULL;
    
68.     p->data = nn;
    
69.     if (ch->Qhead == NULL)
    
70.     {
    
71.         ch->Qhead = ch->Qtail = p;
    
72.     }
    
73.     else
    
74.     {
    
75.         ch->Qtail->Qnode = p;
    
76.         ch->Qtail = p;
    
77.     }
    
78. }
    
79. int outqueue(graph *ch)
    
80. {
    
81.     if (ch->Qhead == NULL)
    
82.     {
    
83.         return -1;
    
84.     }
    
85.     Queue *Q = ch->Qhead;
    
86.     int temp = Q->data;
    
87.     ch->Qhead = ch->Qhead->Qnode;
    
88.     if (ch->Qhead == NULL)
    
89.     {
    
90.         ch->Qtail = NULL;
    
91.     }
    
92.     free(Q);
    
93.     return temp;
    
94. }
    
95. void widevisit(graph *ch, ElemType nn, ElemType n)
    
96. {
    
97.     printf("下面进行图的广度优先遍历\n");
    
98.     int node = nn;
    
99.     ch->v[nn] = 1;
    
100.     enqueue(ch, nn);
     
101.     while (ch->Qhead != NULL)
     
102.     {
     
103.         node = outqueue(ch);
     
104.         if (node != nn)
     
105.         {
     
106.             printf("->");
     
107.         }
     
108.         printf("%c", 'A' + node - 1);
     
109.         for (int i = 1; i <= n; i++)
     
110.         {
     
111.             if (ch->p[node][i] == 1 && ch->v[i] == 0)
     
112.             {
     
113.                 ch->v[i] = 1;
     
114.                 enqueue(ch, i);
     
115.             }
     
116.         }
     
117.     }
     
118.     putchar('\n');
     
119. }
     
120. void depthvisit(graph *ch, ElemType nn, ElemType n)
     
121. {
     
122.     printf("下面进行图的深度优先遍历\n");
     
123.     int node = nn, j = 1, top = 0, found;
     
124.     ch->v[nn] = 1;
     
125.     ch->stack[top++] = nn;
     
126.     printf("%c", 'A' + nn - 1);
     
127. 
     
128.     while (top > 0)
     
129.     {
     
130.         found = 0;
     
131.         while (j <= n)
     
132.         {
     
133.             if (ch->p[node][j] == 1 && ch->v[j] == 0)
     
134.             {
     
135.                 ch->v[j] = 1;
     
136.                 ch->stack[top++] = j;
     
137.                 printf("->%c", 'A' + j - 1);
     
138.                 node = j;
     
139.                 found = 1;
     
140.                 break;
     
141.             }
     
142.             j++;
     
143.         }
     
144.         j = 1;
     
145.         if (!found)
     
146.         {
     
147.             top--;
     
148.             if (top > 0)
     
149.             {
     
150.                 node = ch->stack[top - 1];
     
151.                 j = ch->stack[top];
     
152.             }
     
153.         }
     
154.     }
     
155.     putchar('\n');
     
156. }
     
157. 
     
158. void input(int *n, int *nn, int *option)
     
159. {
     
160.     while (1)
     
161.     {
     
162.         printf("下面将进行图的遍历，请选择深度优先遍历（输入0）或广度优先遍历（输入1）：");
     
163.         scanf("%d", &(*option));
     
164.         if (*option == 0 || *option == 1)
     
165.         {
     
166.             break;
     
167.         }
     
168.         else
     
169.         {
     
170.             printf("您的输入有误！\n\n");
     
171.         }
     
172.     }
     
173.     do
     
174.     {
     
175.         printf("请输入结点数：");
     
176.         scanf("%d", &(*n));
     
177. 
     
178.         if (*n <= 0)
     
179.         {
     
180.             printf("结点数不得小于等于0！\n");
     
181.         }
     
182.     } while (*n <= 0);
     
183.     do
     
184.     {
     
185.         printf("请选择从哪个结点开始遍历:");
     
186.         scanf("%d", &(*nn));
     
187. 
     
188.         if (*nn < 1 || *nn > *n)
     
189.         {
     
190.             printf("您的输入不正确！\n");
     
191.         }
     
192.     } while (*nn < 1 || *nn > *n);
     
193. }
     
194. void freeG(graph *ch, int n)
     
195. {
     
196.     Queue *current = ch->Qhead;
     
197.     Queue *next;
     
198.     while (current != NULL)
     
199.     {
     
200.         next = current->Qnode;
     
201.         free(current);
     
202.         current = next;
     
203.     }
     
204.     for (int i = 0; i <= n; i++)
     
205.     {
     
206.         free(ch->p[i]);
     
207.     }
     
208.     free(ch->p);
     
209.     free(ch->v);
     
210.     free(ch->stack);
     
211. }
     

复制代码

某一个“天”

某一个“天”

三体人的智子

好

三体人的智子

懂

三体人的智子

懂了