그래프

그래프는 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다
그래프 G 객체를 나타내는 정점과 객체를 연결하는 간선의 집합
G = (V,E)
V 는 그래프에 있는 정점들의 집합
E는 정점을 연결한는 간선들의 집합

오일러 경로

(그림이 발컨이다 ..)
그래프 하면 나오는 대표적인 문제로 오일러 경로가 있다
다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제이다

오일러정리
모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가 존재함
따라서 위 이미지에는 오일러 경로가 존재하지않는다
홀수개이면 들어갔다가 돌아오는 경로가 부족하기 때문이다

그래프의 종류

무방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프이다
정점 V1 과 V2를 연결하는 간선을 (V1, V2)로 표현을 하는데 이때 간선에 방향이 없기 때문에 (V1,V2)와 (V2,V1)은 같은 간선을 의미한다

방향 그래프

간선에 방향이 있는 그래프이다
정점 V1에서 V2를 연결하는 간선 V1->V2를 <V1,V2>로 표현을한다
이때 V1 을 꼬리 V2를 머리라고 한다
무방향 그래프와 다르게 (V1,V2)와 (V2,V1)은 다르 간선을 의미한다

완전 그래프

각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프이다
정점이 n개인 무방향 그래프에서는 최대 간선 수는 n(n-1)/2개 가 된다
무방향 그래프 이미지의 그래프에서 54/2=10개가 최대 간선수가 된다
정점이 n개 인 방향그래프에서는 n(n-1)개가 된다
마찬가지로 방향그래프 이미지의 그래프에서 최대간선의 수는 54=20개가 된다

부분 그래프

원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프이다

가중 그래프 , 네트워크

정점을 연결하는 간선에 가중치를 할당한 그래프이다

그래프 용어

인접: 그래프에서 두 정점 v1과 v2를 연결하는 간선 (v1 ,v2)가 있을때 두 정점 v1,v2를 '인접'되어 있다고 하고 , 간선 (v1,v2)ㄴ느 점점 v1과 v2에 부속 되어있다고한다

차수: 정점에 부속되어있는 간선의 수

경로: 그래프에서 간선을 따라 갈수있는길을 순서대로 나열한것, 정점 v(i)에서 v(j)까지의 간선으로 연결된 정점을 순서대로 나열한 리스트
경로길이 - 경로를 구성하는 간선의 수

단순 경로: 모든 다른 정점으로 구성된경로

사이클: 단순 경로 중에서 시작 정점과 마지막 정점이 같은 경로
다시 돌아오는 경로라고 보면 된다

DAG 방향 그래프이면서 사이클이 없는 그래프

연결그래프: 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프 , 즉 떨어져 있는 정점이 없는 그래프
그래프에서 두정점 V(I) 에서 V(J)까지 경로가 있으면 연결되어있다고 한다
트리는 사이클이 없는 연결그래프이다

그래프 구현

그래프 구현에는 인접행렬과 인접리스트로 구현하는 방법이 있다

인접행렬 구현

#include<iostream>
using namespace std;

#define SIZE 10
template<typename T>
class AdjacencyMatrix
{
private:
	int Matrix[SIZE][SIZE]; // 인접행렬 
	int size; //정점 개수 
	T buffer[SIZE]; //정점의 집합
public:
	AdjacencyMatrix() //초기화 
	{
		size = 0;
		for (int i = 0; i < SIZE; i++)
		{
			buffer[i] = NULL;
			for (int j = 0; j < SIZE; j++)
			{
				Matrix[i][j] = NULL;
			}
		}
	}
	void Insert(T data) //정점 나타내기위함 
	{
		if (size >= SIZE)
		{
			cout << "Matrix is Full" << '\n';
		}
		buffer[size++] = data;
	}
	void Insert(int i, int j, int value = 1) //간선 세우기 
	{
		if (size <= 0)
		{
			cout << "Empty Vetrix" << '\n';
		}
		if (i >= size || j >= size)
		{
			cout << "Out of Range" << '\n';
		}
		Matrix[i][j] = value;
		Matrix[j][i] = value; //무방향
	}
	void Show()
	{
		cout << ' ';
		for (int i = 0; i < size; i++)
		{
			cout << buffer[i] << ' ';
		}
		cout << '\n';
		for (int i = 0; i < size; i++)
		{
			cout << buffer[i] << ' ';
			for (int j = 0; j < size; j++)
			{
				cout << Matrix[i][j] << ' ';
			}
			cout << '\n';
		}
	}
};

int main()
{
	AdjacencyMatrix <char> matrix;

	matrix.Insert('A');
	matrix.Insert('B');
	matrix.Insert('C');
	matrix.Insert('D');
	matrix.Insert(1, 3);
	matrix.Show();

	return 0;
}

정점 D와 정점 B는 간선으로 이어졌다

인접행렬 장-단점

장점
두 정점이 연결되어 있는지 확인하기가 쉽다
두 정점 사이의 간선의 가중치를 쉽게 확인이 가능하다

단점
정점의 개수가 많을 때 메모리 낭비가 쉽다
특정 정점과 연결된 정점을 찾을때 시간이 오래걸린다

인접 리스트

#include"iostream"
using namespace std;
#define SIZE 10

template<typename T>

class AdjacencyList
{
private:
	struct Node
	{
		Node* next;
		T data;
		Node(T data, Node* link = NULL)
		{
			this->data = data;
			next = link;
		}
	};
	int size;//정점의 개수
	T vertex[SIZE]; // 정점의 집합
	Node* graphList[SIZE];//인접 리스트 
public :
	AdjacencyList()
	{
		size = 0;
		for (int i = 0; i < SIZE; i++)
		{
			vertex[i] = NULL;
			graphList[i] = NULL;
		}
	}
	~AdjacencyList()
	{
		for (int i = 0; i < size; i++)
		{
			if (graphList[i] != NULL)
			{
				delete graphList[i];

			}

		}

		cout << endl << "SUCCESSFUL DELETION" << endl;
	}
	void Insert(T data)
	{
		if (size > SIZE)
		{
			cout << "List is Full" << '\n';
			return;
		}
		vertex[size++] = data;
	}
	void Insert(int u, int v)
	{
		if (size <= 0)
		{
			cout << "List is Empty" << '\n';
			return;
		}
		if (u >= size || v >= size)
		{
			cout << "Out of Range" << '\n';
			return;

		}
		graphList[u] = new Node(vertex[v], graphList[u]);
		graphList[v] = new Node(vertex[u], graphList[v]);
	}
	void Print()
	{
		for (int i = 0; i < size; i++)
		{
			Node* currentNode = graphList[i];
			cout << vertex[i] << ": ";
			while (currentNode)
			{
				if (currentNode)
				{
				   cout << currentNode->data << ' ';
					currentNode = currentNode->next;
				}
			}
			cout << "\n";
		}
	}
};
int main()
{
	AdjacencyList<char>list;
	list.Insert('A');
	list.Insert('B');
	list.Insert('C');
	list.Insert('D');

	list.Insert(0, 1);
	list.Insert(0, 2);
	list.Insert(0, 3);
	list.Insert(2, 3);

	list.Print();
	return 0;
}

정점 A는 정점 D ,C,B와 연결되어있다
정점 B는 정점 A와 연결되어있다
정점C는 정점 D, A 와 연결되어있다
정점 D는 정점 C,A와 연결되어있다

인접 리스트 장-단점

장점
인접리스트는 행렬과 다르게 필요한 만큼만 메모리를 사용한다

단점
하지만 V(I) V(J)의 연결상태를 보려면 모든 원소를 돌아야 하므로 시간이 오래걸린다