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

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

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 30.11.2007, 22:59   #1
Шушелла
Пользователь
 
Регистрация: 24.10.2007
Сообщений: 15
По умолчанию ГРРафы

подскажите,пожалуйста, какой-нибудь алгоритм для нахождения диаметра данного графа, используя матрицу смежностей.или может исходничок у кого-нибудь есть)?никак не соображу.сенкс)
Шушелла вне форума Ответить с цитированием
Старый 01.12.2007, 16:39   #2
Alek86
Форумчанин
 
Регистрация: 25.09.2007
Сообщений: 189
По умолчанию

www.boost.org
там есть огромная библиотека графов
Alek86 вне форума Ответить с цитированием
Старый 01.12.2007, 17:17   #3
Шушелла
Пользователь
 
Регистрация: 24.10.2007
Сообщений: 15
По умолчанию

Alek86.я там потерялась и не нашла что нужно)
Есть предположение использовать алгоритм Дейкстры для поиска мин путей и взять макс из мин.
?..
Шушелла вне форума Ответить с цитированием
Старый 01.12.2007, 19:53   #4
Alek86
Форумчанин
 
Регистрация: 25.09.2007
Сообщений: 189
По умолчанию

я в графах не разюираюсь.
сказал, что знал
Alek86 вне форума Ответить с цитированием
Старый 01.12.2007, 22:13   #5
Шушелла
Пользователь
 
Регистрация: 24.10.2007
Сообщений: 15
По умолчанию

Alek86,пасиб)
вот мой переделанный алгоритм Дейкстры под максимальную длину для путей.но че-то не работает-может кто-нить увидит ошибки..)пусть комменты не смущают-они остались с поиска кратчайших путей)

Код:
#include <stdio.h>
//#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused

#define VERTEXES 6	//Число вершин в графе

int v;
int main(int argc, char* argv[])
{
//   clrscr();
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;				// Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
     	                        0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };

   // Будем искать путь из вершины s в вершину g
   int s;              		// Номер исходной вершины
   int g;              		// Номер конечной вершины
   printf("Enter s: ");  	// Номер может изменяться от 0 до p-1
   scanf("%i",&s);
   printf("Enter g: ");
	scanf("%i",&g);
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
   		         // на кратчайшем пути

   // Инициализируем начальные значения массивов
   int u;		    // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; 
	//равны бесконечности
      x[u]=0;        
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // 
   x[s]=1; // 
   v=s;    // Делаем s текущей вершиной
   
   while(1)
   {
     
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]<t[v]+a[v][u]) //Если для вершины u еще не 
	
            	// и новый путь в u короче чем 
	//старый, то
         {
            t[u]=t[v]+a[v][u];	
            h[u]=v;	
	//пути из s->u
         }
      }

      // Ищем из всех длин некратчайших путей самый длинный
      int w=-infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                      
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]>w) 
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
		  printf("No way from %s  to %g.",s,g);
        // cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) 
      {        // выводим его
		printf("Min way from %i to %i.",s,g);
        // cout<<" путь из вершины "<<s<<" в вершину "<<g<<":";
   	   u=g;
   	   while(u!=s)
         {
            printf(" %i",u);
            u=h[u];
         }
			printf(" %i Way's length - %i",s,t[g]);
         //cout<<" "<<s<<". Длина пути - "<<t[g];
   	   break;
      }
      x[v]=1;
   }
   getch();
}

Последний раз редактировалось Carbon; 02.12.2007 в 18:09. Причина: code blocks
Шушелла вне форума Ответить с цитированием
Старый 08.12.2007, 14:01   #6
MaTBeu
Eclipse Foundation
Старожил
 
Аватар для MaTBeu
 
Регистрация: 19.09.2007
Сообщений: 2,619
По умолчанию

Глянь тут http://sources.codenet.ru/?cid=12 тут есть лаба по алгоритму Дейкстры. Там же поищи и нахождение диаметра графа... я видел... просто не помню именно в каком разделе.
MaTBeu вне форума Ответить с цитированием
Ответ


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

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

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