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

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

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

Восстановить пароль
Повторная активизация e-mail

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

Ответ
 
Опции темы Поиск в этой теме
Старый 08.06.2023, 21:42   #1
Кристина221
Новичок
Джуниор
 
Регистрация: 08.06.2023
Сообщений: 1
По умолчанию Графы, поиск всех путей, DFS

Привет, может кто помочь разобраться? Два дня пытаюсь понять и все никак
Дано: орентированый граф, с вершинами от 1 до n. (n>=2) и только такие ребра (u,v), что u<v.
Нужно : 1) считать граф с текстового файла, заданного как ниже.
12
1: 2 3 4 5
2: 8
3: 7 9
4: 6 11
5: 8
6: 9 10
7: 10 11
8: 12
9: 10 12
10: 12
11: 12
12:
2) Посчитать, сколько разных путей ведет с вершины 1 до вершины n, но так что бы начало и конец этих путей были разные( всм ребер)
Пример ( для графа который выше): ответ 3
1 - 2 - 8 - 12, 1 - 3 - 9 - 10 - 12, 1 - 4 - 6 - 9 - 12.
без 1 - 5 - 8 - 12, так как последнее ребро совпадает с тем что вышею

Внизу код, который использовала.

Не понимаю, как вчитать граф вида что и выше, получается только когда задан в файле в виде
12
1:2
1:3 и тд., но в задачи нужно конкренто то что выше.
#include <stdlib.h>
#include <stdio.h>
#include<stdbool.h>

struct element;
typedef struct element element, *list;


struct element {
int info;
element *next;
};


void ini(list* h) {
*h = NULL;
}


element * nowy(int a) {
element* u;
u = malloc(sizeof(element));
if (u == NULL) exit(1);
u->next = NULL;
u->info = a;
return u;
}

void dodaj(list* h, element* u) {
u->next = *h;
*h = u;
}


void usun(list* h) {
element *u;
if (*h != NULL) {
u = *h;
*h = (*h)->next;
free(u);
}
}


void oproznij(list* h) {
while (*h != NULL)
usun(h);
}

list szukaj(list h, int a) {
while (h != NULL && h->info != a)
h = h->next;
return h;
}


int rozmiar(list h) {
int wynik = 0;
while (h != NULL) {
++wynik;
h = h->next;
}
return wynik;
}


void druk(list h) {
while (h != NULL) {
printf("%d ", h->info);
h = h->next;
}
printf("\n");
}
void dfs_visit(
list G[], int N, int u, int* time, int d[], int f[], int P[], int K[]
) {
list l = G[u];
K[u] = 2;
d[u] = ++(*time);
while (l != NULL) {
if (K[l->info] == 1) {
P[l->info] = u;
dfs_visit(G, N, l->info, time, d, f, P, K);

}
l = l->next;
}
f[u] = ++(*time);
K[u] = 0;
}


void druk_graf(list *graf, int l_w);




int main(void) {


int N;


FILE *f;
f = fopen("graf.txt", "r");
fscanf(f, "%d", &N);
list G[N];
for (int k = 1; k < N+1; ++k)
ini(&G[k]); // работает

list el;
int s,p;
while (fscanf(f, "%d:%d", &p, &s) != EOF) {
//printf("%d %d\n", p, s);
el = nowy(s);
el->next = G[p];
G[p] = el;
} //считавает начало, дальше не понимаю что

druk_graf(G, N);


for (int k = 0; k < N; ++k)
oproznij(&G[k]);
return 0;
}



void druk_graf(list* graf, int l_w) {
int k;
printf(" Количество вершин: %d\n", l_w);
for (k = 1; k < l_w + 1; ++k) {
printf("%d: ", k);
druk(graf[k]);
}
}
Кристина221 вне форума Ответить с цитированием
Ответ


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

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин Daniia Паскаль, Turbo Pascal, PascalABC.NET 0 19.03.2019 19:27
Полный перебор всех возможных путей в графе Александррррррр Помощь студентам 1 13.01.2014 07:22
Поиск всех путей между двумя вершинами ориент. графа(Язык С) dasterse Помощь студентам 0 13.05.2012 17:18
Поиск всех путей в лабиринте от точки до точки pavel_abelardo Помощь студентам 12 26.06.2011 00:23