그래프(Graph)의 이해와 종류 - 14장 (1)

그래프와 관련된 용어

위 그림과 같이 그래프에서는 정점(vertex)는 연결의 대상이 되는 개체 또는 위치.

간선은 그들 사이의 연결(다리)이다.

 

더 간단한 그림의 예시를 본다. 다음은 비상연락망 구조를 표현한 그래프.

위의 그래프에서는 방향성이 빠져있다. 이렇듯 그래프의 연결 관계에 있어서 방향성이 없는 그래프를 가리켜

'무방향 그래프'라고 한다.

 

그리고 위와 같이 간선에 방향정보가 포함되어 있으면 '방향 그래프'

 

 

가중치 그래프와 부분 그래프

다음 그림에서 보이듯 간선에 가중치 정보를 넣을 수 있다.

이러한 형태의 그래프를 가리켜 가중치 그래프라 표현한다.

 

이 때 가중치가 되는 값은 다양하게 설정할 수 있다. 예로들어

1. A정점에서 B정점까지 걸리는 '시간'

2. A정점에서 B정점까지 걸리는 '거리'

등. 만약 A정점부터 시작해 C 정점까지 가는데 최소 비용(거리)은 6.(A->B->C)

 

그리고 다음과 같은 그래프.

위와 같은 형태의 그래프를 부분 그래프. 부분 집합이 원 집합의 일부 원소로 이루어진 집합인것 처럼.

부분 그래프는 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 뜻한다.

 

 

그래프를 구현하는 두 가지 방법

그래프를 구현하는 방법에 있어서 배열을 사용하는 방법, 연결 리스트를 이용하는 방법이 있다.

 

1. 인접 행렬 기반 그래프 - 정방 행렬(n x n크기의 행렬 - 2차원 배열)

2. 인접 리스트 기반 그래프 - 연결 리스트, 혹은 C++의 STL컨테이너 vector를 통해 비슷하게 사용가능.

 

우선 인접 행렬 기반 그래프.

위 그림과 같이. A,B,C,D 정점이 4개인 그래프는 4x4크기의 행렬. 즉 2차원 배열을 선언한다.

그리고 두 정점이 연결되어 있다면 내부 값으로 1을 그게 아니라면 0으로 표시한다.

(기본적으로 초기화할 때 0으로 모두 초기화를 해주는게 좋다)

 

위 그림은 간선에 방향이 없는 무 방향 그래프이기에. A행의 B열의 1이. B행의 A열이 1이 세팅된것을 알 수 있다.

-> 즉 무방향 그래프라면 arr[m][n] = 1일때, arr[n][m]도 1을 대입해야한다.

 

그 다음은 방향이 존재하는 인접 행렬 기반 그래프.

무방향 그래프와는 달리. 어느 정점에서 다른 정점으로 가는 방향 간선정보가 존재할 때만 1을 넣어준다.

 

이제 인접 리스트 기반의 그래프

우선 위 그래프도 무방향. 즉 인접 행렬 기반 그래프던 인접 리스트 기반 그래프던간에 무방향,방향 그래프를 확인해야한다.

 

인접 리스트 기반의 그래프는 하나의 정점이 자신과 연결된 정점의 정보를 담기 위해 하나의 연결리스트를 가진다.

그리고 각각의 정점에 연결된 간선의 정보는 각각의 연결 리스트에 담아야한다.

-> 인접 행렬에 비해 메모리 공간 효율성이 높음.

 

그 다음은 인접 리스트 방향 그래프를 본다.

똑같이. 어느정점에서 다른 정점으로 가는 간선이 존재할 때 정점에 연결된 정점의 정보를 담는다.

 

인접 리스트 기반의 그래프 구현

인접 리스트는 C++의 vector컨테이너를 이용해 간단하게 사용가능하지만, 책의 내용을 참고해 구현.

 

-> ALGraph.h

#pragma once

class LinkedList;

class ALGraph
{
public:
	ALGraph() = delete;
	ALGraph(int inputV);
	~ALGraph(); // adjList 메모리 해제.
	void AddEdge(int fromV, int toV); // 간선 추가
	void ShowGraphEdgeInfo(); // 간선 정보 출력
private:
	int numV; // 정점의 수
	int numE; // 간선의 수
	LinkedList* adjList; // 간선의 정보
};

-> ALGraph.cpp

#include <iostream>
#include "ALGraph.h"
#include "LinkedList.h"

ALGraph::ALGraph(int inputV) : numV(inputV), numE(0)
{
	adjList = new LinkedList[numV]();
}
ALGraph::~ALGraph()
{
	delete[] adjList;
}
void ALGraph::AddEdge(int fromV, int toV)
{
	// 무방향 그래프.
	adjList[fromV].push_front(toV);
	adjList[toV].push_front(fromV);
	++numE;
}

void ALGraph::ShowGraphEdgeInfo()
{
	int i, vx;

	for (i = 0; i < numV; ++i) 
	{
		std::cout << static_cast<char>(i + 'A') << "와 연결된 정점 : ";

		if (adjList[i].LFirst())
		{
			vx = adjList[i].iterator()->GetData();
			std::cout << static_cast<char>(vx + 'A') << " ";
			while (adjList[i].LNext())
			{
				vx = adjList[i].iterator()->GetData();
				std::cout << static_cast<char>(vx + 'A') << " ";
			}
			std::cout << std::endl;
		}
	}
}

-> main.cpp

enum 
{
	A = 0, B, C, D, E, F, G, H, I, J
};

int main()
{
	
	ALGraph a(5);

	a.AddEdge(A, B);
	a.AddEdge(A, D);
	a.AddEdge(B, C);
	a.AddEdge(C, D);
	a.AddEdge(D, E);
	a.AddEdge(E, A);

	a.ShowGraphEdgeInfo();


	return 0;
}

-> 실행결과

이렇게 인접 리스트 기반 그래프의 구현은 어렵지 않다.