트리

트리(Tree)는 계층적(hierarchical) 데이터 구조로 여러 개의 노드(node)가 부모-자식 관계로 연결되어 있는 자료구조이다.

      A (루트)
     / \
    B   C
   /     \
  D       E

BST

이진 탐색 트리(BST)는 이전 트리의 한 종류로, 탐색에 최적화된 구조를 가진다.
탐색, 삽입, 삭제가 O(log N)의 시간 복잡도를 가진다.
아래의 규칙을 지켜야한다.

1. 왼쪽 서브트리의 값 < 부모 노드의 값
2. 오른쪽 서브트리의 값 > 부모 노드의 값
3. 이러한 규칙이 모든 노드에 재귀적으로 적용됨

---

그래프

그래프(Graph)는 정점(Vertex)와 간선(Edge)로 이루어진 비선형 데이터 구조이다.
트리는 특정한 계층 구조를 가졌지만, 그래프는 트리보다 더 자유로운 형태를 가지고 있다.
그래프는 모든 방향으로 연결될 수 있는 자료구조이다.

그래프는 현실 세계의 다양한 관계를 표현하는데 유용하다.

• SNS -> 사람(노드)들이 친구 관계(간선)로 연결된 형태
• 교통망 -> 도시(노드) 간의 도로(간선) 연결
• 웹 페이지 구조 -> 웹 페이지(노드)들이 링크(간선)로 연결

그래프는 아래로 이루어져있다.

• 정점(Vertex) : 그래프에서 데이터를 담고 있는 요소
  • 노드(Node)라고도 부른다.
• 간선(Edge) : 노드 간의 연결을 의미함

그래프는

• 방향성이 있을 수도 있고 없을 수도 있다.
• 가중치가 있을 수도 있고 없을 수도 있다.
• 순환이 있을 수도 있고 없을 수도 있다.

그래프를 컴퓨터에서 표현할 때 크게 2가지로 표현할 수 있데 오늘은 인접 행렬만 알아본다.

인접 행렬(Adjacenct Matrix)

      A  B  C  D
    ----------------
  A | 0  1  0  1
  B | 1  0  1  1
  C | 0  1  0  1
  D | 1  1  1  0

위의 인접 행렬의 경우에는 비가중치 그래프이다.
가중치라고 하면 1 대신 가중치 값을 저장하면 된다.

• 장점
  • 간선이 존재하는지 여부를 O(1) 시간에 확인 가능
  • 구현이 단순함 (배열만 사용)
  • 가중치 그래프에 쉽게 확장 가능
• 단점
  • 공간 복잡도 O(V²)
    • 노드 수가 많으면 메모리 낭비 심함
  • 연결된 노드를 찾는 데 O(V)

직접 짠 그래프 코드

인접 행렬으로 설정 가능하게 제작했다.

class Graph
{
public:
	class Edge
	{
	public:
		int toIndex;
		float weight;

	public:
		Edge(int to, float weightValue = 1)
		{
			toIndex = to;
			weight = weightValue;
		}
	};

	class Node
	{
	public:
		int index;
		vector<Edge> edges;

	public:
		void AddEdge(Edge edge)
		{
			edges.push_back(edge);
		}
	};

private:
	vector<Node> nodes;

public:
	void AddNode()
	{
		Node n;
		n.index = nodes.size();
		nodes.push_back(n);
	}

	void AddEdge(int from, int to, float weight = 1)
	{
		nodes[from].AddEdge(Edge(to, weight));
	}

	Node& Get(int index)
	{
		return nodes[index];
	}

	void Print()
	{
		for (int i = 0; i < nodes.size(); i++)
		{
			cout << "Node" << i << " : ";

			for (int j = 0; j < nodes[i].edges.size(); j++)
				cout << "[" << nodes[i].edges[j].toIndex << (nodes[i].edges[j].weight ? ", " + to_string(nodes[i].edges[j].weight) : "") << "] ";

			cout << endl;
		}
	}
};

int main()
{
	Graph g;

	int nodeCount;
	cout << "노드 갯수 : ";
	cin >> nodeCount;

	for (int i = 0; i < nodeCount; i++)
		g.AddNode();

	for (int i = 0; i < nodeCount; i++)
		for (int j = 0; j < nodeCount; j++)
		{
			//weight 값
			float temp;
			cin >> temp;

			if (temp)
				g.AddEdge(i, j, temp);
		}

	g.Print();
}