도움이될까한다 stl 로 복잡한문법좀죽여놔서 그나바보기편할듯
#include <iostream>
#include "graph.h"
using namespace std;
void main(void)
{
GraphFactory fac;
Dijkstra* g = new Dijkstra();
Graphs* result;
Vertex* a = fac.MakeVertex('a');
Vertex* b = fac.MakeVertex('b');
Vertex* c = fac.MakeVertex('c');
Vertex* d = fac.MakeVertex('d');
Vertex* e = fac.MakeVertex('e');
Vertex* f = fac.MakeVertex('f');
Vertex* G = fac.MakeVertex('g');
Vertex* h = fac.MakeVertex('h');
Vertex* i = fac.MakeVertex('i');
a->Add_Edge(fac.MakeEdge(a, e, 247));
b->Add_Edge(fac.MakeEdge(b, a, 35));
b->Add_Edge(fac.MakeEdge(b, c, 126));
b->Add_Edge(fac.MakeEdge(b, f, 150));
c->Add_Edge(fac.MakeEdge(c, d, 117));
c->Add_Edge(fac.MakeEdge(c, f, 162));
c->Add_Edge(fac.MakeEdge(c, G, 220));
e->Add_Edge(fac.MakeEdge(e, h, 98));
f->Add_Edge(fac.MakeEdge(f, e, 82));
f->Add_Edge(fac.MakeEdge(f, G, 154));
f->Add_Edge(fac.MakeEdge(f, h, 120));
G->Add_Edge(fac.MakeEdge(G, i, 106));
g->Add_Vertex(a);
g->Add_Vertex(b);
g->Add_Vertex(c);
g->Add_Vertex(d);
g->Add_Vertex(e);
g->Add_Vertex(f);
g->Add_Vertex(G);
g->Add_Vertex(h);
g->Add_Vertex(i);
result = g->Make_Way(b);
result->TestPrint();
}
//////////////////////////////////////////// graph.h ////////////////////////////////////// 파일분할하기귀찮아서 하나에다쳐박음
#include <list>
#include <stack>
#include <queue>
#include <map>
#define MAX_W 36698
using namespace std;
typedef char mt;
class Vertex;
class Edge;
class Graphs;
class GraphFactory;
enum visit {visited,notVisited};
class Vertex
{
public:
mt data;
int visited;
int weightSum;
list<Edge*> adList;
Vertex(mt d=0):adList(0){
> visited = notVisited;
weightSum = MAX_W;
}
~Vertex(){
adList.clear();
}
void Add_Edge(Edge* e){
adList.push_back(e);
}
};
class Edge
{
public:
int weight;
Vertex* from;
Vertex* to;
int id=0;
Edge(){}
Edge(Vertex* f, Vertex* t, int w) :weight(w), from(f), to(t){ }
Edge(Vertex* f, Vertex* t, int w,int ID) :weight(w), from(f), to(t),id(ID){ }
~Edge(){ from = NULL; to = NULL; }
};
class GraphFactory
{
private:
int edgeCNT = 0;
public:
Edge* MakeEdge(Vertex* f, Vertex* t, int w){
edgeCNT++;
return new Edge(f, t, w,edgeCNT);
}
Vertex* MakeVertex(mt d){
return new Vertex(d);
}
};
class Graphs
{
public:
list<Vertex*> vertices;
public:
Graphs() :vertices(0){ }
~Graphs(){
vertices.clear();
}
void Add_Vertex(Vertex* v){
vertices.push_back(v);
}
void TestPrint() ;
void DFS(Vertex* v);
void BFS(Vertex* v);
list<Vertex*> getVertices(){ return vertices; }
};
void Graphs::TestPrint()
{
list<Vertex*>::iterator vIter;
list<Edge*>::iterator eIter;
for (vIter = vertices.begin(); vIter != vertices.end(); vIter++){
for (eIter = (*vIter)->adList.begin(); eIter != (*vIter)->adList.end(); eIter++)
cout << (*eIter)->from->data << " -> " << (*eIter)->to->data<<endl;
}
}
void Graphs::DFS(Vertex* v)
{
list<Edge*>::iterator eIter;
cout << v->data<<" ";
v->visited = visited;
for (eIter = v->adList.begin(); eIter != v->adList.end(); ++eIter){
if ((*eIter)->to != NULL && (*eIter)->to->visited == notVisited)
DFS((*eIter)->to);
}
}
void Graphs::BFS(Vertex* v)
{
list<Edge*>::iterator eIter;
queue<Vertex*> que;
Vertex* cur;
que.push(v);
while (!que.empty()){
cur = que.front();
if (cur->visited == visited){
que.pop();
continue;
}
cout << cur->data << " ";
cur->visited = visited;
que.pop();
eIter = cur->adList.begin();
while (eIter != cur->adList.end()){
if ((*eIter)->to->visited == notVisited){
que.push((*eIter)->to);
}
++eIter;
}
}
}
class Dijkstra :public Graphs
{
private:
map<int,Edge*> nodes;
Vertex* root;
Vertex* dest;
public:
Dijkstra() :Graphs(){ }
Graphs* Make_Way(Vertex* r);
//Override
void Add_Vertex(Vertex* v);
void Add_Edges(map<int, Edge*> &lines, list<Edge*>::iterator &eIter, list<Edge*>::iterator &eIterEnd){
while (eIter != eIterEnd){
lines[((*eIter)->id)] = (*eIter);
eIter++;
}
}
};
void Dijkstra::Add_Vertex(Vertex* v)
{
vertices.push_back(v);
Edge* e = new Edge(v, v, -1);
nodes[e->id] = e;
}
Graphs* Dijkstra::Make_Way(Vertex* r)
{
map<int, Edge*> lines;
GraphFactory fac;
Graphs* dstra;
map<int, Edge*>::iterator mapIter;
list<Vertex*>::iterator vIter = vertices.begin();
Edge* e=NULL;
Vertex* v=NULL;
int curW = MAX_W;
int lineIndex = 0;
r->weightSum = 0;
Add_Edges(lines, r->adList.begin(), r->adList.end());
if (vertices.empty())return NULL;
dstra = new Graphs();
while (vIter != vertices.end()){
dstra->Add_Vertex(fac.MakeVertex((*vIter)->data));
vIter++;
}
while (!lines.empty()){
lineIndex = lines.begin()->first;
e = lines[lineIndex];
curW = e->from->weightSum + e->weight;
v = e->to;
if (v->visited == notVisited || v->weightSum == MAX_W){
nodes[e->id] = e;
v->visited = visited;
v->weightSum = curW;
Add_Edges(lines, v->adList.begin(), v->adList.end());
}
else if ( e->to->weightSum > curW){
mapIter = nodes.begin();
while (mapIter != nodes.end()){
if ((*mapIter).second->to-> v- gt;data){
nodes.erase((*mapIter).first);
nodes[e->id] = e;
break;
}
mapIter++;
}
v->visited = visited;
v->weightSum = curW;
Add_Edges(lines, v->adList.begin(), v->adList.end());
}
lines.erase(lineIndex);
}
mapIter = nodes.begin();
while (mapIter != nodes.end()){
e = (*mapIter).second;
if (e->from->data != e->to->data){
vIter = dstra->vertices.begin();
while (vIter != dstra->vertices.end()){
if ((*vIter)-> e->from->data)
break;
vIter++;
}
(*vIter)->Add_Edge(e);
}
mapIter++;
}
return dstra;
}
댓글 0