Graphs, DFS, BFS

생성일: 2021년 11월 27일 오전 12:24

stack과 queue도 불러와서 사용하였다.

GraphType.h

#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를 방문한 적이 있는지에 대한 유무를 저장.
};

GraphType.cpp

#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;
}

DFSearch.cpp

#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;
}

BFSearch.cpp

#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;
}

ShortestPath.cpp

#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());
}