2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 C++диаметр графа
Сообщение04.12.2009, 04:25 


30/03/09
41
Мне нужно написать программу на c++ нахождение диаметра графа
в интернете я нашла такую программу но она у мя не работат


Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число ребер, которые необходимо пройти, чтобы добраться из одной вершины в другую. Для решения этой задачи можно использовать алгоритм Дейкстры, что и показано ниже. Я рассматриваю не ориентированный, не взвешенный граф. Входными данными служат количество вершин и множество ребер.

вот сама программа
Реализация на C++:
main.cpp
#include <stdlib.h>
#include <stdio.h>
#define MAX 51
struct contact {contact *next; int first,second,wt;};
#include "graf.h"

int main()
{
FILE *fp;
int n,i,j,a=0,b=0,dia=1;
contact *head,*p;
FILE *fp2=fopen("exit.txt","w+");
if(fp=fopen("graf.txt","r"))
{
//Ввод количества вершин графа;
fscanf(fp,"wt: %d\n",&n);
int **graf=new int *[n];
for(i=0;i<n;i++)
graf[i]=new int[n];

//Построение матрицы расстояний;
if(a_matrix(fp,n,graf))
{
//Проверга графа на связность;
if(e_link(n,graf))
{
//Построение списка всех возможных маршрутов;
v_list(&head,n,graf);
int *graf_b=new int[n];
p=head;
while(p->next!=NULL)
{
if(p->wt==-1&&b!=p->first)
{
a=p->first;
b=p->first;
//Отыскание длинн маршрутов от вершины a;
dijkstra(n,graf,a,graf_b);
//Поиск максимального расстояния;
maxway(n,graf_b,&dia);
}
p=p->next;
}
fprintf(fp2,"Диаметр графа = %d",dia);
}
else fprintf(fp2,"Ошибка: граф не связен");
}
else fprintf(fp2,"Ошибка: граф пуст;");
fclose(fp);
}
else fprintf(fp,"Ошибка: не могу прочитать входные данные;");
fclose(fp2);
}

graf.h
int a_matrix(FILE *fp, int n, int **graf)
{
int res=0,i,j,first,second;
if(n>1)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)
graf[i][j]=0;
else
graf[i][j]=2;

while(fscanf(fp,"%d-%d",&first,&second)!=EOF)
{
graf[first-1][second-1]=1;
graf[second-1][first-1]=1;
}
res=1;
}
return res;
}

int e_link(int n, int **graf)
{
int i,res=1;
for(i=0;i<n&&(i+1)!=n-1&&res!=0;i++)
if(graf[i][i+1]!=1)
res=0;
return res;
}

void v_list(contact **head, int n, int **graf)
{
contact *p;
int i,j;
*head=new contact;
p=*head;
for(i=1;i<n+1;i++)
for(j=i;j<n+1;j++)
if(i!=j)
{
p->next=new contact;
p->first=i;
p->second=j;
if(graf[i-1][j-1]==1)
p->wt=1;
else
p->wt=-1;
p=p->next;
}
p->next=NULL;
}

void dijkstra(int n, int **graf, int a, int *graf_b)
{

int *graf_a=new int[n],i,j,flag;
for(i=0;i<n;i++)
{
graf_a[i]=0;
graf_b[i]=MAX;
}
graf_b[a-1]=0;
flag=0;
while(flag!=1)
{
graf_a[a-1]=1;
for(i=0;i<n;i++)
//if(graf_a[i]==0&&graf[i][a-1]==1)
if(graf[i][a-1]==1&&graf_b[a-1]<graf_b[i])
graf_b[i]=graf_b[a-1]+1;

for(i=0;i<n;i++)
if(graf[i][a-1]==1&&graf_a[i]==0)
{
a=i+1;
break;
}
if(i==n) a++;
for(i=0;i<n&&graf_a[i]==1;i++);
if(i==n) flag=1;
}
}

void maxway(int n, int *graf_b, int *dia)
{
int i,j;
for(i=0;i<n;i++)
if(graf_b[i]>*dia)
*dia=graf_b[i];
}

Структура входного файла graf.txt
< Граф >::=< количество вершин >| пробел |< множество ребер >
< Количество вершин >::=натуральное число
< Множество ребер >::=< вершина >| '–' |< вершина

у мя vs выдает
1) warning C4996: 'fscanf': This function or variable may be unsafe. Consider using fscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
see declaration of 'fscanf'
2) warning C4101: 'j' : unreferenced local variable
warning C4101: 'j' : unreferenced local variable
3) warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
see declaration of 'fopen'
4) warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
see declaration of 'fopen'
5) warning C4996: 'fscanf': This function or variable may be unsafe. Consider using fscanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
see declaration of 'fscanf'
6)warning C4101: 'j' : unreferenced local variable

0 error(s), 7 warning(s)

Помогите разобраться как это исправить что бы всё работало..

 Профиль  
                  
 
 Re: C++диаметр графа
Сообщение04.12.2009, 11:56 


06/04/09
156
Воронеж
Используйте тег код.

warning C4996 - компилятор от мелкомягких предупреждает, что функция может быть небезопасной. Вариант избавления написан в сообщении или МСДН.

warning C4101 - переменная объявлена, но не используется.

Вы читаете, что вам пишет компилятор?

 Профиль  
                  
 
 Re: C++диаметр графа
Сообщение04.12.2009, 19:33 
Заслуженный участник


15/05/05
3445
USA
Negodiaika в сообщении #267870 писал(а):
... 0 error(s), 7 warning(s)
Помогите разобраться как это исправить что бы всё работало..

Эти типы предупреждений можно на данном этапе игнорировать. Они не помешают скомпилировать и запустить программу.
Объясните, что значит "не работает": Выдает неверный результат? Зависает? Выдает сообщение "Пошли вы все на фиг"?

 Профиль  
                  
 
 Re: C++диаметр графа
Сообщение06.12.2009, 02:27 
Заслуженный участник


26/07/09
1559
Алматы
2Negodiaika
Кажется, у вас все работает как надо, а ту чепуху с warning'ами можете, как вам уже порекомендовали, просто проигнорировать. :)

 Профиль  
                  
 
 Re: C++диаметр графа
Сообщение21.12.2009, 15:42 


30/03/09
41
я знаю что на warning всё равно,но у мя не идёт по другой причине
у меня появляется окошко и в нем ошибка же когда сама программа запускается,но вот сейчас даже того нет,так как у меня вот это

1>LINK : fatal error LNK1000: Internal error during IncrBuildImage

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group