Задание
Оценка за задание есть наибольшая из оценок за решённые задачи.
Задание должно быть выложено в репозиторий homework, который должен быть выложен на bitbucket. В противном случае, вне зависимости от задачи вы получаете не более 6 баллов.
Если вы хотите получить оценку выше 8 баллов, код должен быть чистым и читаемым (по существу я этого требовал и раньше). Т.е. все функции, переменные и классы имеют содержательные и понятные названия. Схема именования сущностей в одном типе сущностей однородна (т.е. либо везде сокращения, либо везде полные слова). Функции не бывают длиннее ~10 строк и не делают больше одного дела. Строки не бывают длиннее 75 символов (включая отступы). Внутри строк есть одна политика на тему того, как ставить пробелы. Части кода расположены стандартным образом: импорты -> константы и глобальные переменные -> определения (функций и классов) -> if __name__ == "__main__". Нет дублирования кода. Модуль, все функции и классы должны сопровождаться документацией. Там, где это возможно, функции должны сопровождаться примерами вызова, которые должны проходить doctest.
Я настоятельно рекомендую писать чистый код изначально (да, это значит, что иногда в очевидных, казалось бы, местах приходится на 10 минут задуматься над названием переменной), потому что так быстрее получить рабочую программу. Всё равно основное время уходит на отладку, а не на написание.
(6 баллов) Дан граф в виде словаря соседей (т.е. в словаре ключ – вершина, значение – списоск соседей) и одна из вершин в нём. Написать функцию для нахождения компоненты связности, содержащей эту вершину. Функция получает на вход граф и вершину и выдаёт список вершин.
(8 баллов) Дан граф в виде csv-файла (см. ниже). Напишите программу, которая найдёт в нём компоненту связности, включающую первую вершину, упомянутую в файле. Программа выводит на экран список её вершин в одну строку.
(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