무방향 간선 그래프 만들고 그래프 너비우선탐색(BFS)으로 순회

고안 할 때 아이디어

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 ; iMat[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; iMat[i][j] = -1;         // Mat[0][?] 꼴이나 Mat[?][0] 꼴들은 아예 안쓸거라 -1말고 다른 -값으로 초기화 하는 것도 좋음. 여기선 필요 x
		}
	}
	
	for(i=0; iE[i].endV1 = 0;
		G->E[i].endV2 = 0;
		G->E[i].label = 0;
	}

	i = 0;
	int n1,n2;
	
	while(iV[i].label = 0;
	}


	int* q = (int*)malloc(sizeof(int)*N); 
	int  qsize;
	for(i=0; iV[S].label = 1;

	int ei , opposite;
	
	
	//첫노드에 대한 작업
	//q에 S노드 근처 정점 다 넣고 시작(qsize 갱신) // 이 때 근처 정점들 다 출력하고 visited(=1)로 바꿔준다
	for(i=1; iMat[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; iMat[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; iV[i].k == v1)
			break;
	}
	if(i == N+1){
		printf("-1\n");
		return;
	}
	//노드 2  "
	for(i=1; iV[i].k == v2)
			break;
	}
	if(i == N+1){
		printf("-1\n");
		return;
	}

	// 둘사이에 간선이 없음 --> 간선 생성
	if(g->Mat[v1][v2] == -1)
	{
		//간선에 대한 정보를 넣을 위치 찾기
		for(i=0; iE[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;
	}
	
	

}