Помощь - Поиск - Пользователи - Календарь
Полная версия: графы
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Квин
Здравствуйте.
Прошу помочь с выполнением такой вот задачи на Си, комилятор visual C.
Дан файл в котором указаны пары вершин графов, связанных между собой
1. заполнить из этого файла двумерный массив ширины n на n, где n - это количество вершин, заполнить так, что если между вершинами есть связь, то в массив на соответствующем пересечении ставим 1, если нет, то ноль. Вот эот массив вывести.

2. построить дерево, по полученному дереву указать все возможные пути в этом графе.

По первому у меня что-то есть, а вот по второму вообще не знаю как и что делать. Очень прошу помочь.



Lapp
Цитата(Квин @ 16.02.2007 18:20) *

По первому у меня что-то есть,

Вот и покажи, что есть.
Вторая часть не совсем ясна.. "Построить дерево" - значит вывести его? Два пути, один из которых включает второй - различны? Известно ли что-то заранее про граф? Могут ли в нем быть циклы?..
И последнее: Поиск и FAQ могут помочь..
Гость
Код

#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;
}



вот что есть, и что мне позволили знания,а оставшуюсь вторую часть я совсем осилить не могу, а дело очень горит. помогите плиз...
На счёт вывести дерево, то я не знаю - если это необходимо для решения то наверное, а если нет то на выход вообще то только все пути какие в этом дереве есть. Про граф ничего не сказано, даже мне кажется граф тут употреблено длясловца, т.е. просто задаётся папарное соединение вершин дерева, по этому построить само дерево, а потом вывести все пути возможные в этом дереве - никаких условий специфичных характерных для гарфов, ничего такого нет.
Квин
Друзья, ну очень прошу помочь, вот первая чатсь кое как есть, прошу помочь прикрутить к ней второую. Сам не осиливаю и всё...
мисс_граффити
Насколько я помню дискретную математику, дерево - это частный случай графа (граф без циклов, с четко определенным соотношением числа ребер и вершин).
Что предполагается делать в случае, если предлагаемый граф не удовлетворяет условиям для дерева?
Гость
а можн продолжить? ну т.е. выполнить конечную задачу в независимости от того удовлетворяет ли он условию дерева или нет?
Если да, то очень прошу помочь так сделать...в целом весь разговор о графах, не стоит сильно оглядываться на деревья....
мисс_граффити
Цитата
т.е. выполнить конечную задачу в независимости от того удовлетворяет ли он условию дерева или нет?

как можно построить дерево, если заданный граф не удовлетворяет условиям дерева?
деревья, кстати, разные бывают...

про построение графов почитай вот здесь
примеры, правда, на паскале, но теория полезная.
Гость
теорию нам дали, я как раз реализовать не могу...если не соответствует, то можно ограничится просто соответствующим предупреждением, но мне ОЧЕНь нужно программа которая выполняла бы конечную задачу в случае если всё впорядке
мисс_граффити
Ну так в чем проблема? Со списками работать умеешь?
Гость
ну да вроди умею более или менее, но тем не менее как обойти и всё такео всё равно не соображаю....
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.