データ構造 状況に応じてより効率的にアクセスできるようにデータを整理する方法です。データ構造は、プログラムを構築するあらゆるプログラミング言語の基礎です。 Python は、他のプログラミング言語と比べて、これらのデータ構造の基礎を簡単な方法で学習するのに役立ちます。

この記事では、Python プログラミング言語のデータ構造と、それらがリスト タプルや辞書などの特定の組み込みデータ構造やツリー、グラフなどの高度なデータ構造とどのように関連しているかについて説明します。

リスト

Python リストは、他の言語で宣言された、順序付けられたデータのコレクションである配列とまったく同じです。リスト内の項目が同じタイプである必要がないため、非常に柔軟です。

Python List の実装は、C++ の Vector や JAVA の ArrayList に似ています。すべての要素を移動する必要があるため、コストのかかる操作は、リストの先頭から要素を挿入または削除することです。事前に割り当てられたメモリがいっぱいになった場合、リストの末尾での挿入と削除もコストがかかる可能性があります。

以下に示すように、Python でリストを作成できます。

例: Python リストの作成

Python3

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

出力

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

リスト要素には、割り当てられたインデックスによってアクセスできます。 Python のリストの開始インデックスでは、シーケンスは 0 で、終了インデックスは (要素が N 個ある場合) N-1 です。

例: Python のリスト操作

Python3

# 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 

辞書

Python辞書 これは、時間計算量が O(1) である他の言語のハッシュ テーブルと似ています。これはデータ値の順序付けされていないコレクションであり、マップのようなデータ値を格納するために使用されます。要素として単一の値のみを保持する他のデータ型とは異なり、ディクショナリはキー:値のペアを保持します。ディクショナリをより最適化するために、キーと値がディクショナリに提供されます。

Python 辞書のインデックス付けはキーを使用して行われます。これらはハッシュ可能なタイプ、つまり文字列、数値、タプルなどの決して変更できないオブジェクトです。中かっこ ({}) またはを使用して辞書を作成できます。 辞書の理解力 。

例: Python 辞書の操作

Python3

# 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 では、データ シーケンスのグループ化に括弧を使用するかどうかにかかわらず、一連の値を「カンマ」で区切って配置することによってタプルが作成されます。

注記： 単一の要素を使用してタプルを作成することもできますが、少し注意が必要です。括弧内に 1 つの要素があるだけでは十分ではありません。タプルにするには末尾に「カンマ」が必要です。

例: Python タプル操作

Python3

# 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) で挿入、削除、および走査を実行する一般的な手法です。

同じインデックス位置に複数の値が存在する場合、値はそのインデックス位置に追加され、リンクされたリストが形成されます。 CPython では、ダミー変数を含むディクショナリを使用して実装されます。ここで、キーは、時​​間計算量を大幅に最適化したメンバー セットです。

セットの実装:

単一の HashTable に対する多数の操作を含むセット:

例: Python の集合演算

Python3

# 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 のフリーズ セットは、適用先のフリーズ セットに影響を与えずに結果を生成するメソッドと演算子のみをサポートする不変オブジェクトです。セットの要素はいつでも変更できますが、フリーズされたセットの要素は作成後も同じままです。

パラメータが渡されない場合は、空のフローズンセットが返されます。

Python3

# 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 文字列は、Unicode 文字を表すバイトの配列です。簡単に言うと、文字列は不変の文字の配列です。 Python には文字データ型はなく、単一の文字は単に長さ 1 の文字列です。

注記： 文字列は不変であるため、文字列を変更すると新しいコピーが作成されます。

例: Python 文字列操作

Python3

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 バイト配列操作

Python3

# 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 のカウンター操作

Python3

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 操作

Python3

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 の操作

Python3

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 は、多くの辞書を 1 つのユニットにカプセル化し、辞書のリストを返します。キーを見つける必要がある場合、キーが見つかるまですべての辞書が 1 つずつ検索されます。

例: Python ChainMap の操作

Python3

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' 

名前付きタプル

あ 名前付きタプル 通常のタプルにはない各位置の名前を持つタプル オブジェクトを返します。たとえば、最初の要素が fname を表し、2 番目の要素が lname を表し、3 番目の要素が DOB を表す、student という名前のタプルを考えてみましょう。 fname を呼び出す場合、インデックス位置を記憶する代わりに、実際に fname 引数を使用して要素を呼び出すことができると仮定すると、タプル要素にアクセスするのが非常に簡単になります。この機能は NamedTuple によって提供されます。

例: Python の NamedTuple 操作

Python3

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 のデキュー操作

Python3

# 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

Python3

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 ユーザーリスト

Python3

# 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 ユーザー文字列

Python3

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 になります。リスト内の各ノードは、少なくとも 2 つの部分で構成されます。

• データ
• 次のノードへのポインタ (または参照)

例: Python でのリンク リストの定義

Python3

# 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 つのノードを持つ単純なリンク リストを作成してみましょう。

Python3

# 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 |ヌル | | 3 | null |>> > +----+------+ +----+------+ +----+------+> > '''> > 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 | null |>> > +----+------+ +----+------+ +----+------+> > '''>

リンクされたリストのトラバーサル

前のプログラムでは、3 つのノードを持つ単純なリンク リストを作成しました。作成されたリストを調べて、各ノードのデータを出力してみましょう。トラバーサルのために、指定されたリストを出力する汎用関数 printList() を作成しましょう。

Python3

# 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) 方式で項目を格納する線形データ構造です。スタックでは、新しい要素が一方の端に追加され、要素はその端からのみ削除されます。挿入および削除操作は、プッシュおよびポップと呼ばれることがよくあります。

スタックに関連付けられた関数は次のとおりです。

empty() – スタックが空かどうかを返します – 時間計算量: O(1) size() – スタックのサイズを返します – 時間計算量: O(1) top() – スタックの最上位要素への参照を返します– 時間計算量: O(1) Push(a) – スタックの先頭に要素 'a' を挿入 – 時間計算量: O(1) Pop() – スタックの最上位の要素を削除 – 時間計算量: O( 1)

Python スタックの実装

Python のスタックは、次の方法を使用して実装できます。

• リスト
• Collections.deque
• キュー.LifoQueue

リストを使った実装

Python の組み込みデータ構造リストをスタックとして使用できます。 Push() の代わりに、append() を使用してスタックの先頭に要素を追加し、pop() が LIFO 順序で要素を削除します。

Python3

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) を提供するリストと比較して、deque の追加およびポップ操作の時間計算量が O(1) であるためです。時間の複雑さ。

Python3

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() 関数を使用してキューに挿入され、get() はキューからデータを取り出します。

Python3

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) 方式で項目を格納する線形データ構造です。キューを使用すると、最後に追加された項目が最初に削除されます。キューの良い例は、最初に来たコンシューマが最初に処理されるリソースのコンシューマのキューです。

キューに関連付けられた操作は次のとおりです。

エンキュー: 項目をキューに追加します。キューがいっぱいの場合、それはオーバーフロー状態であると言われます – 時間複雑さ: O(1) デキュー: キューから項目を削除します。項目は、プッシュされたのと同じ順序でポップされます。キューが空の場合、それはアンダーフロー状態であると言われます – 時間複雑さ: O(1) フロント: キューから前のアイテムを取得します – 時間複雑さ: O(1) リア: キューから最後のアイテムを取得します – 時間複雑さ:O(1)

Pythonキューの実装

Python のキューは次の方法で実装できます。

• リスト
• コレクション.deque
• 尾.尾

リストを使った実装

enqueue() と dequeue() の代わりに、append() と Pop() 関数が使用されます。

Python3

# 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) を提供するリストと比較して、deque の追加およびポップ操作の時間計算量が O(1) であるためです。時間の複雑さ。

Python3

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 に初期化します。 maxsize がゼロの「0」は、無限のキューを意味します。このキューは FIFO ルールに従います。

Python3

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 

優先キュー

優先キュー は抽象データ構造であり、キュー内の各データ/値には特定の優先順位があります。たとえば、航空会社では、ビジネスクラスまたはファーストクラスというタイトルが付いた手荷物は、他の手荷物よりも早く到着します。 Priority Queue は、次のプロパティを持つキューの拡張です。

• 優先度の高い要素は、優先度の低い要素よりも前にデキューされます。
• 2 つの要素の優先順位が同じ場合、それらはキュー内の順序に従って処理されます。

Python3

# 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 におけるこのデータ構造の特性は、毎回最小のヒープ要素がポップされる (min-heap) ということです。要素がプッシュまたはポップされるたびに、ヒープ構造が維持されます。 heap[0] 要素も毎回最小の要素を返します。

O(log n) 回の最小要素の抽出と挿入をサポートします。

Python3

# 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 

ツリーの最上位のノードはルートと呼ばれ、最下位のノードまたは子のないノードはリーフ ノードと呼ばれます。ノードの直下にあるノードはその子と呼ばれ、何かの直上にあるノードはその親と呼ばれます。

バイナリ ツリーは、その要素がほぼ 2 つの子を持つことができるツリーです。バイナリ ツリー内の各要素は子を 2 つだけ持つことができるため、通常はそれらに left と right の子という名前を付けます。 Binary Tree ノードには次の部分が含まれます。

• データ
• 左の子へのポインタ
• 正しい子へのポインタ

例: ノードクラスの定義

Python3

# 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 

例: ツリーへのデータの追加

Python3

# 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) を呼び出します。
• ルートを訪問します。

Python3

# 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 = root /*ルートから開始*/
• temp_node が NULL でない間のループ
  • temp_node->data を出力します。
  • temp_node の子 (最初に左の子、次に右の子) を q にエンキューします。
  • qからノードをデキューします

Python3

# 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)

グラフ

あ グラフ は、ノードとエッジで構成される非線形データ構造です。ノードは頂点と呼ばれることもあり、エッジはグラフ内の任意の 2 つのノードを接続する線または円弧です。より正式には、グラフは、頂点 (またはノード) の有限セットと、ノードのペアを接続するエッジのセットで構成されるグラフとして定義できます。

上のグラフでは、頂点のセット V = {0,1,2,3,4}、エッジのセット E = {01, 12, 23, 34, 04, 14, 13} です。

次の 2 つは、グラフの最も一般的に使用される表現です。

• 隣接行列
• 隣接リスト

隣接行列

隣接行列は、サイズ V x V の 2D 配列です。ここで、V はグラフ内の頂点の数です。 2D 配列を adj[][] とすると、スロット adj[i][j] = 1 は、頂点 i から頂点 j までのエッジがあることを示します。無向グラフの隣接行列は常に対称です。隣接行列は、重み付きグラフを表すためにも使用されます。 adj[i][j] = w の場合、頂点 i から頂点 j まで重み w のエッジが存在します。

Python3

# 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 番目の頂点に隣接する頂点のリストを表します。この表現は、重み付きグラフを表すために使用することもできます。エッジの重みはペアのリストとして表すことができます。以下は、上記のグラフの隣接リスト表現です。

Python3

# 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 です。

Python3

# 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

深さ優先トラバーサル グラフの場合、ツリーの深さ優先探索に似ています。ここでの唯一の注意点は、ツリーとは異なり、グラフにはサイクルが含まれる可能性があり、ノードが 2 回アクセスされる可能性があることです。ノードを複数回処理しないようにするには、ブール値の訪問済み配列を使用します。

アルゴリズム：

• ノードのインデックスとアクセスした配列を取得する再帰関数を作成します。
• 現在のノードを訪問済みとしてマークし、ノードを出力します。
• すべての隣接ノードとマークされていないノードを走査し、隣接ノードのインデックスを使用して再帰関数を呼び出します。

Python3

# 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 はエッジの数です。