Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.12.2011, 13:23   #1
Даsha
 
Регистрация: 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;
}
Даsha вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
графы поиск в ширину 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