Kodomo

Пользователь

Задание

Оценка за задание есть наибольшая из оценок за решённые задачи.

Задание должно быть выложено в репозиторий homework, который должен быть выложен на bitbucket. В противном случае, вне зависимости от задачи вы получаете не более 6 баллов.

Если вы хотите получить оценку выше 8 баллов, код должен быть чистым и читаемым (по существу я этого требовал и раньше). Т.е. все функции, переменные и классы имеют содержательные и понятные названия. Схема именования сущностей в одном типе сущностей однородна (т.е. либо везде сокращения, либо везде полные слова). Функции не бывают длиннее ~10 строк и не делают больше одного дела. Строки не бывают длиннее 75 символов (включая отступы). Внутри строк есть одна политика на тему того, как ставить пробелы. Части кода расположены стандартным образом: импорты -> константы и глобальные переменные -> определения (функций и классов) -> if __name__ == "__main__". Нет дублирования кода. Модуль, все функции и классы должны сопровождаться документацией. Там, где это возможно, функции должны сопровождаться примерами вызова, которые должны проходить doctest.

Я настоятельно рекомендую писать чистый код изначально (да, это значит, что иногда в очевидных, казалось бы, местах приходится на 10 минут задуматься над названием переменной), потому что так быстрее получить рабочую программу. Всё равно основное время уходит на отладку, а не на написание.

  1. (6 баллов) Дан граф в виде словаря соседей (т.е. в словаре ключ – вершина, значение – списоск соседей) и одна из вершин в нём. Написать функцию для нахождения компоненты связности, содержащей эту вершину. Функция получает на вход граф и вершину и выдаёт список вершин.

  2. (8 баллов) Дан граф в виде csv-файла (см. ниже). Напишите программу, которая найдёт в нём компоненту связности, включающую первую вершину, упомянутую в файле. Программа выводит на экран список её вершин в одну строку.

  3. (10 баллов) Дан граф в виде csv-файла (см. ниже). Напишите программу, которая найдёт в нём все компоненты связности. (Подход: взять произвольную вершину, найти компоненту связности с ней, взять любую вершину, которая ещё не в компоненте связности, повторить, взболтать). Для каждой найденной компоненты связности программа выводит на экран список её вершин в одну строку.

Пример графа для задания 1

{
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C'],
    'C': ['A', 'E'],
    'D': ['A', 'E'],
    'E': ['C', 'D'],
    'X': ['Y', 'Z'],
    'Y': ['X', 'Z'],
    'Z': ['X', 'Y'],
}

Пример графа для заданий 2-3

Неориентированный граф представлен в виде CSV-файла. Каждая строка файла описывает ребро графа. (NB: если вы представляете граф в виде словаря соседей, то строка A B должна порождать два ребра: A -> B и B -> A)

A B
A C
A D
B C
C E
D E
X Y
X Z
Y Z

Ещё один пример

282 219
205 113
410 74
39 241
92 31
7 160
387 15
195 199
290 120
94 396
106 412
70 500
296 111
222 336
362 105
54 37
265 457
242 83
442 34
109 73
432 282
24 492
333 218
126 126
422 408
376 40
73 203
259 428
259 234
117 351
235 289
423 355
125 299
193 186
432 112
120 74
403 358
7 31
358 435
269 17
485 38
352 342
308 58
372 43
499 27
174 175
66 13
129 166
117 324
38 292
121 229
354 57
98 378
62 384
379 187
332 99
56 432
179 302
92 257
169 424
319 410
281 19
210 160
142 203
469 63
327 241
439 104
494 224
74 470
275 460
168 86
165 151
30 491
286 414
283 383
158 186
179 218
364 378
228 279
368 175
378 488
251 38
104 402
361 177
53 40
472 268
189 91
368 209
127 96
20 487
107 443
382 133
348 331
222 233
144 183
49 486
137 415
309 27
430 498
259 398
218 486
444 431
497 360
328 273
479 469
236 283
1 478
82 131
353 359
343 65
309 432
122 89
435 148
251 321
268 313
462 83
213 65
457 287
231 174
482 120
131 305
415 155
231 456
196 172
354 407
52 317
413 118
105 392
449 356
179 24
420 230
66 320
113 333
346 139
12 24
271 424
230 277
499 308
297 5
178 149
142 223
233 380
44 319
160 419
220 358
23 126
265 125
227 6
472 305
53 439
20 69
483 443
195 15
120 267
299 186
183 169
146 493
62 194
211 91
286 492
264 479
96 43
263 401
383 19
74 209
61 406
0 222
213 448
355 497
358 478
478 288
336 475
16 17
472 5
31 326
496 26
217 54
34 466
474 446
333 64
492 266
381 263
258 97
407 24
331 108
171 322
468 145
430 110
178 51
443 31
468 283
462 123
77 262
342 185
441 15
157 297
486 206
215 392
177 122
112 186
459 483
307 234
304 461
203 344
305 415
72 431
246 385
339 478
53 155
345 23
442 379
170 117
120 478
141 324
304 175
356 121
283 250
0 202
131 2
366 239
246 327
367 59
137 127
373 490
323 349
370 391
18 130
105 472
472 442
427 470
159 486
475 312
79 319
69 183
392 257
25 470
286 483
39 43
153 195
348 65
217 418
119 254
157 121
470 111
219 413
209 349
69 148
38 97
242 409
325 463
393 460
375 239
63 267
182 200
129 399
289 398
65 56
92 14
87 101
142 156
259 77
301 357
237 341
70 63
74 246
214 461
370 325
431 282
147 237
320 227
347 185
454 179
446 469
58 461
285 163
381 465
294 229
206 499
433 250
263 389
375 243
132 133
85 287
369 350
498 15
146 321
234 479
324 254
9 168
140 207
362 366
221 151
122 398
33 171
210 95
112 495
407 70
353 356
412 306
246 253
408 488
108 496
11 367
438 138
48 236
89 34
282 216
368 344
172 227
25 71
234 186
10 41
217 257
210 224
107 239
275 259
124 26
69 223
155 419
260 263
53 213
468 191
379 171
409 449
136 269
246 363
102 437
135 376
363 117
456 205
377 450
56 279
286 471
257 150
307 481
86 42
331 291
36 125
474 481
5 210
166 394
157 475
218 29
253 42
32 288
202 407
315 303
192 43
29 319
92 420
379 193
349 39
353 172
295 213
216 47
9 280
465 374
309 318
304 436
235 320
268 451
401 173
21 84
259 352
283 49
382 344
265 168
214 74
269 260
400 170
439 475
29 300
91 398
281 74
402 49
387 338
286 207
77 400
184 79
318 282
460 74
146 321
65 130
8 249
201 88
250 54
202 19
343 251
397 167
186 241
268 121
138 485
79 35
335 223
362 132
85 308
251 289
428 57
284 469
445 342
401 86
234 437
375 269
267 153
380 299
417 237
65 413
223 344
356 194
167 77
471 94
352 381
11 228
224 498
199 394
391 471
366 447
369 312
260 461
435 110
444 469
404 498
396 474
166 351
414 491
383 447
32 427
449 380
133 294
263 107
300 72
182 468
188 151
372 30
319 426
419 136
137 364
95 319
251 257
96 43
6 186
374 16
314 358
482 251
125 184
7 88
487 155
467 41
28 457
243 126
398 449
47 410
257 301
201 211
240 42
224 27
345 361
52 168
223 331
472 441
196 87
259 298
360 116
22 267
497 313
235 378
325 473
495 455
54 15
246 244
155 380
450 297
111 441
352 155
411 233
480 357
171 412
288 397
277 257
4 9
194 308
162 328
439 370
242 99
41 485
257 256
419 103
302 188
459 43
100 366
466 50
192 472
299 287
164 386
324 42
81 82
406 113
8 345
258 94
170 10
390 217
267 57
438 195
216 390
364 120
352 292
491 241
196 362
313 276
71 185
473 56
150 186
463 287
401 89
140 331
22 384
490 141
335 421
449 482
446 228
16 256
250 353
249 24
474 195
372 336
465 195
444 238
271 415
185 251
382 121
494 177
6 343
59 429
165 79
22 478
416 231
152 470
190 198
374 317
158 264
233 172
20 283
439 71
174 259
341 364
119 120
42 39
83 429
58 4
128 378
313 400
173 248
414 326
344 65
173 94
208 10
230 78
382 470
324 40
491 198
448 419
169 276
6 468
445 391
480 119
179 134
332 129
269 51
382 188
129 343
269 443
477 498
497 440
104 326
33 78
70 134
350 437
449 433
107 48
322 268
444 250
393 218
338 300
471 21
186 338
100 275
280 241
40 492
7 305
231 132
28 42
270 151
262 408
388 408
158 216
108 232
251 60
169 421
223 451
21 248
483 356
500 178
238 237
289 202
40 234
435 251
172 376
181 409
295 307
55 281
354 485
313 17
13 253
386 353
91 222
383 90
7 361
104 159
343 113
230 306
227 349
414 47
152 488
238 294
417 282
402 259
264 37
112 244
173 45
178 439
20 486
33 250
94 385
20 165
183 495
51 248
274 247
265 334
179 469
279 462
367 272
216 98
435 128
420 227
412 420
407 40
138 174
236 136
24 172
465 392
405 331
245 137
492 334
290 170
204 176
68 350
43 63
370 203
47 222
24 329
338 48
198 7
424 132
302 89
10 404
444 319
321 86
211 378
127 315
475 187
290 363
309 302
215 452
316 66
464 397
28 115
339 78
24 304
18 319
100 20
180 95
387 9
297 420
196 436
277 355
160 78
427 56
225 499
297 172
273 404
325 47
189 130
400 128
304 74
437 192
86 109
237 57
305 56
261 466
374 112
376 42
221 273
227 384
422 365
178 260
446 298
393 457
473 14
206 354
141 464
3 319
466 369
124 302
104 74
273 91
142 323
298 377
105 217
404 232
203 461
375 274
110 168
129 185
366 161
457 320
109 167
301 212
12 303
131 437
59 164
120 56
383 385
447 117
412 376
347 268
356 43
254 43
299 259
64 241
325 152
369 318
14 174
302 296
203 359
44 71
85 44
68 268
168 259
30 359
210 407
107 98
37 325
71 442
457 184
325 293
129 340
203 369
464 238
472 415
23 1
33 36
433 330
7 449
206 292
420 221
98 368
467 141
335 329
427 240
14 225
319 198
393 357
352 79
48 184
473 189
444 52
270 76
23 395
453 197
493 10
171 407
9 252
327 58
262 147
386 164
131 49
162 399
499 24
321 214
9 384
58 347
3 123
443 86
229 73
209 97
54 60
130 153
154 48
116 402
125 376
350 53
205 359
173 324
249 19
344 164
406 26
474 293
284 164
432 393
113 179
324 318
335 100
338 33
163 301
441 43
247 167
71 33
307 462
295 402
63 148
299 373
317 38
282 52
188 123
204 308
290 301
402 326
124 229
317 490
284 145
15 172
495 135
65 311
367 225
311 84
363 431
232 203
461 83
5 134
461 328
23 466
479 20
496 199
3 120
378 474
181 277
403 69
495 462
51 361
477 441
123 417
37 119
167 475
299 262
310 464
138 439
426 254
89 20
23 289
9 446
315 495
150 287
72 164
207 483
372 222
381 8
218 446
219 33
8 119
0 69
296 387
158 449
266 495
243 346
366 471
346 139
153 398
316 381
287 129
473 175
103 315
34 221
461 170
113 477
426 3
372 216
497 293
86 498
393 439
128 234
67 447
115 122
144 478
318 17
371 456
168 319
361 157
237 173
355 78
185 318
411 275
212 345
456 490
370 358
301 239
43 82
110 114
342 224
67 403
365 12
464 40
441 104
306 279
17 457
105 306
452 210
272 107
431 13
200 382
410 143
245 81
84 250
196 350
262 294
164 221
217 167
46 277
286 373
142 309
9 302
331 13
422 13
238 28
175 177
293 227
201 139
59 435
127 229
273 336
399 289
132 42
496 323
306 260
103 428
405 329
41 343
184 291
17 120
125 328
251 441
356 25
309 170
349 456
80 436
310 257
393 3
355 68
176 298
78 306
212 217
275 103
339 67
57 454
29 118
291 164
245 368
232 472
100 355
216 259
234 20
341 3
375 17
417 181
129 216
86 207
74 170
152 234
379 167
349 67
400 96
336 162
320 262
129 263
339 141
297 479
148 329
68 458
492 239
434 352
174 280
497 320
383 205
370 199
412 164
185 159
158 128
354 434
351 444
442 208
217 409