Новичок
Профиль
Группа: Участник
Сообщений: 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; } } }
|
|