그림 의 깊이 우선 스 트 리밍 시퀀스
그림 (graph) 은 데이터 구조 G = (V, E) 이 고 그 중에서 V 는 G 중의 결점 의 유한 한 비공 식 집합 이 며 결점 의 비대 칭 은 변 (edge) 이다.E 는 G 중 변 의 유한 집합 이다.V = {0, 1, 2,.무방 향도 (undirected graph) 는 그림 에서 변 을 대표 하 는 짝 이 무질서 하고 무방 향도 에서 변 (u, v) 과 (v, u) 은 같은 변 을 가리킨다.
입력 변 은 무 방향 그림 을 구성 하고 정점 0 을 기점 으로 하 는 깊이 우선 순 위 를 찾 습 니 다.
첫 번 째 행 위 는 두 개의 정수 n, e 로 그림 의 정점 과 변 수 를 나타 낸다.아래 e 줄 은 줄 마다 두 개의 정 수 를 나타 내 고 한 변 의 출발점, 종점 을 나타 내 며 중복 되 지 않 고 실패 하지 않도록 확보한다.1≤n≤20，0≤e≤190
앞의 n 줄 출력 은 그림 과 인접 하지 않 은 행렬 입 니 다. 마지막 줄 출력 은 정점 0 을 기점 으로 하 는 깊이 우선 순 위 를 옮 겨 다 닙 니 다. 모든 출발점 에 대해 먼저 종점 번호 가 가장 작고 방문 되 지 않 은 한 쪽 을 옮 겨 다 닙 니 다.번호 마다 빈 칸 을 출력 합 니 다.
4 5 0 1 0 3 1 2 1 3 2 3
0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 2 3
#include<cstdio>
#include<iostream>
using namespace std;
int map[21][21];
int used[21];
int n,e;
void dfs(int v,int count)
{
int steak[210],i;
int top=0;
steak[top++]=v;
printf("%d ",v);
used[v]=1;
while(top>0)
{
int x=steak[top-1];
for(i=1;i<n;i++)
{
if(!used[i]&&map[x][i])
{
steak[top++]=i;
printf("%d ",i);
used[i]=1;
count++;
break;
}
}
if(i==n)
top--;
}
if(count<n)
{
for(int i=1;i<n;i++)
if(!used[i])
dfs(i,count);
}
}
int main()
{
// freopen("in.txt","r",stdin);
int x,y;
scanf("%d%d",&n,&e);
for(int i=0;i<e;i++)
{
scanf("%d%d",&x,&y);
map[x][y]=map[y][x]=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d ",map[i][j]);
printf("
");
}
dfs(0,0);
printf("
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
비귀속 이차수(전차, 중차, 후차, 잎 노드의 계산)#pragma once #include<iostream> #include<queue> #include<stack> using namespace std; template<class T> struct BinaryTree...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
