알고리즘 7 - 6: 그림 의 옮 겨 다 니 기 - 넓이 우선 검색 (c 언어)
제목 설명
트 리 와 같은 차원 으로 옮 겨 다 니 는 과정 을 우선 검색 합 니 다.그 과정 은 그림 속 의 특정한 정점 v 에서 출발 하여 v 를 방문 한 후에 v 의 방문 되 지 않 은 각 인접 점 을 차례대로 방문 한 다음 에 각각 이러한 인접 점 에서 출발 하여 그들의 인접 점 을 차례대로 방문 하고 '먼저 방문 되 는 정점 의 인접 점' 을 '나중에 방문 되 는 정점 의 인접 점' 보다 먼저 방문 하 게 한다.그림 에 있 는 모든 방문 한 정점 의 인접 점 이 접근 할 때 까지.만약 이 그림 에 정점 이 방문 되 지 않 았 다 면, 다른 그림 에서 방문 되 지 않 은 정점 을 시작 점 으로 선택 하 십시오.그림 의 모든 정점 이 방문 할 때 까지 상기 과정 을 반복 합 니 다.
그 알고리즘 은 다음 과 같이 설명 할 수 있다.
이 문제 에서 그림 이 없 는 인접 행렬 (즉 배열 표시) 을 읽 고 방향 이 없 는 그림 을 만 들 고 상기 설명 에서 의 알고리즘 에 따라 모든 정점 을 옮 겨 다 니 며 출력 이 정점 을 옮 겨 다 니 는 순서 입 니 다.
입력 설명
입력 한 첫 줄 은 정수 n 을 포함 하고 그림 에 n 개의 정점 이 있 음 을 나타 낸다.그 중 n 은 50 을 넘 지 않 는 다.
이후 n 줄 마다 n 개의 빈 칸 으로 구 분 된 정수 0 또는 1 이 있 고 i 줄 의 j 번 째 0 또는 1 에 대해 1 은 i 번 째 정점 과 j 번 째 정점 이 직접 연결 되 어 있 음 을 나타 내 며 0 은 직접 연결 되 지 않 았 음 을 나타 낸다.i 와 j 가 같 을 때 대응 하 는 정 수 는 0 이다.
입력 은 인접 행렬 이 대칭 행렬 임 을 보증 합 니 다. 즉, 입력 한 그림 은 반드시 방향 이 없 는 그림 입 니 다.
출력 설명
n 개의 정 수 를 포함 하 는 줄 만 있 습 니 다. 제목 설명 에 있 는 넓 은 범위 에 따라 전체 그림 의 방문 정점 순 서 를 우선 옮 겨 다 니 는 것 을 의미 합 니 다.정수 마다 빈 칸 을 출력 하고 줄 끝 출력 줄 바 꾸 기 에 주의 하 십시오.
샘플 입력 4 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0
출력 샘플 0, 3, 1, 2
//
#include
#include
#include
int n, k, l;
int a[55][55];
int b[55];
int ans[55];
void DFS(int x)
{
int i, j;
if(b[x] == 1)
{
ans[k++] = x;
b[x] = 0;
}
if(k == n)
{
for(i = 0; i < n; i++)
{
printf("%d ", ans[i]);
}
printf("
");
exit(0);
}
for(i = 0; i < n; i++)
{
if(a[x][i] == 1 && b[i] == 1)
{
ans[k++] = i;
b[i] = 0;
}
}
DFS(ans[++l]);
return ;
}
int main()
{
int i, j;
scanf("%d", &n);
{
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
}
k = 0;
l = 0;
for(j = 0; j < n; j++)
b[j] = 1;
for(i = 0; i < n; i++)
{
if(b[i] == 1)
{
DFS(i);
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
