Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Ада и другие языки _ графы
Автор: Квин 16.02.2007 22:20
Здравствуйте.
Прошу помочь с выполнением такой вот задачи на Си, комилятор visual C.
Дан файл в котором указаны пары вершин графов, связанных между собой
1. заполнить из этого файла двумерный массив ширины n на n, где n - это количество вершин, заполнить так, что если между вершинами есть связь, то в массив на соответствующем пересечении ставим 1, если нет, то ноль. Вот эот массив вывести.
2. построить дерево, по полученному дереву указать все возможные пути в этом графе.
По первому у меня что-то есть, а вот по второму вообще не знаю как и что делать. Очень прошу помочь.
Автор: Lapp 17.02.2007 9:55
По первому у меня что-то есть,
Вот и покажи, что есть.
Вторая часть не совсем ясна.. "Построить дерево" - значит вывести его? Два пути, один из которых включает второй - различны? Известно ли что-то заранее про граф? Могут ли в нем быть циклы?..
И последнее: Поиск и FAQ могут помочь..
Автор: Гость 18.02.2007 8:08
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "filework.h"
int *mkarray(int n)
{
int i,g;
int *mas;
mas=(int*)malloc(sizeof(int)*n*n);
for(i=0;i<n;i++)
{
for(g=0;g<n;g++)
{
mas[i*n+g]=0;
}
}
return mas;
};
int* readfile(int *n)
{
int s1, s2;
int *mas;
FILE *stream;
if( (stream = fopen( "c:/input.txt", "r" )) != NULL )
{
fscanf(stream,"%d",n);
mas=mkarray(*n);
while(!feof(stream))
{
fscanf(stream,"%d %d", &s1, &s2);
mas[s1* *n+s2]=1;
mas[s1+s2* *n]=1;
}
fclose(stream);
}
return mas;
};
_____________________________________
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include "filework.h"
int main()
{
int *p;
int i,g,n;
p=readfile(&n);
for(i=0;i<n;i++)
{
for(g=0;g<n;g++)
{
printf("%d ",p[i*n+g]);
}
printf("\n");
}
return 0;
}
вот что есть, и что мне позволили знания,а оставшуюсь вторую часть я совсем осилить не могу, а дело очень горит. помогите плиз...
На счёт вывести дерево, то я не знаю - если это необходимо для решения то наверное, а если нет то на выход вообще то только все пути какие в этом дереве есть. Про граф ничего не сказано, даже мне кажется граф тут употреблено длясловца, т.е. просто задаётся папарное соединение вершин дерева, по этому построить само дерево, а потом вывести все пути возможные в этом дереве - никаких условий специфичных характерных для гарфов, ничего такого нет.
Автор: Квин 19.02.2007 0:07
Друзья, ну очень прошу помочь, вот первая чатсь кое как есть, прошу помочь прикрутить к ней второую. Сам не осиливаю и всё...
Автор: мисс_граффити 19.02.2007 0:29
Насколько я помню дискретную математику, дерево - это частный случай графа (граф без циклов, с четко определенным соотношением числа ребер и вершин).
Что предполагается делать в случае, если предлагаемый граф не удовлетворяет условиям для дерева?
Автор: Гость 19.02.2007 1:01
а можн продолжить? ну т.е. выполнить конечную задачу в независимости от того удовлетворяет ли он условию дерева или нет?
Если да, то очень прошу помочь так сделать...в целом весь разговор о графах, не стоит сильно оглядываться на деревья....
Автор: мисс_граффити 19.02.2007 1:13
как можно построить дерево, если заданный граф не удовлетворяет условиям дерева?
деревья, кстати, разные бывают...
про построение графов почитай вот http://ric.uni-altai.ru/Fundamental/pascal3/lab3/lab3-index.htm
примеры, правда, на паскале, но теория полезная.
Автор: Гость 19.02.2007 2:08
теорию нам дали, я как раз реализовать не могу...если не соответствует, то можно ограничится просто соответствующим предупреждением, но мне ОЧЕНь нужно программа которая выполняла бы конечную задачу в случае если всё впорядке
Автор: мисс_граффити 19.02.2007 2:15
Ну так в чем проблема? Со списками работать умеешь?
Автор: Гость 19.02.2007 3:15
ну да вроди умею более или менее, но тем не менее как обойти и всё такео всё равно не соображаю....