Algorithms/graphs5 Maximum flow 알고리즘 Network flow란 각각의 간선에 정해진 용량보다 작은 유량이 주어진 방향그래프를 의미함. Maximum flow란 위 수원지에서 수요지까지 공급할 수 있는 최대 유량을 의미함 #include #define MAX_V 10 const int INF = 987654321; int V; typedef struct { int queueArray[MAX_V]; int front; int rear; }Queue; void push(Queue* q, int item) { if ((q->rear + 1) % MAX_V == q->front) { return; } q->queueArray[q->rear] = item; q->rear = (q->rear + 1) % MAX_V; } void pop(Queue* q).. 2021. 6. 21. topological sorting 알고리즘 - 유향 그래프의 정점이 간선의 방향을 거스르지 않도록 나열한 것을 의미함 #include #include #define MAX_N 25 #define MAX_M 25 #define CONNECTED 1 #define NOT_CONNECTED 0 #define NOT_UPDATED_YET 0 #define NOT_VISITED -1 #define DUPLICATE -2 int map[MAX_N][MAX_N] = { 0, }; int count[MAX_N] = { 0, }; int test_case, n, m; typedef struct { int queue[MAX_N]; int cur_ptr; int last_ptr; } Queue; void queue_reset(Queue* queue) { queue-.. 2021. 6. 21. minimum spanning tree 알고리즘 - 네트워크(가중치가 간선에 할당된 그래프)에 있는 모든 정점들을 가장 적은 비용으로 연결하는 트리 - 가공된 데이터를 사용하는 것을 배움 #include int V; int graph[100][100]; int minKey(int* key, unsigned char* mstSet) { int min = 2147483647; int min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == 0 && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } void printMST(int parent[]) { int weightSum = 0; for (int i = 1; i < V; i++) { .. 2021. 6. 21. Floyd-Warshall 알고리즘 - 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘 - 제일 바깥쪽 반복문은 거쳐가는 꼭짓점 - 두 번째 반복문은 출발하는 꼭짓점 - 세 번째 반복문은 도착하는 꼭짓점 N개의 정점과 방향과 가중치 w를 가진 M개의 간선으로 이루어진 방향 그래프가 주어짐. 이때 모든 정점들의 쌍에 대해 A에서 시작하여 B로 도착하는 최단 거리를 구하시오 #include #define INFINITY 999999 int weight[101][101]; int result[101][101]; void floyd(int n) { int i, j, k; for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { if (k == 0) { for (j = 0; j < n; j++).. 2021. 6. 18. 1263 사람 네트워크2 풀이중 연구 단체 사람 네트워크. 영향력 분석 프로그램 그래프의 노드 수 디스트는 노드 아이로부터 노드 제이까지의 최단 거리 2018. 10. 31. 이전 1 다음
