Courses

그래프 이론

BFS - 폭 넓은 산책

Module: BFS - 폭 넓은 산책

Problem

2/6

BFS: 시작(Python)

Theory Click to read/hide

BFS(Breadth-First Search)는 단순 알고리즘과 고급 알고리즘 모두에서 매우 자주 사용되는 그래프 순회 방법입니다. Breadth-First Search는 소스 노드에서 시작하여 점진적으로 멀어지는 그래프의 개별 수준을 통해 작동합니다. 이것은 애니메이션에서 명확하게 보여집니다.

간단한 BFS를 작성하려면 처음부터 끝까지 가져갈 수 있는 데이터 구조인 대기열로 작업할 수 있어야 하며 그래프를 다음 형식으로 저장할 수 있어야 합니다. 인접 목록의.

알고리즘에 대한 공식적인 설명

1) 검색이 시작되는 꼭지점의 번호를 초기 빈 큐에 배치합니다.
2) 큐의 시작 부분에서 정점 U를 추출하고 별도의 배열에서 사용된 것으로 표시합니다.
3) 대기열의 끝에서 정점 U의 가장자리를 사용하여 도달할 수 있고 아직 표시되지 않은 모든 정점을 추가합니다.
4) Queue가 비어 있으면 연결된 그래프의 모든 노드를 스캔한 것이며 그렇지 않으면 2단계로 돌아갑니다.

작업의 어려움
최악의 경우 알고리즘은 그래프의 모든 노드를 방문하므로 그래프를 인접 리스트 형태로 저장할 때 알고리즘의 시간 복잡도는 O(|V| + |E|)이며, 여기서 V는 집합 그래프의 꼭짓점의 집합이고 E는 가장자리 집합입니다.
즉, 알고리즘은 모서리 수 + 정점 수에 대해 최악의 경우에 작동합니다.

Problem

일부 마을은 도로로 연결되어 있으며 방향이 없는 그래프로 나타낼 수 있습니다. 이 그래프의 정점은 마을이고 가장자리는 마을 사이의 도로입니다(그래프에는 주기가 포함될 수 있음). 마을에서 S artel 행상인. 매일 아침, 행상인은 작은 잡화를 팔기 위해 아직 방문하지 않은 마을과 현재 마을에서 길이 있는 마을로 이동합니다. 행상인의 아텔은 항상 그룹으로 나뉘어 현재 마을에서 도로가 있는 모든 마을을 하루에 돌아다닐 수 있습니다.
행상인들이 모든 마을을 방문하는 데 며칠이 걸립니까? 문제에 대한 답을 반환하는 \(bfs()\) 함수를 작성하세요.

입력
첫 번째 줄에는 3개의 정수 n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 마을 수, 마을 사이의 도로 수, 행상인 갱단이 기반을 두고 있는 마을 수. ;다음

m 줄에는 각 u, v(\(1 < = u, v <= n\ )) - 도로가 있는 두 마을의 수. 마을은 1로 인덱싱됩니다.



출판물

하나의 숫자를 출력하세요 - 행상인이 모든 마을을 방문하는 데 며칠이 걸리는지.



 
 

예


<헤드>

<일>#
<몸>

                                      
                                       1000
                                             ms
                                        
 
                                            32 Mb
                                         
   
                    Rules for program design and list of errors in automatic problem checking
                 
                                       
                                   Teacher commentary 
                        
                            
                        
                              

                Insert the missing code snippets

                    Python
      

        
                    
        


        
        
		

                    
			

입력
출력


1
6 7 1

1 2

15 

23

5 4

34

36

4 6
4



                              
            
       
                               
                                  
                           





            
 

   


   

  
                              
           

    

				
					Write the program below
				

					
                                    
                                    def bfs():            

                                
				

					
                                    
                                    

                                
				

					
                                    
                                    n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

입력	출력
1	6 7 1 1 2 15 23 5 4 34 36 4 6	4

Write the program below
def bfs():

n, m, s = map(int, input().split()) s -= 1 used = [False] * n # True, если были в вершине i tm = [0] * n # tm[i] - день, когда в деревню i пришла артель коробейников g = [] # список смежности for i in range(n): g.append([]) for i in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) print(bfs())


          
           
         
            
               
               
                      
                  
               
          
            
         
               
                    
                        Program check result
                            
                            
                              
                              
                            
To check the solution of the problem, you need to register or log in!

Courses 그래프 이론 BFS - 폭 넓은 산책

Module: BFS - 폭 넓은 산책

2/6

BFS: 시작(Python)

Theory Click to read/hide

Problem

예

Teacher commentary

Insert the missing code snippets

Program check result

To check the solution of the problem, you need to register or log in!

Courses

그래프 이론

BFS - 폭 넓은 산책