|
Мне нужно написать программу на 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)
Помогите разобраться как это исправить что бы всё работало..
|
04.12.2009, 04:25 
