Untitled
Never
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #define MAX_SIZE 5 // 구현 int edge_num(int adj_matrix[MAX_SIZE][MAX_SIZE]) { int ret=0; // 리턴할 변수 생성 for(int i=0; i<MAX_SIZE; ++i){ for(int j=0; j<MAX_SIZE; ++j){ if(adj_matrix[i][j]==1) ret++; // 간선 연결 정보의 개수를 ret에 담음. } } return ret/2; // 간선 연결 정보의 개수 / 2 를 리턴. } // 구현 void complete_graph(int adj_matrix[MAX_SIZE][MAX_SIZE]) { for(int i=0; i<MAX_SIZE; ++i){ int cnt=0; // i정점의 간선 연결 정보의 개수를 cnt에 저장. for(int j=0; j<MAX_SIZE; ++j){ if(i==j) continue; // i==j이면 continue if(adj_matrix[i][j]==1) cnt++; // 간선 연결 정보가 있으면 cnt에 +1 } if(cnt!=MAX_SIZE-1){ // i 정점이 다른 모든 정점과 연결되어있지 않으면 printf("Non-complete graph\n"); return; // 출력 후 함수 종료 } } printf("complete graph\n"); // 모든 정점이 각각 다른 모든 정점과 연결되어 있음. } // 구현 void check_simple_path(int adj_matrix[MAX_SIZE][MAX_SIZE], char path[]) { bool flag=true; // simple path 여부를 flag에 저장. int visited[MAX_SIZE]={0,}; // 정점 방문 여부를 visited에 저장. visited[path[0]-'0']=1; // 가장 처음 방문 정점 여부를 1로 채움. for(int i=1; path[i]!='\0'; ++i){ // path 끝에 도달할 때 까지 int prev=path[i-1]-'0'; // 이전 방문 정점을 prev에 저장. int cur =path[i]-'0'; // 현재 방문 정점을 cur에 저장. if(adj_matrix[prev][cur]!=1) flag=false; // prev에서 cur로 갈 수 없으면 실패. if(visited[cur]==1) flag=false; // 이미 cur을 방문했었다면 실패 visited[cur]=1; // cur 방문 여부를 1로 채움. } if(flag) printf("Yes\n"); // simple path 여부에 따라 결과 출력. else printf("No\n"); } int dfs(int x, int visited[MAX_SIZE], int adj_matrix[MAX_SIZE][MAX_SIZE]){ // get_largest_connected_component()에 필요한 dfs 함수. visited[x]=1; // 현재 정점 방문했다고 기록. int ret=0; // 현재 정점을 포함해서 dfs로 방문한 정점의 개수를 ret에 저장. for(int i=0; i<MAX_SIZE; ++i){ // 현재 정점 x에 대해 간선 정보 탐색. if(x==i) continue; // x와 i가 같으면 continue if(adj_matrix[x][i]==1 && !visited[i]){ // 간선 연결 정보가 있고, 아직 방문하지 않은 정점이면 int temp=dfs(i, visited, adj_matrix); // temp에 dfs로 방문한 정점의 개수를 저장. ret+=temp; // ret에 temp 추가. } } return ret+1; // 현재 정점도 포함시켜줘야 하므로 ret에 +1해준 값을 리턴. } // 구현 int get_largest_connected_component(int adj_matrix[MAX_SIZE][MAX_SIZE]) { int ret=0; // 가장 큰 연결요소의 정점의 수를 담는 변수. for(int i=0; i<MAX_SIZE; ++i){ // 모든 정점에 대해 int visited[MAX_SIZE]={0,}; // 정점 방문 여부를 체크하는 visited배열 선언 및 초기화. int temp=dfs(i, visited, adj_matrix); // temp에 i정점에 연결된 연결요소의 정점의 수를 저장. if(ret<temp) ret=temp; // temp가 최댓값이라면, ret 갱신 } return ret; // ret 리턴. } int main() { int G1[MAX_SIZE][MAX_SIZE] = { { 0, 1, 1, 0, 1 }, { 1, 0, 1, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; int G2[MAX_SIZE][MAX_SIZE] = { { 0, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0 } }; int G3[MAX_SIZE][MAX_SIZE] = { { 0, 1, 0, 0, 1 }, { 1, 0, 1, 0, 0 }, { 0, 1, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 0, 1, 0 } }; int G4[MAX_SIZE][MAX_SIZE] = { { 0, 1, 0, 0, 0 }, { 1, 0, 1, 0, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 1, 0 } }; int G5[MAX_SIZE][MAX_SIZE] = { { 0, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 1, 1, 1, 0 } }; char path[] = "0123"; printf("1. 그래프의 총 간선의 수: %d \n", edge_num(G1)); printf("\n"); printf("2. Non-complete graph or complete graph: "); complete_graph(G5); printf("\n"); printf("3. A simple path?(Yes/No): "); check_simple_path(G3, path); printf("\n"); printf("4. 가장 큰 연결요소의 정점의 수: %d", get_largest_connected_component(G4)); printf("\n\n"); return 0; }