Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++] Задача. Графы 
V
    Опции темы
feanaro
Дата 8.6.2007, 17:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 21.12.2006

Репутация: нет
Всего: нет



Народ, проблема с задачей..  smile 
Граф представляет собой авиарейсы. Найти такой город А, из которого можно добраться до всех остальных, сделав не более одной пересадки. 

Это сообщение отредактировал(а) feanaro - 8.6.2007, 20:54
PM MAIL   Вверх
JAPH
Дата 8.6.2007, 19:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 312
Регистрация: 8.1.2007
Где: Ленобласть

Репутация: 12
Всего: 23



Граф ориентированный? И, вообще, как он задан?


--------------------
Что непонятно - спрашиваем smile
PM MAIL ICQ   Вверх
feanaro
Дата 8.6.2007, 20:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 21.12.2006

Репутация: нет
Всего: нет



JAPH Нет, неориентированный. 
Вообще, реализовать алгоритм нужно, используя какие либо из уже данных. Ниже приведу (но их много))

Код

#include <values.h>
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
struct Item {
int D;
Item * Next;
  Item():D(-1),Next(0){}
  Item(int V): D(V),Next(0){}
};
//---------------------------------------------------------------------------
class Cont {
protected:
Item * _Head;
Item * _Tail;
public:
    Cont():_Head(0),_Tail(0){}
    bool Empty(void) {return _Head?false:true;}
    virtual void Push(int V) = 0;
    virtual int  Pop(void);
    ~Cont();
};
//---------------------------------------------------------------------------
class CStack: public Cont {
public:
    CStack():Cont(){}
    virtual void Push(int V);
};
//---------------------------------------------------------------------------
class CQueue: public Cont {
public:
    CQueue():Cont(){}
    virtual void Push(int V);
};
//---------------------------------------------------------------------------
class Matrix {
protected:
  double ** _m;
  int _Size;
  virtual  void   Init(double Value);
public:
                  Matrix(int Size);
                  Matrix(const Matrix & M);
           double operator () (int row, int col);
           int    Size(void) {return _Size;}
           void   Set(int row, int col, double Value);
  virtual  void   Print(void);
           void   PrintFloydPath(int From, int To);
           void   PrintFloydPaths();
                  ~Matrix();
};
//---------------------------------------------------------------------------
class Graph: public Matrix {
  virtual void    Init(double Value);
public:
                  Graph(int Size):Matrix(Size){Init(MAXDOUBLE);}
                  Graph(const Graph & G):Matrix(G){}
  virtual void    Random(double Density, double MaxWeight = 1);
  virtual void    Print(void);
  virtual void    AddEdge(int V0, int V1, double Weight = 1);
  virtual void    DeleteEdge(int V0, int V1);
  virtual  int    EdgeCount(void);
           int    VertexCount(void) {return _Size;}
  virtual Graph   ShortestPath(int From, int To);
          void    Visit(int From, Cont & C);
          void    FindMinEdge(int & V0, int & V1);
          Graph   Floyd(Matrix & M);
          Graph   Kruskal(void);
          int     Hamiltonian(int v, int w, int Length, bool * Labelled, Graph & G);
          Graph   HamiltonianPath(int From, int To);
};
//---------------------------------------------------------------------------
class SGraph: public Graph {
public:
                  SGraph(int Size):Graph(Size){}
                  SGraph(const SGraph & G): Graph(G){}
  virtual void    Random(double Density, double MaxWeight = 1);
  virtual  int    EdgeCount(void) {return Graph::EdgeCount()/2;};
  virtual void    AddEdge(int V0, int V1, double Weight = 1);
};
//---------------------------------------------------------------------------
class WGraph: public Graph {
public:
                  WGraph(int Size):Graph(Size){}
                  WGraph(const WGraph & G): Graph(G){}
  virtual  int    EdgeCount(void) {return Graph::EdgeCount()/2;};
  virtual void    AddEdge(int V0, int V1, double Weight = 1);
};
//---------------------------------------------------------------------------
class OrGraph: public Graph {
public:
                  OrGraph(int Size):Graph(Size){}
                  OrGraph(const OrGraph & G): Graph(G){}
  virtual void    Random(double Density, double MaxWeight = 1);
  virtual void    AddEdge(int V0, int V1, double Weight = 1);
          OrGraph TransClosure(bool PathOrder);

};
//---------------------------------------------------------------------------
class OrWGraph: public Graph {
public:
                  OrWGraph(int Size):Graph(Size){}
                  OrWGraph(const OrWGraph & G): Graph(G){}
  virtual void    Random(double Density, double MaxWeight = 1);
};
//---------------------------------------------------------------------------
struct Deikstra {
bool   Label;
double Path;
int    Vertex;
  Deikstra():Label(false),Path(MAXDOUBLE),Vertex(-1){}
};
//---------------------------------------------------------------------------
int Cont::Pop(void)
{
if(_Head)
  {
  Item * I = _Head;
  _Head = _Head->Next;
  int V = I->D;
  delete I;
  if (!_Head) _Tail = 0;
  return V;
  }
return -1;
}
//---------------------------------------------------------------------------
    Cont::~Cont()
{
while(_Head)
  {
  Item * I = _Head->Next;
  delete _Head;
  _Head = I;
  }
}
//---------------------------------------------------------------------------
void CStack::Push(int V)
{
if(_Head)
  {
  Item * I = new Item(V);
  I->Next = _Head;
  _Head = I;
  }
else
  _Tail = _Head = new Item(V);
}
//---------------------------------------------------------------------------
void CQueue::Push(int V)
{
if(_Head)
  {
  _Tail->Next = new Item(V);
  _Tail = _Tail->Next;
  }
else
  _Tail = _Head = new Item(V);
}
//---------------------------------------------------------------------------
       Matrix::Matrix(int Size):_Size(0),_m(0)
{
if(Size > 0)
  {
  _Size = Size;
  _m = new double*[_Size];
  for(int i = 0; i < _Size; i++)
    _m[i] = new double [_Size];
  Init(0);
  }
}
//---------------------------------------------------------------------------
       Matrix::Matrix(const Matrix & M)
{
if (&M != this)
  {
  _Size = 0;
  _m = 0;
  if(M._Size > 0)
    {
    _Size = M._Size;
    _m = new double*[_Size];
    for(int i = 0; i < _Size; i++)
      _m[i] = new double [_Size];
    }
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    _m[i][j] = M._m[i][j];
  }
}
//---------------------------------------------------------------------------
void   Matrix::Init(double Value)
{
for(int i = 0; i < _Size; i++)
for(int j = 0; j < _Size; j++)
  _m[i][j] = Value;
}
//---------------------------------------------------------------------------
double Matrix::operator () (int row, int col)
{
if(row < _Size && col < _Size && row >= 0 && col >= 0)
  return _m[row][col];
return MAXDOUBLE;
}
//---------------------------------------------------------------------------
void   Matrix::Set(int row, int col, double Value)
{
if(row < _Size && col < _Size && row >= 0 && col >= 0)
  _m[row][col] = Value;
}
//---------------------------------------------------------------------------
void   Matrix::Print(void)
{
for(int i = 0; i < _Size; i++)
  {
  for(int j = 0; j < _Size; j++)
    printf("%10.2lf",_m[i][j]);
  printf("\n");
  }
}
//---------------------------------------------------------------------------
void   Matrix::PrintFloydPath(int From, int To)
{
if (From != To)
  {
  printf("Path from %d to %d :  ",From,To);
  int v = From;
  printf("%d ",v);
  do
    {
    v = _m[v][To];
    if (v == -1)
      {
      printf("--> |x|");
      break;
      }
    printf("--> %d ",v);
    }
  while(v != To);
  printf("\n");
  }
}
//---------------------------------------------------------------------------
void   Matrix::PrintFloydPaths()
{
for (int v = 0; v < _Size; v++)
  for (int w = 0; w < _Size; w++)
     PrintFloydPath(v,w);
printf("\n");
}
//---------------------------------------------------------------------------
       Matrix::~Matrix()
{
for(int i = 0; i < _Size; i++)
  delete [] _m[i];
delete [] _m;
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void   Graph::Init(double Value)
{
for(int i = 0; i < _Size; i++)
for(int j = 0; j < _Size; j++)
  if(i != j) _m[i][j] = Value;
}
//---------------------------------------------------------------------------
void    Graph::AddEdge(int V0, int V1, double Weight)
{
if(V0 >= 0 && V1 >= 0 && V0 < _Size && V1 < _Size && V0 != V1 && Weight >= 0)
  {
  _m[V0][V1] = Weight;
  }
}
//---------------------------------------------------------------------------
void    Graph::DeleteEdge(int V0, int V1)
{
if(V0 >= 0 && V1 >= 0 && V0 < _Size && V1 < _Size && V0 != V1)
  {
  _m[V0][V1] = MAXDOUBLE;
  }
}
//---------------------------------------------------------------------------
void   Graph::Random(double Density, double MaxWeight)
{
if (Density >= 0 && Density <= 1 && MaxWeight >= 0)
  {
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    if(i > j)
      {
      if(Density >= (double)rand()/RAND_MAX)
        _m[i][j] = MaxWeight*rand()/RAND_MAX;
      else
        _m[i][j] = MAXDOUBLE;
      _m[j][i] = _m[i][j];
      }
    else
      continue;
  }
}
//---------------------------------------------------------------------------
void   Graph::Print(void)
{
for(int i = 0; i < _Size; i++)
  {
  for(int j = 0; j < _Size; j++)
    if(_m[i][j] < MAXDOUBLE)
      printf("%7.1lf",_m[i][j]);
    else
      printf("     oo");
  printf("\n");
  }
printf("\n");
}
//---------------------------------------------------------------------------
Graph Graph::ShortestPath(int From, int To)
{
if (From >= 0 && From < _Size && To < _Size && To >= 0)
  {
  if(From == To) return Graph(0);
  Deikstra * D = new Deikstra[_Size];
  D[From].Path   = 0;
  D[From].Vertex = -1;
  int U, V = From;
  double SPath;
  do
    {
    D[V].Label = true;
    for(U = 0; U < _Size; U++)
      {
      if(D[U].Label || _m[V][U] == MAXDOUBLE) continue;
      if(D[U].Path > D[V].Path + _m[V][U])
        {
        D[U].Path   = D[V].Path + _m[V][U];
        D[U].Vertex = V;
        }
      }
    SPath = MAXDOUBLE;
    V = -1;
    for(U = 0; U < _Size; U++)
      if(!(D[U].Label) && D[U].Path < SPath)
         {
         SPath = D[U].Path;
         V = U;
         }
    }
  while(V != -1 && V != To);
  Graph G(_Size);
  V = To;
  while(D[V].Vertex != -1)
    {
    G.AddEdge(V,D[V].Vertex,_m[V][D[V].Vertex]);
    V = D[V].Vertex;
    }
  delete [] D;
  return G;
  }
return Graph(0);
}
//---------------------------------------------------------------------------
int    Graph::EdgeCount(void)
{
if(_Size)
  {
  int Count = 0;
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    {
    if(i == j) continue;
    if(_m[i][j] < MAXDOUBLE) Count++;
    }
  return Count;
  }
return 0;
}
//---------------------------------------------------------------------------
Graph   Graph::Floyd(Matrix & M)
{
Graph G(*this);
if(M.Size() == _Size)
  {
  for(int i = 0; i < _Size; i++)
    for(int s = 0; s < _Size; s++)
      M.Set(i, s, G._m[i][s] == MAXDOUBLE ? -1 : s);
  for(int i = 0; i < _Size; i++)
    for(int s = 0; s < _Size; s++)
      if (G._m[s][i] < MAXDOUBLE)
        for(int t = 0; t < _Size; t++)
          if (G._m[i][t] < MAXDOUBLE)
            if(G._m[s][t] > G._m[s][i] + G._m[i][t])
               {
               G._m[s][t] = G._m[s][i] + G._m[i][t];
               M.Set(s, t, M(s, i));
               }
  }
return G;
}
//---------------------------------------------------------------------------
void    Graph::FindMinEdge(int & V0, int & V1)
{
double MinWeight = MAXDOUBLE;
V0 = V1 = -1;
for(int i = 0; i < _Size; i++)
  for(int s = 0; s < _Size; s++)
    {
    if (i == s)  continue;
    if (_m[i][s] < MAXDOUBLE)
      {
      MinWeight = _m[i][s];
      V0        = i;
      V1        = s;
      }
    }
if (MinWeight == MAXDOUBLE)
  V0 = V1 = -1;
}
//---------------------------------------------------------------------------
Graph   Graph::Kruskal(void)
{
Graph MST(_Size);
Graph G(*this);
bool * Labelled = new bool[_Size];
for(int i = 0; i < _Size; i++) Labelled[i] = false;
int V0 = -1, V1 = -1;
while (MST.EdgeCount() < (_Size - 1)*2)
  {
  G.FindMinEdge(V0,V1);
  if(V0 == -1 && V1 == -1)
    break;
  if(!Labelled[V0] || !Labelled[V1])
    {
    MST.AddEdge(V0,V1,_m[V0][V1]);
    MST.AddEdge(V1,V0,_m[V0][V1]);
    Labelled[V0] = true;
    Labelled[V1] = true;
    }
  G.DeleteEdge(V0,V1);
  G.DeleteEdge(V1,V0);
  }
delete [] Labelled;
return MST;
}
//---------------------------------------------------------------------------
void    Graph::Visit(int From, Cont & C)
{
if (From >= 0 && From < _Size)
  {
  int V = From;
  bool * Labelled = new bool[_Size];
  for(int i = 0; i < _Size; i++)
    Labelled[i] = false;
  C.Push(V);
  Labelled[V] = true;
  do
    {
    V = C.Pop();
    printf("%d ", V);
    for(int U = 0; U < _Size; U++)
      {
      if(!Labelled[U] && _m[V][U] != MAXDOUBLE)
        {
        C.Push(U);
        Labelled[U] = true;
        }
      }
    }
  while(!C.Empty());
  delete [] Labelled;
  printf("\n");
  }
}
//---------------------------------------------------------------------------
int  Graph::Hamiltonian(int v, int w, int Length, bool * Labelled, Graph & G)
{
if (v == w)
  return Length == 0 ? 1 : 0;
Labelled[v] = true;
for (int t = 0; t < _Size; t++)
  if( _m[v][t] < MAXDOUBLE && _m[v][t] != 0 && !Labelled[t])
    if ( Hamiltonian(t, w, Length - 1, Labelled, G))
      {
      G.AddEdge(t,v,_m[t][v]);
      G.AddEdge(v,t,_m[v][t]);
      return 1;
      }
Labelled[v] = false;
return 0;
}
//---------------------------------------------------------------------------
Graph   Graph::HamiltonianPath(int From, int To)
{
bool * Labelled = new bool[_Size];
for (int i = 0; i < _Size; i++) Labelled[i] = false;
Graph G(_Size);
int f = Hamiltonian(From,To, _Size - 1 ,Labelled, G);
delete [] Labelled;
return G;
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void    SGraph::AddEdge(int V0, int V1, double Weight)
{
Graph::AddEdge(V0,V1,1);
Graph::AddEdge(V1,V0,1);
}
//---------------------------------------------------------------------------
void   SGraph::Random(double Density, double MaxWeight)
{
if (Density >= 0 && Density <= 1 && MaxWeight >= 0)
  {
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    if(i > j)
      {
      if(Density >= (double)rand()/RAND_MAX)
        _m[i][j] = 1.0;
      else
        _m[i][j] = MAXDOUBLE;
      _m[j][i] = _m[i][j];
      }
    else
      continue;
  }
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void    WGraph::AddEdge(int V0, int V1, double Weight)
{
Graph::AddEdge(V0,V1,Weight);
Graph::AddEdge(V1,V0,Weight);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void    OrGraph::AddEdge(int V0, int V1, double Weight)
{
Graph::AddEdge(V0,V1,1);
}
//---------------------------------------------------------------------------

OrGraph OrGraph::TransClosure(bool PathOrder)
{
OrGraph G(*this);
for(int i = 0; i < _Size; i++)
  for(int s = 0; s < _Size; s++)
     if (G._m[s][i] == 1)
       for(int t = 0; t < _Size; t++)
         G._m[s][t] = G._m[i][t] == 1 ? 1 : G._m[s][t];
if(!PathOrder)
  for(int i = 0; i < _Size; i++)
    G._m[i][i] = 0;
return G;
}
//---------------------------------------------------------------------------
void   OrGraph::Random(double Density, double MaxWeight)
{
if (Density >= 0 && Density <= 1 && MaxWeight >= 0)
  {
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    {
    if(i == j) continue;
    if(Density >= (double)rand()/RAND_MAX)
      _m[i][j] = 1.0;
    else
      _m[i][j] = MAXDOUBLE;
    }
  }
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
void   OrWGraph::Random(double Density, double MaxWeight)
{
if (Density >= 0 && Density <= 1 && MaxWeight >= 0)
  {
  for(int i = 0; i < _Size; i++)
  for(int j = 0; j < _Size; j++)
    {
    if(i == j) continue;
    if(Density >= (double)rand()/RAND_MAX)
      _m[i][j] = MaxWeight*rand()/RAND_MAX;
    else
      _m[i][j] = MAXDOUBLE;
    }
  }
}


PM MAIL   Вверх
JAPH
Дата 8.6.2007, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 312
Регистрация: 8.1.2007
Где: Ленобласть

Репутация: 12
Всего: 23



Проверьте, вроде ничего.
Код
int Graph::FindCentralVertex() {
    for (int i = 0; i < _Size; ++i) { // Перебираем кандидатов.
        int j = 0; // Для каждой вершины,
        while (j < _Size) {
            if (i != j) { // кроме текущей, естественно,
                int pl = ShortestPath(i, j).EdgeCount(); // смотрим, насколько далёк путь к ней.
                if (pl == 0 || pl > 2) break; // Если его нет или он слишком длинный, сдаёмся.
            }
            ++j;
        }
        if (j == _Size) return i; // Если не сдались и вышли из цикла из-за !(j<_Size),
                                  //то мы нашли требуемую вершину. Все такие найти не просят => сразу возвращаем.
    }
    return -1; // Если ни один кандидат не подошёл, возвращаем признак неуспеха.
}
void main() {
    SGraph g(7); // Только здесь пользуюсь неориентированностью.
                 // Почему? Да просто все методы, нужные в FindCentralVertex(), есть в Graph. Ну, если что, переделаете :)
    g.AddEdge(6, 1);
    g.AddEdge(0, 1);
    g.AddEdge(6, 2);
    g.AddEdge(6, 3);
    g.AddEdge(4, 3);
    g.AddEdge(5, 3);
    g.Print();
    cout<<g.FindCentralVertex()<<"\n";
}



--------------------
Что непонятно - спрашиваем smile
PM MAIL ICQ   Вверх
feanaro
Дата 9.6.2007, 09:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 21.12.2006

Репутация: нет
Всего: нет



JAPH, спасибо огромное, вроде работает) 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.0683 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.