전체 글 썸네일형 리스트형 AOV(Topological sort) 아래의 AOV network에서 task의 작업 순서를 나열하시오. 6 0 2 0 3 1 3 1 4 2 3 2 5 3 5 4 5 입력파일은 뱡향성 그래프의 edge에 대한 정보를 나타낸다. 입력의 첫 번째 줄은 vertex 수를 나타내고, 두 번째 줄 부터는 edge의 정보이다. (출발 정점(vertex)과 도착 정점(vertex)을 나타낸다) 입력파일로 부터 AOV network를 만든다. AOV network에서 task의 작업 순서를 정렬하여 출력한다. #include #include #include enum { FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR }; #define NAME(a) #a #define CATCH(ERROR) do{printf(NAME(ERROR).. 더보기 Dijkstra Dijkstra's algorithm을 사용하여 아래 그래프에서 시작 정점(0)에서 다른 모든 정점으로 가는 최단 경로와 가중치 값(weight value)을 실행의 예와 같이 결과를 출력하시오, 7 12 0 1 7 0 4 3 0 5 10 1 2 4 1 3 10 1 4 2 1 5 6 2 3 2 3 4 11 3 5 9 3 6 4 6 4 5 입력파일의 첫 행은 vertex와 edge의 수를 나타낸다. 다음 행 부터는 정점(vertex) 간선(edge) 가중치 값(weight value) 을 나타낸다. 정점(vertex)과 간선(edge)의 수와 가중치 값(weight value)를 입력 받아 인접 행렬로 그 래프를 표현한다. 시작 정점은 0에서 다른 모든 정점으로 가는 최단 경로의 weight 값을 실행의 .. 더보기 Prim Algorithm 다음과 같이 무방향그래프(undirected graph)에 대하여 prim Algorithm으로 최소비용 신장트리(MST)를 구축하는 과정에서, 정점 선택으로 인해 변화되는 가중치 값 그리고 선택 되는 edge와 edge의 가중치 값을 출력 하고 최소 비용을 구하시오. 7 9 0 1 28 0 5 10 1 2 16 1 6 14 2 3 12 3 4 22 3 6 18 4 5 25 4 6 24 입력파일의 첫 행은 vertex수와 edge의 수를 나타낸다. 다음 행부터는 정점(vertex) 간선(edge) 가중치 값(weight value) 을 나타낸다. 정점(vertex)과 간선(edge)의 수와 가중치 값(weight value)를 입력 받아 그래프를 표현한다. 시작 정점은 0으로 하여 최소 비용 트리를 구한.. 더보기 Kruskal Algorithm 다음과 같이 무방향그래프(undirected graph)에 대하여 Kruskal's Algorithm으로 최소비용 신장트리(MST)를 구축해 나가는 과정을 출력 하시오. 탐색되는 edge를 순서대로 출력하 고, 최소 비용을 구하시오. 7 9 0 1 28 0 5 10 1 2 16 1 6 14 2 3 12 3 4 22 3 6 18 4 5 25 4 6 24 정점(vertex)과 간선(edge)의 수와 가중치 값(weight value)를 입력 받아 그래프를 표현 한다. 최소비용 신장트리(MST)를 구축하는 과정에서 선택되는 edge와 최소비용을 출력하시오. #include #include #include enum { FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR }; #define .. 더보기 Connected Component 입력된 무방향그래프의 connected component를 출력하는 프로그램을 작성하라. 8 10 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 7 6 7 8 7 0 1 0 2 1 3 2 3 4 5 5 6 6 7 #include #include #include enum { FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR }; #define NAME(a) #a #define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false) #define CALLOC(type,data_num,ptr) do{if(!(ptr=(type*)calloc(data_num,sizeof(type)))){CATCH(MEMORY_ALLOCATION.. 더보기 BFS https://kanei-0415.tistory.com/54 DFS 다음과 같이 무방향그래프(undirected graph) 데이터를 입력받아 인접리스트를 만들고 dfs 결과를 출력하는 프로그램을 작성하라. 입력파일의 첫 줄은 정점(vertex) 수와 간선(edge)의 수를 나타냄, 그래 kanei-0415.tistory.com 문제에 대해 dfs 대신 bfs의 결과를 출력하는 프로그램을 작성하라. #include #include #include enum { FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR }; #define NAME(a) #a #define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false) #define CA.. 더보기 DFS 다음과 같이 무방향그래프(undirected graph) 데이터를 입력받아 인접리스트를 만들고 dfs 결과를 출력하는 프로그램을 작성하라. 입력파일의 첫 줄은 정점(vertex) 수와 간선(edge)의 수를 나타냄, 그래프의 정점 인덱스는 0부터 시작됨 8 10 0 1 0 2 1 3 1 4 2 5 2 6 3 7 4 7 5 7 6 7 #include #include #include enum { FILE_OPEN_ERROR, MEMORY_ALLOCATION_ERROR }; #define NAME(a) #a #define CATCH(ERROR) do{printf(NAME(ERROR));exit(0);}while(false) #define CALLOC(type,data_num,ptr) do{if(!(ptr=(t.. 더보기 Adjacency Multilists 다음과 같이 사용자로부터 정보를 입력받아서 무방향그래프(undirected graph)를 Adjacency multilist로 구성하여 각 정점에 부속(속해있는)되는 간선을 출력하는 프로그램 을 작성하라. 4 6 0 1 0 2 0 3 1 2 1 3 2 3 입력파일의 첫 줄은 정점(vertex) 수와 간선(edge)의 수를 나타냄, 그래프의 정점은 0부터 시작됨 하나의 간선 (i, j)을 표현하는 방법 정점과 간선의 수를 입력받음 그래프를 구성하는 간선을 하나씩 입력받으면서 adjacency multilist를 구성함(같은 간선이 두 번 입력되지 않음을 가정함) 각 정점에 대해 부속된 간선(edges incident to a vertex v)을 출력하기 (입력데이터 순서대로 출력, 헤더노드 정점이 먼저 오.. 더보기 이전 1 2 3 4 5 다음
