![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 20.02.2011
Сообщений: 9
|
![]()
помогите пожалуйста доделать программу. Нужно найти расстояние от произвольной вершины до всех остальных. Алгоритм реализован поиском в ширину.
входной файл: 33 12 23 12 Код HTML:
#include <iostream.h> #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <fstream.h> int i,j,k,p,cur; int start,n,m; main() { FILE *vvod; int *Label; //объявляет массив меток int *FIFO; //объявляет структуру данных "очередь" int **Graf;/объявляет матрицу смежности графа //----------------------------------------------- if((vvod=fopen("C:\\input.txt","r"))==NULL) //чтение файла { puts("ne nauden fail! "); return NULL; } fscanf(vvod,"%d%d",&n,&m);//читает количество вершин и количество ребер fscanf(vvod,"\n"); printf("Vvedite startovyu vershiny. Ot 0 do %d. ",n-1); scanf("%d",&start); Label=new int [n]; //память для массива меток n FIFO= new int [n];//память для очереди, состоящей из n элементов Graf=new int *[n]; //память для матрицы n*n for (i=0; i<n; i++) Graf[i]=new int [n]; for(k=0;k<m;k++) //представление графа в виде матрицы смежности { fscanf(vvod,"%d%d",&i,&j);//читает номера смежных вершин Graf[i][j]=1; //соединены ребром fscanf(vvod,"\n"); } for(i=0; i<m; i++) { FIFO[i]=0; Label[i]=32767; } p=0; //указатель на начало очереди k=1;//указатель на конец очереди FIFO[p]=start; //заносит стартовую вершину очереди Label[start]=0; //и помещает её меткой 0 while(p!=k) { cur=FIFO[p];//выделяет очередную вершину из очереди p++;//сдвигает указатель начала на единицу for(i=0;i<n;i++) if(Graf[cur][i]==1 && Label[i]>Label[cur]+1) { FIFO[k]=i; //заносит вершину в очередь k++; //сдвигает указатель конца очереди Label[i]=Label[cur]+1;//помечает вершину } } for (i=0;i<n;i++) cout<<Label[i]<<" ";//выводит результат (не выводит :D) fclose(vvod); getch(); return 0; } |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
графы поиск в ширину | KaMish_44 | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 30.04.2011 05:31 |
поиск в ширину | ooooch | Помощь студентам | 1 | 29.11.2009 11:26 |
поиск в ширину на с++ | Pavel.d | Помощь студентам | 1 | 19.04.2009 12:08 |
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) | Serega123 | Помощь студентам | 3 | 30.10.2008 22:26 |