구현 - 인접행렬과 인접리스트를 이용한 BFS, DFS

대략 정신이 혼미해진다.

graph.txt

graph2.txt

main.cpp

#include "AdjMatGraph.h"

#include "AdjListGraph.h"

int main()

{

cout << "matrix \n";

AdjMatGraph g;

g.load("graph.txt");

g.display();

g.depth_first_search(0);

cout << endl;

g.resetVisited();

g.breadth_first_search(0);

cout << endl << endl;

cout << "linkedlist \n";

AdjListGraph lg;

lg.load("graph.txt");

lg.display();

lg.depth_first_search(0);

cout << endl;

lg.resetVisited();

lg.breadth_first_search(0);

cout << endl << endl;

cout << "connected componenet\n";

AdjMatGraph g2;

g2.load("graph2.txt");

g2.display();

g2.resetVisited();

g2.findConnectedComponent();

}

AdjListGraph.h

#pragma once

#include <iostream>

#include <fstream>

#include <queue>

using namespace std;

#define MAX_VTXS 256

class GNode

{

protected:

int id;

GNode* link;

public:

GNode(int i, GNode* link = nullptr) : id(i), link(link){}

~GNode() {

if (link) delete link;

}

int getId() { return id; }

GNode* getLink() { return link; }

void setLink(GNode* lin) { link = lin; }

};

class AdjListGraph

{

protected:

int size{};

char vertexName[MAX_VTXS];

GNode* adjacentListOf[MAX_VTXS];

bool visited[MAX_VTXS]{};

public:

AdjListGraph() {  }

~AdjListGraph() { reset(); }

void reset()

{

for (int i = 0; i < size; ++i)

if (adjacentListOf[i] != nullptr) delete adjacentListOf[i];

size = 0;

}

char getVertex(int i) { return vertexName[i]; }

bool isEmpty() { return size == 0; }

bool isFull() { return size >= MAX_VTXS; }

void resetVisited()

{

for (int i = 0; i < size; ++i)

visited[i] = false;

}

bool isLinked(int u, int v)

{

for (auto p = adjacentListOf[u]; p != nullptr; p = p->getLink())

if (p->getId() == v) return true;

return false;

}

void depth_first_search(int vIndex)

{

visited[vIndex] = true;

cout << vertexName[vIndex];

for (auto p = adjacentListOf[vIndex]; p != nullptr; p = p->getLink())

if (!visited[p->getId()])

depth_first_search(p->getId());

}

void breadth_first_search(int vIndex)

{

std::queue<int> q;

q.push(vIndex);

visited[vIndex] = true;

while (!q.empty())

{

int index = q.front();

cout << vertexName[index];

q.pop();

for (auto iter = adjacentListOf[index]; iter != nullptr; iter = iter->getLink())

{

int id = iter->getId();

if (!visited[id])

{

visited[id] = true;

q.push(id);

}

}

}

}

void insertVertex(char name)

{

if (!isFull())

{

vertexName[size] = name;

adjacentListOf[size++] = nullptr;

}

else printf("Error: 그래프 정점 개수 초과\n");

}

void insertEdge(int u, int v, int val)

{

adjacentListOf[u] = new GNode(v, adjacentListOf[u]);

}

void display(ostream& out = cout)

{

out << size << endl;

for (int i = 0; i < size; i++)

{

cout << vertexName[i] << " : ";

for (GNode* v = adjacentListOf[i]; v != nullptr; v = v->getLink())

cout << vertexName[v->getId()];

cout << endl;

}

}

GNode* adjacent(int v) { return adjacentListOf[v]; }

void load(char* filename)

{

ifstream is(filename);

int size;

is >> size;

for (int i = 0; i < size; ++i)

{

char vertexName[100];

is >> vertexName;

insertVertex(*vertexName);

for (int j = 0; j < size; ++j)

{

int val;

is >> val;

if (val != 0)

insertEdge(i, j, val);

}

}

}

void save(char* filename)

{

ofstream os(filename);

display(os);

}

};

AdjMatGraph.h

#pragma once

#include <iostream>

#include <fstream>

#include <queue>

using namespace std;

#define MAX_VTXS 256

class AdjMatGraph

{

protected:

int size{};

char vertexName[MAX_VTXS]{};

int edge[MAX_VTXS][MAX_VTXS]{};

bool visited[MAX_VTXS]{};

int label[MAX_VTXS];

public:

AdjMatGraph() { reset(); }

char getVertex(int i) { return vertexName[i]; }

int getEdge(int i, int j) { return edge[i][j]; }

void setEdge(int i, int j, int val) { edge[i][j] = val; }

bool isEmpty() { return size == 0; }

bool isFull() { return size >= MAX_VTXS; }

void resetVisited()

{

for (int i = 0; i < size; ++i)

visited[i] = false;

}

void depth_first_search(int vIndex)

{

visited[vIndex] = true;

label[vIndex] = true;

cout << vertexName[vIndex];

for (int i = 0; i < size; ++i)

if (edge[vIndex][i] && !visited[i])

depth_first_search(i);

}

void depth_first_search_color(int vIndex, int color)

{

visited[vIndex] = true;

label[vIndex] = color;

for (int i = 0; i < size; ++i)

if (edge[vIndex][i] && !visited[i])

depth_first_search_color(i, color);

}

void breadth_first_search(int vIndex)

{

std::queue<int> q;

q.push(vIndex);

visited[vIndex] = true;

while (!q.empty())

{

int index = q.front();

cout << vertexName[index];

q.pop();

for (int i = 0; i < size; ++i)

{

if (edge[index][i] && !visited[i])

{

visited[i] = true;

q.push(i);

}

}

}

}

void findConnectedComponent()

{

int count = 0;

for (int i = 0; i < size; ++i)

{

if (!visited[i])

depth_first_search_color(i, ++count);

}

cout << "colored count : " << count << endl;

for (int i = 0; i < size; ++i)

{

cout << vertexName[i] <<" : " << label[i] << endl;

}

cout << endl;

}

void reset()

{

size = 0;

for (int i = 0; i < MAX_VTXS; ++i)

for (int j = 0; j < MAX_VTXS; ++j)

setEdge(i, j, 0);

}

void insertVertex(char name)

{

if (!isFull()) vertexName[size++] = name;

else printf("Error: 그래프 정점 개수 초과\n");

}

void insertEdge(int u, int v, int val)

{

edge[u][v] = val;

edge[v][u] = val;

}

void display(ostream& out = cout)

{

out << size << endl;

for (int i = 0; i < size; i++) 

{

cout << vertexName[i] << " : ";

for (int j = 0; j < size; j++)

cout << edge[i][j] << " ";

cout << endl;

}

}

void load(char* filename)

{

ifstream is(filename);

int size;

is >> size;

for (int i = 0; i < size; ++i)

{

char vertexName[100] ;

is >> vertexName;

insertVertex(*vertexName);

for (int j = 0; j < size; ++j)

{

int val;

is >> val;

if (val != 0)

insertEdge(i, j, val);

}

}

}

void save(char* filename)

{

ofstream os(filename);

display(os);

}

};