고안 할 때 아이디어
1. label을 이용해 해당 Vertex가 방문 되었는지(=1) 안되었는지(=0)
2. 큐를 이용해서 깊이레벨이 낮은 부분부터 접근할 수 있게
//BFS(너비우선 탐색) #include#include typedef struct Vertex{ int k; int label; }VERTEX; typedef struct Edge{ int endV1; int endV2; int label; //설계할 때 괜히 만들음. 없어도 됨. }EDGE; // 이거 구조에 대해서 생각할 필요가 있음. 일단은 포인터 형식을 이용하지 않았음 typedef struct Graph{ EDGE* E; VERTEX* V; int** Mat; }GRAPH; void makeEdge(GRAPH* g, int v1, int v2, int M, int N); void BFS(GRAPH* G, int S, int N); void main() { int N, M, S; int i , j ; scanf("%d %d %d", &N, &M, &S); GRAPH *G = (GRAPH*)malloc(sizeof(GRAPH)); G->E = (EDGE*)malloc(sizeof(EDGE)*M); G->V = (VERTEX*)malloc(sizeof(VERTEX)*(N+1)); G->Mat = (int**)malloc(sizeof(int*)*(N+1)); //이차원의 배열을 구현하는 블로그를 보면서 얻은 아이디어 - 같은 논리여도 메모리를 내가 원하는대로 구성하는 것에 따라 달라짐 G->Mat[0] = (int*)malloc(sizeof(int)*(N+1)*(N+1)); for(i=1 ; i Mat[i] = G->Mat[i-1] + (N+1); } // 그래프 초기화 for(i=0; i< N+1; i++) { G->V[i].k = i; G->V[i].label = 0; } for(i=0; i Mat[i][j] = -1; // Mat[0][?] 꼴이나 Mat[?][0] 꼴들은 아예 안쓸거라 -1말고 다른 -값으로 초기화 하는 것도 좋음. 여기선 필요 x } } for(i=0; i E[i].endV1 = 0; G->E[i].endV2 = 0; G->E[i].label = 0; } i = 0; int n1,n2; while(i V[i].label = 0; } int* q = (int*)malloc(sizeof(int)*N); int qsize; for(i=0; i V[S].label = 1; int ei , opposite; //첫노드에 대한 작업 //q에 S노드 근처 정점 다 넣고 시작(qsize 갱신) // 이 때 근처 정점들 다 출력하고 visited(=1)로 바꿔준다 for(i=1; i Mat[S][i] != -1) { //간선에 반대편 노드를 구하는 부분 ei = G->Mat[S][i]; if(G->E[ei].endV1 == S) opposite = G->E[ei].endV2; else opposite = G->E[ei].endV1; //반대편 노드에 대해서 작업 if(G->V[opposite].label == 0) { printf("%d\n",opposite); G->V[opposite].label = 1; q[qsize]= opposite; qsize++; } } } while(qsize != 0) { S = q[0]; //위에 첫노드에 했던 작업을 큐안에서 나온 정점에게 작업 하는 것 // 코드도 같음 for(i=1; i Mat[S][i] != -1) { ei = G->Mat[S][i]; if(G->E[ei].endV1 == S) opposite = G->E[ei].endV2; else opposite = G->E[ei].endV1; if(G->V[opposite].label == 0) { printf("%d\n",opposite); G->V[opposite].label = 1; q[qsize]= opposite; qsize++; } } } //큐 갱신 for(i=0; i V[i].k == v1) break; } if(i == N+1){ printf("-1\n"); return; } //노드 2 " for(i=1; i V[i].k == v2) break; } if(i == N+1){ printf("-1\n"); return; } // 둘사이에 간선이 없음 --> 간선 생성 if(g->Mat[v1][v2] == -1) { //간선에 대한 정보를 넣을 위치 찾기 for(i=0; i E[i].endV1== 0) // 0번 vertex는 존재 하지 않도록 설계되어 있음 break; } //해당 간선에 대한 정보를 업데이트 g->E[i].endV1 = v1; g->E[i].endV2 = v2; //간선과 관련이 있기 때문에 행렬부분도 업데이트 g->Mat[v1][v2] = i; g->Mat[v2][v1] = i; return; } }
'알고리즘' 카테고리의 다른 글
이진 탐색트리_ 탐색, 삽입, 삭제, 전위순회 (0) | 2018.07.10 |
---|---|
최소신장트리 간선의 가중치 출력 - Kruskal으로 간선이 선택됨 (0) | 2018.07.09 |
인접행렬을 이용한 그래프 구현하기(알고리즘_교보문고_국형준 참고) (0) | 2018.07.05 |
배열로 구현한 개방조사법 해시테이블(선형조사법으로 충돌 방지) (0) | 2018.07.05 |
최대힙을 이용해서 제자리 정렬하기 (0) | 2018.06.29 |