데이터 구조 상황에 따라 보다 효율적으로 액세스할 수 있도록 데이터를 구성하는 방법입니다. 데이터 구조는 프로그램이 구축되는 모든 프로그래밍 언어의 기본입니다. Python은 다른 프로그래밍 언어에 비해 더 간단한 방법으로 이러한 데이터 구조의 기본을 배우는 데 도움이 됩니다.

이 기사에서는 Python 프로그래밍 언어의 데이터 구조와 이것이 목록 튜플, 사전 등과 같은 특정 내장 데이터 구조 및 트리, 그래프 등과 같은 일부 고급 데이터 구조와 어떻게 관련되어 있는지 논의합니다.

기울기

Python 목록은 정렬된 데이터 모음인 다른 언어로 선언된 배열과 같습니다. 목록의 항목이 동일한 유형일 필요가 없으므로 매우 유연합니다.

Python List의 구현은 C++의 벡터 또는 JAVA의 ArrayList와 유사합니다. 비용이 많이 드는 작업은 모든 요소를 ​​이동해야 하기 때문에 목록의 시작 부분에서 요소를 삽입하거나 삭제하는 것입니다. 사전 할당된 메모리가 가득 차면 목록 끝에 삽입하고 삭제하는 것도 비용이 많이 들 수 있습니다.

아래와 같이 Python으로 목록을 만들 수 있습니다.

예: Python 목록 생성

파이썬3

List> => [> 1> ,> 2> ,> 3> ,> 'GFG'> ,> 2.3> ]> print> (> List> )>

산출

[1, 2, 3, 'GFG', 2.3] 

목록 요소는 할당된 인덱스로 액세스할 수 있습니다. 목록의 Python 시작 인덱스에서 시퀀스는 0이고 끝 인덱스는 (N 요소가 있는 경우) N-1입니다.

예: Python 목록 작업

파이썬3

# Creating a List with> # the use of multiple values> List> => [> 'Geeks'> ,> 'For'> ,> 'Geeks'> ]> print> (> ' List containing multiple values: '> )> print> (> List> )> # Creating a Multi-Dimensional List> # (By Nesting a list inside a List)> List2> => [[> 'Geeks'> ,> 'For'> ], [> 'Geeks'> ]]> print> (> ' Multi-Dimensional List: '> )> print> (List2)> # accessing a element from the> # list using index number> print> (> 'Accessing element from the list'> )> print> (> List> [> 0> ])> print> (> List> [> 2> ])> # accessing a element using> # negative indexing> print> (> 'Accessing element using negative indexing'> )> > # print the last element of list> print> (> List> [> -> 1> ])> > # print the third last element of list> print> (> List> [> -> 3> ])>

산출

List containing multiple values: ['Geeks', 'For', 'Geeks'] Multi-Dimensional List: [['Geeks', 'For'], ['Geeks']] Accessing element from the list Geeks Geeks Accessing element using negative indexing Geeks Geeks 

사전

파이썬 사전 O(1)의 시간 복잡도를 갖는 다른 언어의 해시 테이블과 같습니다. 이는 맵과 같은 데이터 값을 저장하는 데 사용되는 정렬되지 않은 데이터 값 모음입니다. 이는 요소로 단일 값만 보유하는 다른 데이터 유형과 달리 키:값 쌍을 보유합니다. 보다 최적화하기 위해 사전에 키-값을 제공합니다.

Python 사전의 색인화는 키의 도움으로 수행됩니다. 이는 해시 가능한 유형, 즉 문자열, 숫자, 튜플 등과 같이 결코 변경될 수 없는 객체입니다. 중괄호({})를 사용하여 사전을 만들 수 있습니다. 사전 이해 .

예: Python 사전 작업

파이썬3

# Creating a Dictionary> Dict> => {> 'Name'> :> 'Geeks'> ,> 1> : [> 1> ,> 2> ,> 3> ,> 4> ]}> print> (> 'Creating Dictionary: '> )> print> (> Dict> )> # accessing a element using key> print> (> 'Accessing a element using key:'> )> print> (> Dict> [> 'Name'> ])> # accessing a element using get()> # method> print> (> 'Accessing a element using get:'> )> print> (> Dict> .get(> 1> ))> # creation using Dictionary comprehension> myDict> => {x: x> *> *> 2> for> x> in> [> 1> ,> 2> ,> 3> ,> 4> ,> 5> ]}> print> (myDict)>

산출

Creating Dictionary: {'Name': 'Geeks', 1: [1, 2, 3, 4]} Accessing a element using key: Geeks Accessing a element using get: [1, 2, 3, 4] {1: 1, 2: 4, 3: 9, 4: 16, 5: 25} 

튜플

파이썬 튜플 목록과 매우 유사한 Python 객체의 모음이지만 튜플은 본질적으로 변경할 수 없습니다. 즉, 튜플의 요소는 일단 생성되면 추가하거나 제거할 수 없습니다. 리스트와 마찬가지로 튜플에도 다양한 유형의 요소가 포함될 수 있습니다.

Python에서 튜플은 데이터 시퀀스 그룹화를 위해 괄호를 사용하거나 사용하지 않고 '쉼표'로 구분된 값 시퀀스를 배치하여 생성됩니다.

메모: 튜플은 단일 요소로 생성할 수도 있지만 약간 까다롭습니다. 괄호 안에 요소가 하나 있는 것만으로는 충분하지 않습니다. 튜플로 만들려면 뒤에 '쉼표'가 있어야 합니다.

예: Python 튜플 작업

파이썬3

# Creating a Tuple with> # the use of Strings> Tuple> => (> 'Geeks'> ,> 'For'> )> print> (> ' Tuple with the use of String: '> )> print> (> Tuple> )> > # Creating a Tuple with> # the use of list> list1> => [> 1> ,> 2> ,> 4> ,> 5> ,> 6> ]> print> (> ' Tuple using List: '> )> Tuple> => tuple> (list1)> # Accessing element using indexing> print> (> 'First element of tuple'> )> print> (> Tuple> [> 0> ])> # Accessing element from last> # negative indexing> print> (> ' Last element of tuple'> )> print> (> Tuple> [> -> 1> ])> > print> (> ' Third last element of tuple'> )> print> (> Tuple> [> -> 3> ])>

산출

Tuple with the use of String: ('Geeks', 'For') Tuple using List: First element of tuple 1 Last element of tuple 6 Third last element of tuple 4 

세트

파이썬 세트 변경 가능하고 중복 요소를 허용하지 않는 정렬되지 않은 데이터 모음입니다. 세트는 기본적으로 멤버십 테스트를 포함하고 중복 항목을 제거하는 데 사용됩니다. 여기에 사용된 데이터 구조는 평균 O(1)에서 삽입, 삭제 및 순회를 수행하는 인기 있는 기술인 해싱(Hashing)입니다.

동일한 인덱스 위치에 여러 값이 있는 경우 값이 해당 인덱스 위치에 추가되어 연결 목록을 형성합니다. 에서 CPython 세트는 더미 변수가 있는 사전을 사용하여 구현됩니다. 여기서 핵심은 시간 복잡도에 대해 더 큰 최적화로 설정된 멤버입니다.

구현 설정:

단일 HashTable에 대한 수많은 작업으로 설정:

예: Python 집합 작업

파이썬3

# Creating a Set with> # a mixed type of values> # (Having numbers and strings)> Set> => set> ([> 1> ,> 2> ,> 'Geeks'> ,> 4> ,> 'For'> ,> 6> ,> 'Geeks'> ])> print> (> ' Set with the use of Mixed Values'> )> print> (> Set> )> # Accessing element using> # for loop> print> (> ' Elements of set: '> )> for> i> in> Set> :> > print> (i, end> => ' '> )> print> ()> # Checking the element> # using in keyword> print> (> 'Geeks'> in> Set> )>

산출

Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True 

냉동 세트

Python의 고정 세트는 고정 세트 또는 적용되는 세트에 영향을 주지 않고 결과를 생성하는 메서드와 연산자만 지원하는 불변 객체입니다. 세트의 요소는 언제든지 수정될 수 있지만 고정된 세트의 요소는 생성 후에도 동일하게 유지됩니다.

매개변수가 전달되지 않으면 빈 Frozenset이 반환됩니다.

파이썬3

# Same as {'a', 'b','c'}> normal_set> => set> ([> 'a'> ,> 'b'> ,> 'c'> ])> print> (> 'Normal Set'> )> print> (normal_set)> # A frozen set> frozen_set> => frozenset> ([> 'e'> ,> 'f'> ,> 'g'> ])> print> (> ' Frozen Set'> )> print> (frozen_set)> # Uncommenting below line would cause error as> # we are trying to add element to a frozen set> # frozen_set.add('h')>

산출

Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'}) 

끈

Python 문자열은 유니코드 문자를 나타내는 바이트 배열입니다. 간단히 말해서 문자열은 불변의 문자 배열입니다. Python에는 문자 데이터 유형이 없습니다. 단일 문자는 단순히 길이가 1인 문자열입니다.

메모: 문자열은 변경할 수 없으므로 문자열을 수정하면 새 복사본이 생성됩니다.

예: Python 문자열 작업

파이썬3

String> => 'Welcome to GeeksForGeeks'> print> (> 'Creating String: '> )> print> (String)> > # Printing First character> print> (> ' First character of String is: '> )> print> (String[> 0> ])> > # Printing Last character> print> (> ' Last character of String is: '> )> print> (String[> -> 1> ])>

산출

Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s 

바이테어레이

Python Bytearray는 0 <= x < 256 범위의 가변 정수 시퀀스를 제공합니다.

예: Python Bytearray 작업

파이썬3

# Creating bytearray> a> => bytearray((> 12> ,> 8> ,> 25> ,> 2> ))> print> (> 'Creating Bytearray:'> )> print> (a)> # accessing elements> print> (> ' Accessing Elements:'> , a[> 1> ])> # modifying elements> a[> 1> ]> => 3> print> (> ' After Modifying:'> )> print> (a)> # Appending elements> a.append(> 30> )> print> (> ' After Adding Elements:'> )> print> (a)>

산출

Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e') 

지금까지 우리는 핵심 Python에 내장된 모든 데이터 구조를 연구했습니다. 이제 Python에 대해 더 깊이 알아보고 많은 경우에 유용하며 위에 정의된 함수보다 더 많은 기능을 제공하는 일부 컨테이너를 제공하는 컬렉션 모듈을 살펴보겠습니다.

컬렉션 모듈

내장 데이터 유형의 기능을 개선하기 위해 Python 컬렉션 모듈이 도입되었습니다. 다양한 컨테이너를 제공합니다. 각각을 자세히 살펴보겠습니다.

카운터

카운터는 사전의 하위 클래스입니다. 키는 반복 가능 항목의 요소를 나타내고 값은 반복 가능 항목의 해당 요소 수를 나타내는 순서가 지정되지 않은 사전 형식으로 반복 가능 항목의 요소 수를 유지하는 데 사용됩니다. 이는 다른 언어의 가방 또는 다중 집합과 동일합니다.

예: Python 카운터 작업

파이썬3

from> collections> import> Counter> > # With sequence of items> print> (Counter([> 'B'> ,> 'B'> ,> 'A'> ,> 'B'> ,> 'C'> ,> 'A'> ,> 'B'> ,> 'B'> ,> 'A'> ,> 'C'> ]))> > # with dictionary> count> => Counter({> 'A'> :> 3> ,> 'B'> :> 5> ,> 'C'> :> 2> })> print> (count)> count.update([> 'A'> ,> 1> ])> print> (count)>

산출

Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1}) 

OrderedDict

안 OrderedDict 역시 사전의 하위 클래스이지만 사전과 달리 키가 삽입된 순서를 기억합니다.

예: Python OrderedDict 작업

파이썬3

from> collections> import> OrderedDict> print> (> 'Before deleting: '> )> od> => OrderedDict()> od[> 'a'> ]> => 1> od[> 'b'> ]> => 2> od[> 'c'> ]> => 3> od[> 'd'> ]> => 4> for> key, value> in> od.items():> > print> (key, value)> print> (> ' After deleting: '> )> od.pop(> 'c'> )> for> key, value> in> od.items():> > print> (key, value)> print> (> ' After re-inserting: '> )> od[> 'c'> ]> => 3> for> key, value> in> od.items():> > print> (key, value)>

산출

Before deleting: a 1 b 2 c 3 d 4 After deleting: a 1 b 2 d 4 After re-inserting: a 1 b 2 d 4 c 3 

기본사전

기본사전 존재하지 않고 KeyError를 발생시키지 않는 키에 대한 일부 기본값을 제공하는 데 사용됩니다. 해당 개체는 데이터 유형을 인수로 전달하여 DefaultDict() 메서드를 사용하여 초기화할 수 있습니다.

메모: default_factory는 생성된 사전의 기본값을 제공하는 함수입니다. 이 매개변수가 없으면 KeyError가 발생합니다.

예: Python DefaultDict 작업

파이썬3

from> collections> import> defaultdict> > # Defining the dict> d> => defaultdict(> int> )> > L> => [> 1> ,> 2> ,> 3> ,> 4> ,> 2> ,> 4> ,> 1> ,> 2> ]> > # Iterate through the list> # for keeping the count> for> i> in> L:> > > # The default value is 0> > # so there is no need to> > # enter the key first> > d[i]> +> => 1> > print> (d)>

산출

defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2}) 

체인맵

ChainMap은 많은 사전을 단일 단위로 캡슐화하고 사전 목록을 반환합니다. 키를 찾아야 할 경우 키를 찾을 때까지 모든 사전을 하나씩 검색합니다.

예: Python ChainMap 작업

파이썬3

from> collections> import> ChainMap> > > d1> => {> 'a'> :> 1> ,> 'b'> :> 2> }> d2> => {> 'c'> :> 3> ,> 'd'> :> 4> }> d3> => {> 'e'> :> 5> ,> 'f'> :> 6> }> > # Defining the chainmap> c> => ChainMap(d1, d2, d3)> print> (c)> print> (c[> 'a'> ])> print> (c[> 'g'> ])>

산출

ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1 

KeyError: 'g' 

NamedTuple

ㅏ NamedTuple 일반 튜플에는 없는 각 위치의 이름이 포함된 튜플 객체를 반환합니다. 예를 들어, 첫 번째 요소가 fname을 나타내고, 두 번째 요소가 lname을 나타내고, 세 번째 요소가 DOB를 나타내는 학생이라는 이름의 튜플을 생각해 보세요. 인덱스 위치를 기억하는 대신 fname을 호출한다고 가정하면 실제로 fname 인수를 사용하여 요소를 호출할 수 있습니다. 그러면 튜플 요소에 액세스하는 것이 정말 쉬울 것입니다. 이 기능은 NamedTuple에서 제공됩니다.

예: Python NamedTuple 작업

파이썬3

from> collections> import> namedtuple> > # Declaring namedtuple()> Student> => namedtuple(> 'Student'> ,[> 'name'> ,> 'age'> ,> 'DOB'> ])> > # Adding values> S> => Student(> 'Nandini'> ,> '19'> ,> '2541997'> )> > # Access using index> print> (> 'The Student age using index is : '> ,end> => '')> print> (S[> 1> ])> > # Access using name> print> (> 'The Student name using keyname is : '> ,end> => '')> print> (S.name)>

산출

The Student age using index is : 19 The Student name using keyname is : Nandini 

무엇에 대해서

Deque(이중 종료 대기열) 컨테이너 양쪽에서 더 빠른 추가 및 팝 작업을 위해 최적화된 목록입니다. O(n) 시간 복잡도를 갖는 목록과 비교하여 추가 및 팝 작업에 O(1) 시간 복잡도를 제공합니다.

Python Deque는 이중 연결 목록을 사용하여 구현되므로 요소에 무작위로 액세스하는 성능은 O(n)입니다.

예: Python Deque 작업

파이썬3

# importing 'collections' for deque operations> import> collections> # initializing deque> de> => collections.deque([> 1> ,> 2> ,> 3> ])> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(> 4> )> # printing modified deque> print> (> 'The deque after appending at right is : '> )> print> (de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(> 6> )> # printing modified deque> print> (> 'The deque after appending at left is : '> )> print> (de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print> (> 'The deque after deleting from right is : '> )> print> (de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print> (> 'The deque after deleting from left is : '> )> print> (de)>

산출

The deque after appending at right is : deque([1, 2, 3, 4]) The deque after appending at left is : deque([6, 1, 2, 3, 4]) The deque after deleting from right is : deque([6, 1, 2, 3]) The deque after deleting from left is : deque([1, 2, 3]) 

사용자 사전

UserDict는 사전 객체 주위의 래퍼 역할을 하는 사전과 유사한 컨테이너입니다. 이 컨테이너는 누군가 수정되거나 새로운 기능을 사용하여 자신만의 사전을 생성하려고 할 때 사용됩니다.

예: Python UserDict

파이썬3

from> collections> import> UserDict> # Creating a Dictionary where> # deletion is not allowed> class> MyDict(UserDict):> > > # Function to stop deletion> > # from dictionary> > def> __del__(> self> ):> > raise> RuntimeError(> 'Deletion not allowed'> )> > > # Function to stop pop from> > # dictionary> > def> pop(> self> , s> => None> ):> > raise> RuntimeError(> 'Deletion not allowed'> )> > > # Function to stop popitem> > # from Dictionary> > def> popitem(> self> , s> => None> ):> > raise> RuntimeError(> 'Deletion not allowed'> )> > # Driver's code> d> => MyDict({> 'a'> :> 1> ,> > 'b'> :> 2> ,> > 'c'> :> 3> })> print> (> 'Original Dictionary'> )> print> (d)> d.pop(> 1> )>

산출

Original Dictionary {'a': 1, 'b': 2, 'c': 3} 

RuntimeError: Deletion not allowed 

사용자 목록

UserList는 목록 개체 주위의 래퍼 역할을 하는 목록과 유사한 컨테이너입니다. 이는 일부 수정되거나 추가된 기능을 사용하여 자신만의 목록을 생성하려는 경우에 유용합니다.

예: Python 사용자 목록

파이썬3

# Python program to demonstrate> # userlist> from> collections> import> UserList> # Creating a List where> # deletion is not allowed> class> MyList(UserList):> > > # Function to stop deletion> > # from List> > def> remove(> self> , s> => None> ):> > raise> RuntimeError(> 'Deletion not allowed'> )> > > # Function to stop pop from> > # List> > def> pop(> self> , s> => None> ):> > raise> RuntimeError(> 'Deletion not allowed'> )> > # Driver's code> L> => MyList([> 1> ,> 2> ,> 3> ,> 4> ])> print> (> 'Original List'> )> print> (L)> # Inserting to List'> L.append(> 5> )> print> (> 'After Insertion'> )> print> (L)> # Deleting From List> L.remove()>

산출

Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5] 

RuntimeError: Deletion not allowed 

사용자 문자열

UserString은 문자열과 유사한 컨테이너이며 UserDict 및 UserList와 마찬가지로 문자열 개체 주위의 래퍼 역할을 합니다. 누군가 수정되거나 추가된 기능을 사용하여 자신만의 문자열을 만들고 싶을 때 사용됩니다.

예: Python 사용자 문자열

파이썬3

from> collections> import> UserString> # Creating a Mutable String> class> Mystring(UserString):> > > # Function to append to> > # string> > def> append(> self> , s):> > self> .data> +> => s> > > # Function to remove from> > # string> > def> remove(> self> , s):> > self> .data> => self> .data.replace(s, '')> > # Driver's code> s1> => Mystring(> 'Geeks'> )> print> (> 'Original String:'> , s1.data)> # Appending to string> s1.append(> 's'> )> print> (> 'String After Appending:'> , s1.data)> # Removing from string> s1.remove(> 'e'> )> print> (> 'String after Removing:'> , s1.data)>

산출

Original String: Geeks String After Appending: Geekss String after Removing: Gkss 

이제 모든 데이터 구조를 공부한 후 Python 언어에서 사용할 수 있는 스택, 큐, 그래프, 연결 목록 등과 같은 몇 가지 고급 데이터 구조를 살펴보겠습니다.

연결리스트

연결된 목록은 요소가 인접한 메모리 위치에 저장되지 않는 선형 데이터 구조입니다. 연결된 목록의 요소는 아래 이미지와 같이 포인터를 사용하여 연결됩니다.

연결리스트는 연결리스트의 첫 번째 노드를 가리키는 포인터로 표현됩니다. 첫 번째 노드를 헤드라고 합니다. 연결된 목록이 비어 있으면 헤드 값은 NULL입니다. 목록의 각 노드는 최소한 두 부분으로 구성됩니다.

• 데이터
• 다음 노드에 대한 포인터(또는 참조)

예: Python에서 연결 목록 정의

파이썬3

# Node class> class> Node:> > # Function to initialize the node object> > def> __init__(> self> , data):> > self> .data> => data> # Assign data> > self> .> next> => None> # Initialize> > # next as null> # Linked List class> class> LinkedList:> > > # Function to initialize the Linked> > # List object> > def> __init__(> self> ):> > self> .head> => None>

3개의 노드로 구성된 간단한 연결리스트를 만들어 보겠습니다.

파이썬3

# A simple Python program to introduce a linked list> # Node class> class> Node:> > # Function to initialise the node object> > def> __init__(> self> , data):> > self> .data> => data> # Assign data> > self> .> next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> > # Function to initialize head> > def> __init__(> self> ):> > self> .head> => None> # Code execution starts here> if> __name__> => => '__main__'> :> > # Start with the empty list> > list> => LinkedList()> > list> .head> => Node(> 1> )> > second> => Node(> 2> )> > third> => Node(> 3> )> > '''> > Three nodes have been created.> > We have references to these three blocks as head,> > second and third> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | None | | 2 | None | | 3 | None |> > +----+------+ +----+------+ +----+------+> > '''> > list> .head.> next> => second;> # Link first node with second> > '''> > Now next of first Node refers to second. So they> > both are linked.> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | o-------->| 2 | null | | 3 | 널 |> > +----+------+ +----+------+ +----+------+> > '''> > second.> next> => third;> # Link second node with the third node> > '''> > Now next of second Node refers to third. So all three> > nodes are linked.> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | o-------->| 2 | 아 -------->| 3 | 널 |> > +----+------+ +----+------+ +----+------+> > '''>

연결리스트 순회

이전 프로그램에서는 세 개의 노드로 구성된 간단한 연결 목록을 만들었습니다. 생성된 목록을 순회하여 각 노드의 데이터를 인쇄해 보겠습니다. 순회를 위해 주어진 목록을 인쇄하는 범용 함수 printList()를 작성해 보겠습니다.

파이썬3

# A simple Python program for traversal of a linked list> # Node class> class> Node:> > # Function to initialise the node object> > def> __init__(> self> , data):> > self> .data> => data> # Assign data> > self> .> next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> > # Function to initialize head> > def> __init__(> self> ):> > self> .head> => None> > # This function prints contents of linked list> > # starting from head> > def> printList(> self> ):> > temp> => self> .head> > while> (temp):> > print> (temp.data)> > temp> => temp.> next> # Code execution starts here> if> __name__> => => '__main__'> :> > # Start with the empty list> > list> => LinkedList()> > list> .head> => Node(> 1> )> > second> => Node(> 2> )> > third> => Node(> 3> )> > list> .head.> next> => second;> # Link first node with second> > second.> next> => third;> # Link second node with the third node> > list> .printList()>

산출

1 2 3 

스택

ㅏ 스택 LIFO(후입선출) 또는 FILO(선입선출) 방식으로 항목을 저장하는 선형 데이터 구조입니다. 스택에서는 한쪽 끝에 새 요소가 추가되고 해당 끝에서만 요소가 제거됩니다. 삽입 및 삭제 작업을 흔히 푸시(Push) 및 팝(Pop)이라고 합니다.

스택과 관련된 기능은 다음과 같습니다.

empty() – 스택이 비어 있는지 여부를 반환합니다. – 시간 복잡도: O(1) size() – 스택 크기를 반환합니다. – 시간 복잡도: O(1) top() – 스택의 최상위 요소에 대한 참조를 반환합니다. – 시간 복잡도: O(1) push(a) – 스택 맨 위에 'a' 요소를 삽입합니다. – 시간 복잡도: O(1) pop() – 스택의 최상위 요소를 삭제합니다. – 시간 복잡도: O( 1)

Python 스택 구현

Python의 스택은 다음 방법을 사용하여 구현할 수 있습니다.

• 목록
• Collections.deque
• 큐.Lifo큐

목록을 사용한 구현

Python에 내장된 데이터 구조 목록을 스택으로 사용할 수 있습니다. push() 대신, add()를 사용하여 스택 상단에 요소를 추가하고, pop()은 LIFO 순서로 요소를 제거합니다.

파이썬3

stack> => []> # append() function to push> # element in the stack> stack.append(> 'g'> )> stack.append(> 'f'> )> stack.append(> 'g'> )> print> (> 'Initial stack'> )> print> (stack)> # pop() function to pop> # element from stack in> # LIFO order> print> (> ' Elements popped from stack:'> )> print> (stack.pop())> print> (stack.pop())> print> (stack.pop())> print> (> ' Stack after elements are popped:'> )> print> (stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty>

산출

Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: [] 

collections.deque를 사용한 구현:

Python 스택은 컬렉션 모듈의 deque 클래스를 사용하여 구현할 수 있습니다. Deque는 O(n)을 제공하는 목록에 비해 추가 및 팝 작업에 O(1) 시간 복잡도를 제공하므로 컨테이너의 양쪽 끝에서 더 빠른 추가 및 팝 작업이 필요한 경우 목록보다 Deque가 선호됩니다. 시간 복잡도.

파이썬3

from> collections> import> deque> stack> => deque()> # append() function to push> # element in the stack> stack.append(> 'g'> )> stack.append(> 'f'> )> stack.append(> 'g'> )> print> (> 'Initial stack:'> )> print> (stack)> # pop() function to pop> # element from stack in> # LIFO order> print> (> ' Elements popped from stack:'> )> print> (stack.pop())> print> (stack.pop())> print> (stack.pop())> print> (> ' Stack after elements are popped:'> )> print> (stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty>

산출

Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([]) 

큐 모듈을 이용한 구현

대기열 모듈에는 기본적으로 스택인 LIFO 대기열도 있습니다. put() 함수를 사용하여 데이터를 Queue에 삽입하고 get()을 사용하여 Queue에서 데이터를 가져옵니다.

파이썬3

from> queue> import> LifoQueue> # Initializing a stack> stack> => LifoQueue(maxsize> => 3> )> # qsize() show the number of elements> # in the stack> print> (stack.qsize())> # put() function to push> # element in the stack> stack.put(> 'g'> )> stack.put(> 'f'> )> stack.put(> 'g'> )> print> (> 'Full: '> , stack.full())> print> (> 'Size: '> , stack.qsize())> # get() function to pop> # element from stack in> # LIFO order> print> (> ' Elements popped from the stack'> )> print> (stack.get())> print> (stack.get())> print> (stack.get())> print> (> ' Empty: '> , stack.empty())>

산출

0 Full: True Size: 3 Elements popped from the stack g f g Empty: True 

대기줄

스택으로서, 대기줄 FIFO(선입선출) 방식으로 항목을 저장하는 선형 데이터 구조입니다. 대기열을 사용하면 가장 최근에 추가된 항목이 먼저 제거됩니다. 대기열의 좋은 예는 먼저 온 소비자가 먼저 제공되는 리소스에 대한 소비자 대기열입니다.

대기열과 관련된 작업은 다음과 같습니다.

Enqueue: 대기열에 항목을 추가합니다. 대기열이 가득 차면 오버플로 상태라고 합니다. – 시간 복잡도: O(1) 대기열 제거: 대기열에서 항목을 제거합니다. 항목은 푸시된 순서와 동일한 순서로 팝됩니다. 큐가 비어 있으면 언더플로우 조건이라고 합니다. – 시간 복잡도: O(1) 전면: 큐에서 맨 앞 항목 가져오기 – 시간 복잡도: O(1) 후면: 큐에서 마지막 항목 가져오기 – 시간 복잡도 : ㅇ(1)

Python 대기열 구현

Python의 대기열은 다음과 같은 방법으로 구현할 수 있습니다.

• 목록
• collections.deque
• 꼬리.꼬리

목록을 이용한 구현

enqueue(), dequeue() 대신에 add(), pop() 함수를 사용합니다.

파이썬3

# Initializing a queue> queue> => []> # Adding elements to the queue> queue.append(> 'g'> )> queue.append(> 'f'> )> queue.append(> 'g'> )> print> (> 'Initial queue'> )> print> (queue)> # Removing elements from the queue> print> (> ' Elements dequeued from queue'> )> print> (queue.pop(> 0> ))> print> (queue.pop(> 0> ))> print> (queue.pop(> 0> ))> print> (> ' Queue after removing elements'> )> print> (queue)> # Uncommenting print(queue.pop(0))> # will raise and IndexError> # as the queue is now empty>

산출

Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements [] 

collections.deque를 사용한 구현

Deque는 O(n)을 제공하는 목록에 비해 추가 및 팝 작업에 O(1) 시간 복잡도를 제공하므로 컨테이너의 양쪽 끝에서 더 빠른 추가 및 팝 작업이 필요한 경우 목록보다 Deque가 선호됩니다. 시간 복잡도.

파이썬3

from> collections> import> deque> # Initializing a queue> q> => deque()> # Adding elements to a queue> q.append(> 'g'> )> q.append(> 'f'> )> q.append(> 'g'> )> print> (> 'Initial queue'> )> print> (q)> # Removing elements from a queue> print> (> ' Elements dequeued from the queue'> )> print> (q.popleft())> print> (q.popleft())> print> (q.popleft())> print> (> ' Queue after removing elements'> )> print> (q)> # Uncommenting q.popleft()> # will raise an IndexError> # as queue is now empty>

산출

Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([]) 

queue.Queue를 사용한 구현

queue.Queue(maxsize)는 변수를 최대 크기인 maxsize로 초기화합니다. 최대 크기가 0인 '0'은 무한 대기열을 의미합니다. 이 대기열은 FIFO 규칙을 따릅니다.

파이썬3

from> queue> import> Queue> # Initializing a queue> q> => Queue(maxsize> => 3> )> # qsize() give the maxsize> # of the Queue> print> (q.qsize())> # Adding of element to queue> q.put(> 'g'> )> q.put(> 'f'> )> q.put(> 'g'> )> # Return Boolean for Full> # Queue> print> (> ' Full: '> , q.full())> # Removing element from queue> print> (> ' Elements dequeued from the queue'> )> print> (q.get())> print> (q.get())> print> (q.get())> # Return Boolean for Empty> # Queue> print> (> ' Empty: '> , q.empty())> q.put(> 1> )> print> (> ' Empty: '> , q.empty())> print> (> 'Full: '> , q.full())> # This would result into Infinite> # Loop as the Queue is empty.> # print(q.get())>

산출

0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False 

우선순위 대기열

우선순위 대기열 큐의 각 데이터/값이 특정 우선순위를 갖는 추상 데이터 구조입니다. 예를 들어 항공사에서는 비즈니스 또는 일등석이라는 제목의 수하물이 나머지 수하물보다 먼저 도착합니다. 우선순위 큐는 다음 속성을 가진 큐의 확장입니다.

• 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 대기열에서 제거됩니다.
• 두 요소의 우선순위가 동일한 경우 대기열의 순서에 따라 처리됩니다.

파이썬3

# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(> object> ):> > def> __init__(> self> ):> > self> .queue> => []> > def> __str__(> self> ):> > return> ' '> .join([> str> (i)> for> i> in> self> .queue])> > # for checking if the queue is empty> > def> isEmpty(> self> ):> > return> len> (> self> .queue)> => => 0> > # for inserting an element in the queue> > def> insert(> self> , data):> > self> .queue.append(data)> > # for popping an element based on Priority> > def> delete(> self> ):> > try> :> > max> => 0> > for> i> in> range> (> len> (> self> .queue)):> > if> self> .queue[i]>> self> .queue[> max> ]:> > max> => i> > item> => self> .queue[> max> ]> > del> self> .queue[> max> ]> > return> item> > except> IndexError:> > print> ()> > exit()> if> __name__> => => '__main__'> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())>

산출

12 1 14 7 14 12 7 1 

힙 큐(또는 heapq)

Python의 heapq 모듈 우선순위 큐를 표현하는데 주로 사용되는 힙 데이터 구조를 제공합니다. Python에서 이 데이터 구조의 속성은 매번 가장 작은 힙 요소가 팝된다는 것입니다(최소 힙). 요소가 푸시되거나 팝될 때마다 힙 구조가 유지됩니다. heap[0] 요소는 매번 가장 작은 요소도 반환합니다.

O(log n) 시간에 가장 작은 요소의 추출 및 삽입을 지원합니다.

파이썬3

# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li> => [> 5> ,> 7> ,> 9> ,> 1> ,> 3> ]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print> (> 'The created heap is : '> ,end> => '')> print> (> list> (li))> # using heappush() to push elements into heap> # pushes 4> heapq.heappush(li,> 4> )> # printing modified heap> print> (> 'The modified heap after push is : '> ,end> => '')> print> (> list> (li))> # using heappop() to pop smallest element> print> (> 'The popped and smallest element is : '> ,end> => '')> print> (heapq.heappop(li))>

산출

The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1 

이진 트리

트리는 아래 그림과 같은 계층적 데이터 구조입니다.

 tree ---- j  <-- root /  f k /   a h z  <-- leaves 

트리의 최상위 노드를 루트(root)라고 하고, 최하위 노드나 자식이 없는 노드를 리프 노드(leaf node)라고 합니다. 노드 바로 아래에 있는 노드를 하위 노드라고 하고, 노드 바로 위에 있는 노드를 상위 노드라고 합니다.

이진 트리는 요소가 거의 두 개의 자식을 가질 수 있는 트리입니다. 이진 트리의 각 요소에는 자식이 2개만 있을 수 있으므로 일반적으로 왼쪽 및 오른쪽 자식으로 이름을 지정합니다. 이진 트리 노드에는 다음 부분이 포함됩니다.

• 데이터
• 왼쪽 자식에 대한 포인터
• 올바른 자식에 대한 포인터

예: 노드 클래스 정의

파이썬3

# A Python class that represents an individual node> # in a Binary Tree> class> Node:> > def> __init__(> self> ,key):> > self> .left> => None> > self> .right> => None> > self> .val> => key>

이제 Python에서 4개의 노드가 있는 트리를 만들어 보겠습니다. 트리 구조가 아래와 같다고 가정해 보겠습니다.

 tree ---- 1  <-- root /  2 3 / 4 

예: 트리에 데이터 추가

파이썬3

# Python program to introduce Binary Tree> # A class that represents an individual node in a> # Binary Tree> class> Node:> > def> __init__(> self> ,key):> > self> .left> => None> > self> .right> => None> > self> .val> => key> # create root> root> => Node(> 1> )> ''' following is the tree after above statement> > 1> > /> > None None'''> root.left> => Node(> 2> );> root.right> => Node(> 3> );> ''' 2 and 3 become left and right children of 1> > 1> > /> > 2 3> > / /> None None None None'''> root.left.left> => Node(> 4> );> '''4 becomes left child of 2> > 1> > /> > 2 3> > / /> 4 None None None> /> None None'''>

트리 순회

나무를 횡단할 수 있다 다른 방법으로. 다음은 트리를 횡단하는 데 일반적으로 사용되는 방법입니다. 아래 트리를 고려해 보겠습니다.

 tree ---- 1  <-- root /  2 3 /  4 5 

깊이 우선 순회:

• 중위(왼쪽, 루트, 오른쪽) : 4 2 5 1 3
• 예약주문(루트, 왼쪽, 오른쪽) : 1 2 4 5 3
• 후위(왼쪽, 오른쪽, 루트) : 4 5 2 3 1

알고리즘 순서(트리)

• 왼쪽 하위 트리를 탐색합니다. 즉, Inorder(left-subtree)를 호출합니다.
• 루트를 방문하십시오.
• 오른쪽 하위 트리를 탐색합니다. 즉, Inorder(right-subtree)를 호출합니다.

알고리즘 선주문(트리)

• 루트를 방문하십시오.
• 왼쪽 하위 트리를 탐색합니다. 즉, Preorder(left-subtree)를 호출합니다.
• 오른쪽 하위 트리를 탐색합니다. 즉, Preorder(right-subtree)를 호출합니다.

알고리즘 우편순서(트리)

• 왼쪽 하위 트리를 탐색합니다. 즉, Postorder(left-subtree)를 호출합니다.
• 오른쪽 하위 트리를 탐색합니다. 즉, Postorder(right-subtree)를 호출합니다.
• 루트를 방문하십시오.

파이썬3

# Python program to for tree traversals> # A class that represents an individual node in a> # Binary Tree> class> Node:> > def> __init__(> self> , key):> > self> .left> => None> > self> .right> => None> > self> .val> => key> # A function to do inorder tree traversal> def> printInorder(root):> > if> root:> > # First recur on left child> > printInorder(root.left)> > # then print the data of node> > print> (root.val),> > # now recur on right child> > printInorder(root.right)> # A function to do postorder tree traversal> def> printPostorder(root):> > if> root:> > # First recur on left child> > printPostorder(root.left)> > # the recur on right child> > printPostorder(root.right)> > # now print the data of node> > print> (root.val),> # A function to do preorder tree traversal> def> printPreorder(root):> > if> root:> > # First print the data of node> > print> (root.val),> > # Then recur on left child> > printPreorder(root.left)> > # Finally recur on right child> > printPreorder(root.right)> # Driver code> root> => Node(> 1> )> root.left> => Node(> 2> )> root.right> => Node(> 3> )> root.left.left> => Node(> 4> )> root.left.right> => Node(> 5> )> print> (> 'Preorder traversal of binary tree is'> )> printPreorder(root)> print> (> ' Inorder traversal of binary tree is'> )> printInorder(root)> print> (> ' Postorder traversal of binary tree is'> )> printPostorder(root)>

산출

Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1 

시간 복잡도 - O(n)

너비 우선 또는 레벨 순서 순회

레벨 순서 순회 트리의 너비 우선 순회는 트리에 대한 너비 우선 순회입니다. 위 트리의 레벨 순서 순회는 1 2 3 4 5입니다.

각 노드에 대해 먼저 노드를 방문한 다음 해당 하위 노드를 FIFO 대기열에 넣습니다. 아래는 동일한 알고리즘입니다.

• 빈 대기열 만들기 q
• temp_node = 루트 /*루트에서 시작*/
• temp_node가 NULL이 아닌 동안 루프
  • temp_node->data를 인쇄합니다.
  • temp_node의 자식(먼저 왼쪽, 오른쪽 자식)을 q에 대기열에 넣습니다.
  • q에서 노드 대기열 제거

파이썬3

# Python program to print level> # order traversal using Queue> # A node structure> class> Node:> > > # A utility function to create a new node> > def> __init__(> self> ,key):> > self> .data> => key> > self> .left> => None> > self> .right> => None> # Iterative Method to print the> # height of a binary tree> def> printLevelOrder(root):> > > # Base Case> > if> root> is> None> :> > return> > > # Create an empty queue> > # for level order traversal> > queue> => []> > # Enqueue Root and initialize height> > queue.append(root)> > while> (> len> (queue)>> 0> ):> > > # Print front of queue and> > # remove it from queue> > print> (queue[> 0> ].data)> > node> => queue.pop(> 0> )> > # Enqueue left child> > if> node.left> is> not> None> :> > queue.append(node.left)> > # Enqueue right child> > if> node.right> is> not> None> :> > queue.append(node.right)> # Driver Program to test above function> root> => Node(> 1> )> root.left> => Node(> 2> )> root.right> => Node(> 3> )> root.left.left> => Node(> 4> )> root.left.right> => Node(> 5> )> print> (> 'Level Order Traversal of binary tree is -'> )> printLevelOrder(root)>

산출

Level Order Traversal of binary tree is - 1 2 3 4 5 

시간 복잡도: O(n)

그래프

ㅏ 그래프 노드와 에지로 구성된 비선형 데이터 구조입니다. 노드는 정점이라고도 하며 가장자리는 그래프의 두 노드를 연결하는 선 또는 호입니다. 보다 공식적으로 그래프는 유한한 정점(또는 노드) 집합과 노드 쌍을 연결하는 가장자리 집합으로 구성된 그래프로 정의할 수 있습니다.

위 그래프에서 정점 집합 V = {0,1,2,3,4}이고 간선 집합 E = {01, 12, 23, 34, 04, 14, 13}입니다.

다음 두 가지는 가장 일반적으로 사용되는 그래프 표현입니다.

• 인접 행렬
• 인접 목록

인접 행렬

인접 행렬(Adjacency Matrix)은 V x V 크기의 2D 배열입니다. 여기서 V는 그래프의 정점 수입니다. 2D 배열을 adj[][]라고 가정하면, 슬롯 adj[i][j] = 1은 정점 i에서 정점 j까지의 가장자리가 있음을 나타냅니다. 무방향 그래프의 인접 행렬은 항상 대칭입니다. 인접 행렬은 가중치 그래프를 나타내는 데에도 사용됩니다. adj[i][j] = w이면 정점 i에서 정점 j까지 가중치가 w인 간선이 있습니다.

파이썬3

# A simple representation of graph using Adjacency Matrix> class> Graph:> > def> __init__(> self> ,numvertex):> > self> .adjMatrix> => [[> -> 1> ]> *> numvertex> for> x> in> range> (numvertex)]> > self> .numvertex> => numvertex> > self> .vertices> => {}> > self> .verticeslist> => [> 0> ]> *> numvertex> > def> set_vertex(> self> ,vtx,> id> ):> > if> 0> <> => vtx <> => self> .numvertex:> > self> .vertices[> id> ]> => vtx> > self> .verticeslist[vtx]> => id> > def> set_edge(> self> ,frm,to,cost> => 0> ):> > frm> => self> .vertices[frm]> > to> => self> .vertices[to]> > self> .adjMatrix[frm][to]> => cost> > > # for directed graph do not add this> > self> .adjMatrix[to][frm]> => cost> > def> get_vertex(> self> ):> > return> self> .verticeslist> > def> get_edges(> self> ):> > edges> => []> > for> i> in> range> (> self> .numvertex):> > for> j> in> range> (> self> .numvertex):> > if> (> self> .adjMatrix[i][j]!> => -> 1> ):> > edges.append((> self> .verticeslist[i],> self> .verticeslist[j],> self> .adjMatrix[i][j]))> > return> edges> > > def> get_matrix(> self> ):> > return> self> .adjMatrix> G> => Graph(> 6> )> G.set_vertex(> 0> ,> 'a'> )> G.set_vertex(> 1> ,> 'b'> )> G.set_vertex(> 2> ,> 'c'> )> G.set_vertex(> 3> ,> 'd'> )> G.set_vertex(> 4> ,> 'e'> )> G.set_vertex(> 5> ,> 'f'> )> G.set_edge(> 'a'> ,> 'e'> ,> 10> )> G.set_edge(> 'a'> ,> 'c'> ,> 20> )> G.set_edge(> 'c'> ,> 'b'> ,> 30> )> G.set_edge(> 'b'> ,> 'e'> ,> 40> )> G.set_edge(> 'e'> ,> 'd'> ,> 50> )> G.set_edge(> 'f'> ,> 'e'> ,> 60> )> print> (> 'Vertices of Graph'> )> print> (G.get_vertex())> print> (> 'Edges of Graph'> )> print> (G.get_edges())> print> (> 'Adjacency Matrix of Graph'> )> print> (G.get_matrix())>

산출

그래프의 정점

['a', 'b', 'c', 'd', 'e', ​​'f']

그래프의 가장자리

[('a', 'c', 20), ('a', 'e', ​​10), ('b', 'c', 30), ('b', 'e', ​​40), ( 'c', 'a', 20), ('c', 'b', 30), ('d', 'e', ​​50), ('e', 'a', 10), ('e ', 'b', 40), ('e', 'd', 50), ('e', 'f', 60), ('f', 'e', ​​60)]

그래프의 인접 행렬

[[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1 , -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]

인접 목록

목록의 배열이 사용됩니다. 배열의 크기는 정점의 수와 같습니다. 배열을 array[]로 둡니다. 항목 array[i]는 i번째 꼭지점에 인접한 꼭지점의 목록을 나타냅니다. 이 표현은 가중치 그래프를 나타내는 데에도 사용할 수 있습니다. 간선의 가중치는 쌍 목록으로 표현될 수 있습니다. 다음은 위 그래프의 인접 목록 표현입니다.

파이썬3

# A class to represent the adjacency list of the node> class> AdjNode:> > def> __init__(> self> , data):> > self> .vertex> => data> > self> .> next> => None> # A class to represent a graph. A graph> # is the list of the adjacency lists.> # Size of the array will be the no. of the> # vertices 'V'> class> Graph:> > def> __init__(> self> , vertices):> > self> .V> => vertices> > self> .graph> => [> None> ]> *> self> .V> > # Function to add an edge in an undirected graph> > def> add_edge(> self> , src, dest):> > > # Adding the node to the source node> > node> => AdjNode(dest)> > node.> next> => self> .graph[src]> > self> .graph[src]> => node> > # Adding the source node to the destination as> > # it is the undirected graph> > node> => AdjNode(src)> > node.> next> => self> .graph[dest]> > self> .graph[dest]> => node> > # Function to print the graph> > def> print_graph(> self> ):> > for> i> in> range> (> self> .V):> > print> (> 'Adjacency list of vertex {} head'> .> format> (i), end> => '')> > temp> => self> .graph[i]> > while> temp:> > print> (> ' ->{}'> .> format> (temp.vertex), end> => '')> > temp> => temp.> next> > print> (> ' '> )> # Driver program to the above graph class> if> __name__> => => '__main__'> :> > V> => 5> > graph> => Graph(V)> > graph.add_edge(> 0> ,> 1> )> > graph.add_edge(> 0> ,> 4> )> > graph.add_edge(> 1> ,> 2> )> > graph.add_edge(> 1> ,> 3> )> > graph.add_edge(> 1> ,> 4> )> > graph.add_edge(> 2> ,> 3> )> > graph.add_edge(> 3> ,> 4> )> > graph.print_graph()>

산출

Adjacency list of vertex 0 head ->4 -> 1 정점 1 머리의 인접 목록 -> 4 -> 3 -> 2 -> 0 정점 2 머리의 인접 목록 -> 3 -> 1 정점 3 머리의 인접 목록 -> 4 -> 2 -> 1 인접 목록 정점 4 머리 목록 -> 3 -> 1 -> 0 

그래프 순회

너비 우선 검색(BFS)

너비 우선 순회 그래프의 경우 트리의 너비 우선 순회와 유사합니다. 여기서 유일한 문제는 트리와 달리 그래프에 사이클이 포함될 수 있으므로 동일한 노드에 다시 올 수 있다는 것입니다. 노드를 두 번 이상 처리하지 않으려면 부울 방문 배열을 사용합니다. 단순화를 위해 시작 정점에서 모든 정점에 도달할 수 있다고 가정합니다.

예를 들어, 다음 그래프에서는 정점 2에서 순회를 시작합니다. 정점 0에 도달하면 인접한 모든 정점을 찾습니다. 2도 0의 인접한 정점입니다. 방문한 정점을 표시하지 않으면 2가 다시 처리되어 비종료 프로세스가 됩니다. 다음 그래프의 너비 우선 순회는 2, 0, 3, 1입니다.

파이썬3

# Python3 Program to print BFS traversal> # from a given source vertex. BFS(int s)> # traverses vertices reachable from s.> from> collections> import> defaultdict> # This class represents a directed graph> # using adjacency list representation> class> Graph:> > # Constructor> > def> __init__(> self> ):> > # default dictionary to store graph> > self> .graph> => defaultdict(> list> )> > # function to add an edge to graph> > def> addEdge(> self> ,u,v):> > self> .graph[u].append(v)> > # Function to print a BFS of graph> > def> BFS(> self> , s):> > # Mark all the vertices as not visited> > visited> => [> False> ]> *> (> max> (> self> .graph)> +> 1> )> > # Create a queue for BFS> > queue> => []> > # Mark the source node as> > # visited and enqueue it> > queue.append(s)> > visited[s]> => True> > while> queue:> > # Dequeue a vertex from> > # queue and print it> > s> => queue.pop(> 0> )> > print> (s, end> => ' '> )> > # Get all adjacent vertices of the> > # dequeued vertex s. If a adjacent> > # has not been visited, then mark it> > # visited and enqueue it> > for> i> in> self> .graph[s]:> > if> visited[i]> => => False> :> > queue.append(i)> > visited[i]> => True> # Driver code> # Create a graph given in> # the above diagram> g> => Graph()> g.addEdge(> 0> ,> 1> )> g.addEdge(> 0> ,> 2> )> g.addEdge(> 1> ,> 2> )> g.addEdge(> 2> ,> 0> )> g.addEdge(> 2> ,> 3> )> g.addEdge(> 3> ,> 3> )> print> (> 'Following is Breadth First Traversal'> > ' (starting from vertex 2)'> )> g.BFS(> 2> )> # This code is contributed by Neelam Yadav>

산출

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1 

시간 복잡도: O(V+E) 여기서 V는 그래프의 정점 수이고 E는 그래프의 가장자리 수입니다.

깊이 우선 검색 또는 DFS

깊이 우선 순회 그래프의 경우 트리의 깊이 우선 순회와 유사합니다. 여기서 유일한 문제는 트리와 달리 그래프에 주기가 포함될 수 있고 노드를 두 번 방문할 수 있다는 것입니다. 노드를 두 번 이상 처리하지 않으려면 부울 방문 배열을 사용하십시오.

연산:

• 노드의 인덱스와 방문한 배열을 사용하는 재귀 함수를 만듭니다.
• 현재 노드를 방문한 것으로 표시하고 노드를 인쇄합니다.
• 인접 노드와 표시되지 않은 노드를 모두 순회하고 인접 노드의 인덱스를 사용하여 재귀 함수를 호출합니다.

파이썬3

# Python3 program to print DFS traversal> # from a given graph> from> collections> import> defaultdict> # This class represents a directed graph using> # adjacency list representation> class> Graph:> > # Constructor> > def> __init__(> self> ):> > # default dictionary to store graph> > self> .graph> => defaultdict(> list> )> > # function to add an edge to graph> > def> addEdge(> self> , u, v):> > self> .graph[u].append(v)> > # A function used by DFS> > def> DFSUtil(> self> , v, visited):> > # Mark the current node as visited> > # and print it> > visited.add(v)> > print> (v, end> => ' '> )> > # Recur for all the vertices> > # adjacent to this vertex> > for> neighbour> in> self> .graph[v]:> > if> neighbour> not> in> visited:> > self> .DFSUtil(neighbour, visited)> > # The function to do DFS traversal. It uses> > # recursive DFSUtil()> > def> DFS(> self> , v):> > # Create a set to store visited vertices> > visited> => set> ()> > # Call the recursive helper function> > # to print DFS traversal> > self> .DFSUtil(v, visited)> # Driver code> # Create a graph given> # in the above diagram> g> => Graph()> g.addEdge(> 0> ,> 1> )> g.addEdge(> 0> ,> 2> )> g.addEdge(> 1> ,> 2> )> g.addEdge(> 2> ,> 0> )> g.addEdge(> 2> ,> 3> )> g.addEdge(> 3> ,> 3> )> print> (> 'Following is DFS from (starting from vertex 2)'> )> g.DFS(> 2> )>

산출

Following is DFS from (starting from vertex 2) 2 0 1 3 

시간 복잡도: O(V + E), 여기서 V는 정점 수이고 E는 그래프의 간선 수입니다.