граф

Как се намира диаметър на неориентиран ацикличен свързан граф?

не съм 100% сигурен дали е най-доброто, което може да се направи, ама е вариант:
намираш най-кратките пътища от всеки връх до всеки, и избираш най-големия от тях.

Сигнатура!

100% ne e nai-dobroto :)
на мен пък първо ми хрумна да тръгна от крайните върхове,
и ако се срещнат някъде по пътя, се изоставя по-късият.
и така докато останат само два които се обединяват.

абе и на мен ми хрумна това, ама представи си, че графът е като дълъг +. И в един момент се срещат две от разклоненията, махаш по-късото, после махаш още едно от разклоненията (пак по-късото), ама накрая се оказва, че две от махнатите дават по-дълъг радиус...

Сигнатура!

t.e. dva nai-razdalecheni vyrha v dyrvo. Po princip moje da stane lesno s
DP (dynamic programming) - orientirash dyrvoto spriamo niakakyv nachalen
vryh s. Sled tova namirash nai-dylgiq pyt ot vseki vryh do list (tova
stava lineino s DP), tova primerno e dist[1..n]. Sled tova za vseki vryh w razglejdash naslednicite mu i izbirash tezi dva nalsednika u i v za koito
2 + dist[u] + dist[v] e maksimalno. Taka namirash diametyra. Tova neshto
ti e O(n).

Vsyshtnost tova stavashe i po dosta po-lesen nachin (za raziasniavane,
za programirane - s podobna slojnost). Beshe neshto ot roda na - namirash
nai-otdalecheniq vryh ot vryh s, sled tova nai-otdalecheniq vryh ot namereniq
vryh i tova ti e diametyra. Triabva da si go dokajesh che e taka de, zashtoto
ne sym siguren.

То хубаво като идея,обаче изобшо идея си нямам какво е това DP(dynamic programming)!Аз и от графи нищо несхващам!Просто не ги харесвам като структура и не са ми ясни!Обаче ми се налага да направя задачата понеже ми е за курсова работа!Без да искам да ставам нахална,ако някой може да ми помогне ще съм му много благодарна!

Ako ne shvashtash nishto napishi tova koeto kaza Questor - obhojdane v shirina/dylbochina ot vseki vryh, tova go ima vyv vsiaka kniga v koiato stava duma za algoritmi v/hu grafi.

Намерих всички мин.пътища м/у всички възможни вътхове(с алгоритъма на Флойд),но немога да намеря кой е най-дългия от тях!

namirash
nai-otdalecheniq vryh ot vryh s, sled tova nai-otdalecheniq vryh ot namereniq
vryh i tova ti e diametyra

ехе тва е ебаси якото

Сигнатура!

to minimalen pyt v dyrvo obshto vzeto e bezsmisleno poniatie, zashtoto
v dyrvo m/u dva vyrha ima edinstven pyt, no nz. T.e. floyd-a ti e nameril
dyljinite na pytishtata m/u vseki dva vyrha, koeto ti vyrshi idealna rabota - namirash dvoika i,j i!=j, takava che f[j] da e maksimalno (i razlichno
primerno ot infinity, koeto sigurno polzvash v impl na floyda).

След Флойд, обикаляш структурата, в която държиш разстоянията, взимаш най-голямото, и си готов. Само че Floyd ти дава O(n^3)...

Може, както Петко предложи, да разглеждаш графа като дърво, защото ацикличният свързан граф е именно дърво. Би могъл да избереш произволен връх за корен. От там вече, ако пуснеш едно обхождане в ширина, със сложност O(n) можеш да получиш разстоянията от всеки връх до корена. Намираш най-голямото такова (O(n)), но тук вече идва сложното - никой не ти гарантира, че намереният от теб връх е край на диаметъра, нито пък, че диаметърът минава точно през корена на дървото. Може би може да се работи в тази насока, но най-сигурно си е с Флойд.

Такова нешто правя и неще да работи!

void findiameter(void)
{unsigned i,j;int max,min;
max=MAX_VALUE;

for( i=0;i<N;i++){
min=A[0]+A[0];
for( j=0;j<N;j++)
if((i!=j)&&((A[j]+A[j])>min))min=(A[j]+A[j]);
if(min<max)min=max;
}
printf("Diamet1r1t na grafa e %u\n",max);
}

Ами нормално да не ще... Дори и само сложността му O(n^2) би трябвало да ти подскаже, че не е решението, което дискутирахме до сега (Флойд - O(n^3)). Да не говорим, че си надробил една невероятна каша в тези няколко реда Първо на първо при всяка итерация на външния цикъл присвояваш на min стойността на max, която е MAX_VALUE, а накрая дори си правиш труда да отпечаташ стойността на max, която преди това въобще не си и променял (след инициализацията и)...

Направи следното:
1. Измисли алгоритъм. Напиши го на лист стъпка по стъпка. Проиграй го няколко пъти върху измислени от теб прости данни, за да видиш, че работи и да си представиш как точно ще се държи.
2. Реализирай алгоритъма буквално, без да променяш нищо.
3. Пусни и се радвай

Както и да го правя неще да стане!Как да намеря най-големия елемент в матрицата на теглата сле изпълнение на акгоритъма на Флойд!Много ми е спешно!Ако някой знае ше съм благодарен да ми каже!Логически знам как трябва да стане,но програмния код не мога да го напиша!

Ами по принцип се прави по следния начин:

Правиш си променлива min, която инициализираш с някаква голяма стойност. След това завърташ два вложени цикъла по матрицата, така че да обходиш всичките и полета, и за някое поле, ако е по-малко от текущата стойност на променливата ти min, записваш стойността му в нея. Така накрая в min ще е най-малкият елемент.

Интересно ми е как въобще си написал Флойд (три вложени цикъла), щом не можеш да обходиш една матрица. Но всъщност, ако имаш предвид предния код, който беше пейстнал, това не беше никакъв Флойд...