'그래프' 태그의 글 목록

그래프

트리와 그래프는 모두 정점(Vertex)과 간선(Edge)으로 구성된 자료구조트리(Tree)의 특징정의:트리는 사이클이 없는 연결된 그래프모든 노드가 하나의 루트에서 시작하여 부모-자식 관계로 연결특징:N개의 정점이 있다면, N-1개의 간선이 존재사이클이 존재하지 않음 (Cycle-Free).항상 연결 그래프 (Connected Graph).노드 간에 유일한 경로가 존재합니다 (두 노드 사이의 경로는 하나뿐).루트 노드:트리에는 반드시 루트 노드가 존재하며, 이는 트리의 최상위 노드트리의 탐색은 이 루트 노드에서 시작방향성:트리는 일반적으로 방향성이 있으며, 부모 → 자식으로 진행그래프(Graph)의 특징정의:그래프는 정점과 간선으로 구성된 자료구조로, 간선이 정점 쌍을 연결방향성이 있을 수도 있고 없을..

자료구조&알고리즘/C++ 2025. 1. 23. 11:12

그래프 vs 트리

그래프(Graph)와 트리(Tree)는 컴퓨터 과학과 자료구조에서 중요한 개념으로, 트리는 그래프의 한 특수한 형태1. 그래프의 정의구조: 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조.종류:방향 그래프(Directed Graph): 간선에 방향이 있는 그래프.무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프.특성:사이클(Cycle)을 가질 수 있음.연결 그래프(Connected Graph)일 수도 있고, 아닐 수도 있음.루프(Self-loop)와 다중 간선(Multiple edges)을 허용할 수 있음.2. 트리의 정의구조: 트리는 그래프의 특수한 형태로, 방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 한 유형.특성:루트 노드(Roo..

자료구조&알고리즘/C++ 2025. 1. 13. 20:31

항해 99 //백준 11657 //타임머신//벨만 포드(Bellamn- Ford) 알고리즘

https://www.acmicpc.net/problem/11657 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.벨만 포드(Bellamn- Ford) 알고리즘음수 가중치가 있고 음수 사이클이 있는 그래프에서 단일 출발점 최단 경로를 구하는 알고리즘(음수 사이클이 존재하는 것도 판별할 수 있음 -> 만약 타임머신, 블랙홀 , 과거로 돌아갈 수 있다는 워딩이 있다면 ..

cote/Challenge 2025. 1. 13. 20:02