생성일: 2021년 11월 27일 오전 12:24
stack과 queue도 불러와서 사용하였다.
#include "QueType.h"
template<class VertexType>
class GraphType
{
public:
GraphType(int maxV);
~GraphType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void AddVertex(VertexType);
void AddEdge(VertexType, VertexType, int);
int WeightIs(VertexType, VertexType);
void GetToVertices(VertexType, QueType<VertexType>&);
//아래의 세 함수는 traversal을 위해 필요한 함수들
void ClearMarks();
void MarkVertex(VertexType);
bool IsMarked(VertexType);
private:
int numVertices; // 현재 저장하고 있는 vertex 수
int maxVertices; // 최대 vertex 수
VertexType* vertices; //1차원 어레이 => vertex의 정보를 저장 => 특정 vertex의 정보를 찾으려면 여기서 그 vertex의 인덱스번호를 찾고 edges에서 해당 인덱스를 확인해야 함
int** edges; // 2차원 어레이로 받아야 하기 때문에 이중 포인터 사용
bool* marks; // marks[i]는 i번째 vertex를 방문한 적이 있는지에 대한 유무를 저장.
};
#include "GraphType.h"
const int NULL_EDGE = 0;
template<class VertexType>
GraphType<VertexType>::GraphType(int maxV)
{
numVertices = 0;
maxVertices = maxV;
vertices = new VertexType[maxV];
//edges를 이차원 어레이로 만드는 과정 => edges[i][j] 처럼 접근 가능해짐
edges = new int[maxV];
for (int i = 0; i < maxV; i++)
edges[i] = new int[maxV];
marks = new bool[maxV];
}
template<class VertexType>
GraphType<VertexType>::~GraphType()
{
delete[] vertices;
for (int i = 0; i < maxVertices; i++)
delete[] edges[i];
delete[] edges;
delete[] marks;
}
template<class VertexType>
void GraphType<VertexType>::AddVertex(VertexType vertex)
{
vertices[numVertices] = vertex;
for (int index = 0; index < numVertices; index++)
{
edges[numVertices][index] = NULL_EDGE;
edges[index][numVertices] = NULL_EDGE;
}
numVertices++;
}
// IndexIs함수는 멤버함수가 아니다.
// 1차원 어레이인 vertices에서 원하는 vertex의 인덱스 번호를 찾아서 리턴
template<class VertexType>
int IndexIs(VertexType* vertices, VertexType vertex)
{
int index = 0;
while (!(vertex == vertices[index]))
index++;
return index;
}
template<class VertexType>
void GraphType<VertexType>::AddEdge(VertexType fromVertex,
VertexType toVertex, int weight)
{
int row;
int col;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
edges[row][col] = weight;
}
template<class VertexType>
int GraphType<VertexType>::WeightIs
(VertexType fromVertex, VertexType toVertex)
{
int row;
int col;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
return edges[row][col];
}
template<class VertexType>
void GraphType<VertexType>::GetToVertices(VertexType vertex,
QueType<VertexType>& adjVertices)
{
int fromIndex;
int toIndex;
fromIndex = IndexIs(vertices, vertex);
for (toIndex = 0; toIndex < numVertices; toIndex++)
if (edges[fromIndex][toIndex] != NULL_EDGE)
adjVertices.Enqueue(vertices[toIndex]);
}
//여기부터 직접 구현
template<class VertexType>
void GraphType<VertexType>::MakeEmpty()
{
for (int i = 0; i < maxVertices; i++)
{
for (int j = 0; j < maxVertices; j++)
edges[i][j] = NULL_EDGE;
}
for (int i = 0; i < maxVertices; i++)
{
vertices[i] = NULL_EDGE;
}
numVertices = 0;
}
template<class VertexType>
bool GraphType<VertexType>::IsEmpty() const
{
return numVertices == 0;
}
template<class VertexType>
bool GraphType<VertexType>::IsFull() const
{
return numVertices == maxVertices;
}
template<class VertexType>
void GraphType<VertexType>::ClearMarks()
{
for (int i = 0; i < maxVertices; i++)
{
marks[i] = false;
}
}
template<class VertexType>
void GraphType<VertexType>::MarkVertex(VertexType vertex)
{
int index = IndexIs(vertices, vertex);
marks[index] = true;
}
template<class VertexType>
bool GraphType<VertexType>::IsMarked(VertexType vertex)
{
int index = IndexIs(vertices, vertex);
return marks[index] == true;
}
#include "GraphType.h"
#include "StackTType.h"
template<class VertexType>
void DepthFirstSearch(GraphType<VertexType> graph,
VertexType startVertex, VertexType endVertex)
{
using namespace std;
StackType<VertexType> stack; //Stack 사용
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
graph.ClearMarks(); //vertex들을 아직 한개도 방문 안했기 때문에 전부 mark를 전부 false로 바꿔 줌
stack.Push(startVertex);
do
{
stack.Pop(vertex);
if (vertex == endVertex)
{
cout << vertex;
found = true;
}
else
{
if (!graph.IsMarked(vertex))
{
graph.MarkVertex(vertex); //이제 방문했기때문에 mark 함
cout << vertex;
graph.GetToVertices(vertex, vertexQ); //vertex와 연결된 vertex들을 queue에 넣는다.
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(item);
if (!graph.IsMarked(item))
stack.Push(item);
}
}
}
} while (!stack.IsEmpty() && !found);
if (!found)
cout << "Path not found." << endl;
}
#include "GraphType.h"
template<class VertexType>
void BreadthFirstSearch(GraphType<VertexType> graph,
VertexType startVertex, VertexType endVertex)
{
using namespace std;
QueType<VertexType> queue;
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
graph.ClearMarks(); //vertex들을 아직 한개도 방문 안했기 때문에 전부 mark를 전부 false로 바꿔 줌
queue.Enqueue(startVertex);
do
{
queue.Dequeue(vertex);
if (vertex == endVertex)
{
cout << vertex;
found = true;
}
else
{
if (!graph.IsMarked(vertex))
{
graph.MarkVertex(vertex); //방문 했기 때문에 mark하기
cout << vertex;
graph.GetToVertices(vertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(item);
if (!graph.IsMarked(item))
queue.Enqueue(item);
}
}
}
} while (!queue.IsEmpty() && !found);
if (!found)
cout << "Path not found." << endl;
}
#include "GraphType.h"
#include <iostream>
template<class VertexType>
struct ItemType
{
bool operator<(ItemType otherItem);
// ??means greater distance
bool operator==(ItemType otherItem);
bool operator<=(ItemType otherItem);
VertexType fromVertex;
VertexType toVertex;
int distance;
};
template<class VertexType>
void ShortestPath(GraphType<VertexType> graph,
VertexType startVertex)
{
using namespace std;
ItemType item;
int minDistance;
PQType<VertexType> pq(10); // Assume at most 10 vertices
QueType<VertexType> vertexQ;
VertexType vertex;
graph.ClearMarks();
item.fromVertex = startVertex;
item.toVertex = startVertex;
item.distance = 0;
pq.Enqueue(item);
cout << "Last Vertex Destination Distance" << endl;
cout << "-------------------------------------" << endl;
do
{
pq.Dequeue(item);
if (!graph.IsMarked(item.toVertex))
{
graph.MarkVertex(item.toVertex);
cout << item.fromVertex;
cout << " ";
cout << item.toVertex;
cout << " " << item.distance << endl;
item.fromVertex = item.toVertex;
minDistance = item.distance;
graph.GetToVertices(item.fromVertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(vertex);
if (!graph.IsMarked(vertex))
{
item.toVertex = vertex;
item.distance = minDistance +
graph.WeightIs(item.fromVertex, vertex);
pq.Enqueue(item);
}
}
}
} while (!pq.IsEmpty());
}