그래프

[골4] 1405 - 미친 로봇

#include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define y first #define x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define SIZE 4 double arrProb[SIZE]; double simple; int n..

[골4] 1504 - 특정한 최단 경로

#include #include #include #include using namespace std; using IntPair = pair; #define y first #define x second vector adj[805]; int d[805]; priority_queue pq; const int MAX = 4e8; int N, E; void Dijk(int start) { fill(d, d + N + 2, MAX); d[start] = 0; //첫 번째 길이, 두 번째 정점 pq.push({ d[start],start }); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); if (d[cur.x] != cur.y) continue; for (auto n..

유향 비순환 그래프 (DAG = Directed acyclic graph) 와 Khan 알고리즘을 이용한 위상 정렬 (Topological Sort)

DAG에 대한 토폴로지 정렬 알고리즘 위상 정렬이란 방향이 있는 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것이다. 싸이클이 없는(DAG, Directed Acyclic Graph) 그래프에선 가능하며 하나의 유향 그래프에서 여러 위상 정렬이 가능하다. 시간 복잡도 : O(V + E) / V (Vertex) : 노드, E (Edge) : 간선 => Best Case, Worst Case 동일. DFS와 관련된 다양한 유형의 에지의 출발 시간 사이의 관계이다. Tree edge (u, v): departure[u] > departure[v] Back edge (u, v): departure[u] < departure[v] Forward edge (u, v): dep..

가중치 그래프와 임계 경로(Critical Path)

가중치 그래프 Weighted Graph 숫자로 된 가중치를 각 간선에 부여하여 가중치 그래프(weighted graph)로 확장할 수 있다. 이는 비가중치 그래프를 일반화한 것인데, 비가중치 그래프는 모든 간선의 가중치가 동일해서 생략한 가중치 그래프이고 더 많은 정보를 표현할 수 있어서 유용하다. 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 여행하는데 걸리는 시간일 수 있다. 가중치 그래프는 비가중치 그래프와 유사하게 표현할 수 있다. 인접 행렬로 나타낸다면, 가중치 그래프의 인접 행렬은 엔트리로 간선들의 가중치를 갖거나 연결되지 않은 엔트리들에 대해서는 특수한 값을 갖는다. 아래는 위 그래프를 인접행렬로 표현한 것이다. 이 인접행렬에서는 연결된 간선이 없을 때는 특수 값으로 \i..

그래프 개념

다음 두 가지 요소로 구성된다. Vertex의 집합 Edge의 집합 여기서 Vertex는 "어떤 대상의 객체"를 의미하고, Edge는 "Vertex간의 관계"를 뜻한다. 그래프는 Vertex와 Edge의 set으로 정의되며, 구성된다고 볼 수 있다. Graph와 관련된 용어정리 Graph와 관련되서 알고 있어야할 용어의 종류는 다음과 같다. Vertex : 실세계에서의 어떤 대상을 표현하는 객체 문헌에 따라서 Vertex를 "node"라고 표현하기도 함. Edge : 두 Vertex간에 관계가 존재하는 경우 Edge가 존재한다. 문헌에 따라서 Edge를 "arc"라고 표현하기도 한다. Adjacent : 두 Vertex 간에 Edge가 존재함을 의미 Path : 두 Vertex간에 Edge로서 연결되는 ..

C++ 그래프를 이용한 BFS / DFS 계속 업데이트할 예정

출처 : https://www.youtube.com/watch?v=tWVWeAqZ0WU 첫번째 문제 #include #include #include #include #include using namespace std; #define TOTAL_SIZE 1000 #define y first #define x second vector graph[TOTAL_SIZE]; bool visited[TOTAL_SIZE]{ false }; int edge = 0; void DFS(int _start) { cout

[C] 인접 행렬로 그래프 구현

// 인접 행렬 // 그래프를 인접행렬로 표현하기 #include #include #define MAX_VERTEX 30 typedef struct graphType { int n; // 정점개수 int adjMatrix_Arr[MAX_VERTEX][MAX_VERTEX]; }graphType; // 공백. 그래프를 생성하는 연산 void CreateGraph(graphType* ptr) { ptr->n = 0; // 정점 개수를 0으로 초기화 for (int i = 0; i adjMatrix_Arr[i][j] = 0; } } } // 그래프에 정점 n을 삽입하는 연산 void InsertV..

[C] 인접리스트로 그래프 구현

// 그래프를 인접리스트로 표현하기 #include "stdio.h" #include "stdlib.h " #define MAX_VERTEX 30 // 인접리스트의 노드 구조 typedef struct graphNode { int vertex; // 정점을 나타내는 데이터 필드 graphNode *link; // 다음 인접 정점을 연결하는 링크필드 }graphNode; // 그래프를 인접리스트로 표현하기 위한 구조체 typedef struct graphType { int n; //정점 개수 graphNode *adjList_Arr[MAX_VERTEX]; }graphType; // 공백그래프를 생성하는 연산 void CreateGraph(graphType *ptr) { int v; ptr->n = 0; f..