## 【Data Structures 資料結構】
:::info
- 什麼是資料結構?
- 資料結構
- Array數組/List列表/Tuple元組
- Linked List 鏈結串列
- Singly Linked Lists
- Doubly Linked Lists
- Hash Table 哈希表
- Set集合
- Stacks and Queues 堆疊和佇列
- Stack
- Queue
- Recursion 遞迴
- Trees 樹
- Graphs 圖 : 無向圖、有向圖、權重無向圖、權重有向圖
:::
:::warning
參考書籍:
<br/>
參考網站: [NTNU](https://web.ntnu.edu.tw/~algo/)
<br/>
參考網站: [VISUALGO](https://visualgo.net/en)
<br/>
參考網站: [Leetcode 學習 探索知識地圖](https://leetcode.cn/leetbook/)
:::
<br/>
## 什麼是Data Structure資料結構?
也有人叫數據結構
ADT（Abstract Data Type，抽象資料類型）是一種用來描述資料結構的數學模型，強調資料的邏輯結構而不是具體的實現方式
資料結構是一種組織和存儲資料的方式，結構的設計取決於不同的應用需求
基本資料結構： 包括**陣列**、**鏈結串列**、**堆疊**、**佇列**等
複雜資料結構： 包括**樹**、**圖**、**散列表**等，通常用於解決複雜的問題，提高效率
<br/>
## 資料結構
> set集合: 無順序，類型無限制
>
> list(線性)列表: 有索引，有順序，類型無限制，python長度可變
>
> tuple元組: 有索引，有順序，類型無限制，長度不可變
>
> array數組: 有索引，有順序，類型相同，長度不可變
<br/>
## Array數組/List列表/Tuple元組 O(1),O(n)
在Python中，資料結構沒有Array數組，比較接近list，可以增加、減少。但在C語言中，數組一開始要指定大小，若要更動，只能開一個新的數組複製過去
<br/>
```=
# array/list O(1)
list1 = [1,2,3,4,5,6]
print(list1[0])
list2 = [[1,2,3,4,5,6],[7,8,9,10,11,12]]
print(list2[1][4])
```
```=
# 增加數據 O(1)
list1.append(9)
print(list)
list2[0].extend([7, 8])
list2[1].extend([13, 14])
print(list2)
```
```=
# 隨機增加數據 O(1)末尾,O(n)
import random
random_index = random.randint(0, len(list1))
list1.insert(random_index, 10)
print(list1)
random_index1 = random.randint(0, len(list2)-1)
random_index2 = random.randint(0, len(list2[random_index1])-1)
list2[random_index1].insert(random_index2, 15)
print(list2)
```
```=
# .extend() 是列表方法，用來將另一個序列中的元素逐個添加到列表末尾 O(k), k為list02的長度
list01 = [1, 2, 3]
list02 = [4, 5, 6]
list01.extend(list02)
print(list01)
```
```=
# 刪除數據 O(1)末尾,O(n)
list1.remove(10)
print(list1)
list2[1].remove(10)
print(list2)
```
```=
# 反轉 O(n/2) = O(n)
from typing import List
# way1
def reverse_array(list1):
start = 0
end = len(list1) - 1
while start < end:
list1[start], list1[end] = list1[end], list1[start]
start += 1
end -= 1
return list1
# way2
def reverse_array_pythonic(list1):
return list1[::-1]
if __name__ == "__main__":
list1 = [1, 3, 5, 7, 11, 10]
print(reverse_array(list1))
print(reverse_array_pythonic(list1))
```
```=
# palindrome 迴文 O(n)
def is_palindrome(s):
start_index = 0
end_index = len(s) - 1
while start_index < end_index:
if s[start_index] != s[end_index]:
return False
start_index += 1
end_index -= 1
return True
def is_palindrome_pythonic(s):
return s == s[::-1]
s = "ABCBA"
print(is_palindrome(s))
print(is_palindrome_pythonic(s))
# JS 寫法
# function isPalindrome(string) {
# return string === string.split('').reverse().join('');
# }
```
>tuple
tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組
```=
# tuple
# 增加數據
my_tuple = (1, 2, 3)
new_tuple = my_tuple + (4,)
new_tuple
```
```=
my_tuple = (1, "apple", 3.14)
first_element = my_tuple[0]
partial_tuple = my_tuple[1:]
print("First Element:", first_element)
print("Partial Tuple:", partial_tuple)
```
指定位置插入，可以先轉換為list，插入值後再轉回tuple
```=
# 指定位置插入，可以先轉換為list，插入值後再轉回tuple
my_tuple = (1, "apple", 3.14)
tuple_list = list(my_tuple)
tuple_list.insert(2, 10)
my_tuple = tuple(tuple_list)
print("Tuple:", my_tuple)
```
tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組
```=
# tuple元組，是不可變的，所以無法添加或刪除元素，但可以創建一個新的元組
my_tuple = (1, 2, 3)
new_tuple = tuple(t for t in my_tuple if t != 2)
new_tuple
```
指定位置刪除，可以先轉換為list，插入值後再轉回
```=
# 指定位置刪除，可以先轉換為list，插入值後再轉回
my_tuple = (1, 10, "apple", 3.14)
tuple_list = list(my_tuple)
del tuple_list[1]
my_tuple = tuple(tuple_list)
print("Tuple:", my_tuple)
```
反轉，可以先轉換為list，反轉後再轉回
```=
# 反轉，可以先轉換為list，反轉後再轉回
my_tuple = (1, 10, "apple", 3.14)
tuple_list = list(my_tuple)
tuple_list = reverse_array_pythonic(tuple_list)
my_tuple = tuple(tuple_list)
print("Reverse Tuple:", my_tuple)
```
<br/>
## Linked List 鏈結串列
Linked List長度可以增加、刪除，分為單向和雙向，數據節點稱為Node，單向只會指向下一個Node，雙向會指向前一個和下一個Node。頭部Node稱為"head",尾部Node稱為"tail"
<br/>
- Singly Linked List
```=
# single linked lists
# 知道tail情況下
class Node:
def __init__(self, data) -> None::
self.data = data
self.next = None
if __name__ == "__main__":
head = Node(data=1)
tail = head
node1 =Node(data=2)
tail = node1
node2 =Node(data=3)
head.next = node1
node1.next = node2
tail = node2
```
```=
class Node:
def __init__(self, data) -> None:
self.data = data
self.next = None
class LinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
# 末尾插入 O(1)知道尾部, 不知道尾部、任意位置O(n)
def append(self, value):
new_node = Node(value)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
# 頭部插入 O(1)
def prepend(self, value):
new_node = Node(value)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
# 印出
def print_list(self):
tmp = self.head
while tmp:
print(tmp.data, end=" ")
tmp = tmp.next
if tmp:
print("-> ", end=" ")
print()
if __name__ == "__main__":
linkedlist = LinkedList()
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
linkedlist.print_list()
linkedlist.prepend(4)
linkedlist.print_list()
```
```=
class Node:
def __init__(self, data) -> None:
self.data = data
self.next = None
class LinkedList:
def __init__(self, values=None) -> None:
self.head = None
self.tail = None
if values:
self.head = Node(values[0])
current = self.head
for value in values[1:]:
new_node = Node(value)
current.next = new_node
current = new_node
self.tail = current
# 末尾刪除 O(1)知道尾部, 不知道尾部、任意位置O(n)
def postdelete(self):
if self.head == None:
return
elif self.head.next == None: # 只有一個
self.head = None
self.tail = None
return
else:
tmp = self.head
while tmp.next.next:
tmp = tmp.next
tmp.next = None
self.tail = tmp
return tmp
# 頭部刪除 O(1)
def popdelete(self):
if self.head == None:
return
elif self.head.next == None: # 只有一個
self.head = None
self.tail = None
return
else:
tmp = self.head
self.head = self.head.next
tmp.next = None
return tmp # 返回tmp，之後可以查看被刪掉的值
# 反轉 O(n)
def reverse(self):
if self.head == None:
return
if self.head.next == None:
return
prev = None
curr = self.head
after = curr.next
while after:
curr.next = prev
prev = curr
curr = after
after = after.next
curr.next = prev
self.head = self.tail
# 印出
def print_list(self):
tmp = self.head
while tmp:
print(tmp.data, end=" ")
tmp = tmp.next
if tmp:
print("-> ", end=" ")
print()
if __name__ == "__main__":
linkedlist = LinkedList(values=[1, 2, 3, 6, 7, 8])
linkedlist.print_list()
tmp = linkedlist.postdelete()
print(f"post tmp : {tmp.data}")
linkedlist.print_list()
tmp = linkedlist.popdelete()
print(f"pop tmp : {tmp.data}")
linkedlist.print_list()
linkedlist.reverse()
linkedlist.print_list()
```
<br/>
- Doubly Linked List
```=
# double linked lists
# 知道tail情況下
class Node:
def _init_(self, data) -> None:
self.data = data
self.prev = None
self.next = None
if __name__ == "__main__":
head = Node(data=1)
node1 =Node(data=2)
node2 =Node(data=3)
head.next = node1
node1.prev = head
node1.next = node2
node2.prev = node1
tail = node2
```
```=
class Node:
def __init__(self, data) -> None:
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
# 末尾插入 O(1)
def append(self, value):
new_node = Node(value)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
# 頭部插入 O(1)
def prepend(self, value):
new_node = Node(value)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
# 印出
def print_list(self):
tmp = self.head
while tmp:
print(tmp.data, end=" ")
tmp = tmp.next
if tmp:
print("<-> ", end=" ")
print()
if __name__ == "__main__":
doublylinkedlist = DoublyLinkedList()
doublylinkedlist.append(1)
doublylinkedlist.append(2)
doublylinkedlist.append(3)
doublylinkedlist.print_list()
doublylinkedlist.prepend(4)
doublylinkedlist.print_list()
```
```=
class Node:
def __init__(self, data) -> None:
self.data = data # Correctly store the data
self.prev = None # For doubly linked list
self.next = None # For doubly linked list
class DoublyLinkedList:
def __init__(self, values=None) -> None:
self.head = None
self.tail = None
if values:
self.head = Node(values[0])
current = self.head
for value in values[1:]:
new_node = Node(value)
current.next = new_node
new_node.prev = current # Set the previous pointer for doubly linked list
current = new_node
self.tail = current
# 末尾刪除 O(1)
def postdelete(self):
if self.head is None:
return
elif self.head.next is None: # 只有一個
tmp = self.head
self.head = None
self.tail = None
return tmp
else:
tmp = self.tail
self.tail = self.tail.prev
self.tail.next = None
tmp.prev = None
return tmp # 返回tmp，之後可以查看被刪掉的值
# 頭部刪除 O(1)
def popdelete(self):
if self.head is None:
return
elif self.head.next is None: # 只有一個
tmp = self.head
self.head = None
self.tail = None
return tmp
else:
tmp = self.head
self.head = self.head.next
self.head.prev = None
tmp.next = None
return tmp # 返回tmp，之後可以查看被刪掉的值
# 印出
def print_list(self):
tmp = self.head
while tmp:
print(tmp.data, end=" ")
tmp = tmp.next
if tmp:
print("<-> ", end=" ")
print()
if __name__ == "__main__":
doublylinkedlist = DoublyLinkedList(values=[1, 2, 3, 6, 7, 8])
doublylinkedlist.print_list()
tmp = doublylinkedlist.postdelete()
print(f"Post-deleted node: {tmp.data}")
doublylinkedlist.print_list()
tmp = doublylinkedlist.popdelete()
print(f"Pop-deleted node: {tmp.data}")
doublylinkedlist.print_list()
```
<br/>
## Hash Table 哈希表
### Set集合
set集合，只會顯示不重複值
```=
# python set O(1)
my_set = set()
my_set.add(1)
my_set.add(1)
my_set.add(3.14)
print("Set:", my_set)
```
<br/>
## Stacks and Queues 堆疊和佇列
>Stacks: 先進後出（Last In, First Out，LIFO）。Push： 把元素壓入堆疊的頂部、Pop： 從堆疊的頂部彈出元素
>
>Queues: 先進先出（First In, First Out，FIFO）。Enqueue： 把元素添加到佇列的尾部、Dequeue： 從佇列的頭部移除元素
Stack
```=
# Stack 都O(1)
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self): # 查看頭部
if not self.is_empty():
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
if __name__ == "__main__":
my_stack = Stack()
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
print(my_stack.items)
print()
print("頭部元素:", my_stack.peek())
print()
popped_item = my_stack.pop()
print("彈出的元素:", popped_item)
print("彈出後:", my_stack.items)
print()
print("是否為空:", my_stack.is_empty())
print()
print("堆疊大小:", my_stack.size())
```
Queue
```=
# Queues 都O(1)
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
def peek(self):
if not self.is_empty():
return self.items[0]
else:
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
if __name__ == "__main__":
my_queue = Queue()
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)
print(my_queue.items)
print()
print("頭部元素:", my_queue.peek())
print()
removed_item = my_queue.dequeue()
print("彈出的元素:", removed_item)
print("彈出後:", my_queue.items)
print()
print("是否為空:", my_queue.is_empty())
print()
print("佇列大小:", my_queue.size())
```
<br/>
## Recursion 遞迴
>Recursion: 把一個大問題分解成多個相似但規模較小的子問題，然後遞迴地解決這些子問題，常用於處理樹、鏈表等
>
>通常會使用 call stack，每次都會將新的函數呼叫加入到呼叫堆疊的"頂端"
>
>每個函數呼叫都需要一些記憶體來儲存局部變數、參數和返回地址，這些資訊被儲存在呼叫棧的幀中，當遞歸深度增加時，呼叫棧的大小也會增加
>如果每一層遞歸都是O(1)的時間複雜度，而遞迴深度為log n，整體的時間複雜度就是O(log n)
>
>如果每一層遞歸都是O(1)的時間複雜度，但遞歸深度為n，那麼整體的時間複雜度就是O(n)
>
```=
def factorial(n):
if n == 0 :
return 1
else:
return n * factorial(n - 1)
# 使用遞迴計算階乘
result = factorial(5)
print(result)
```
```=
from typing import Optional # O(n)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
new_head = head
if head.next:
new_head = self.reverseList(head=head.next)
head.next.next = head
head.next = None
return new_head
def print_list(head: Optional[ListNode]) -> None:
current = head
while current:
print(current.val, end=" -> " if current.next else "\n")
current = current.next
```
```=
head = ListNode(val=1,
next=ListNode(val=2,
next=ListNode(val=3,
next=ListNode(val=4,
next=ListNode(val=5)))))
print("Original list:")
print_list(head)
# 反轉
s = Solution()
reversed_head = s.reverseList(head=head)
print("Reversed list:")
print_list(reversed_head)
```
<br/>
## Trees 樹
[參考](https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c)
>tree: 以分層的方式組織和存儲資訊。樹由節點（Node）組成，每個節點包含一個數據元素，並連接到其他節點
<br/>
>根節點（Root Node）： 樹的頂部節點，是樹的唯一起始點
>
>葉節點（Leaf Node）： 沒有子節點的節點，位於樹的最底層
>
>父節點（Parent Node）： 有子節點的節點
>
>子節點（Child Node）： 由父節點指向的節點
>邊(Edge)：樹中兩個節點之間的連線
>
>兄弟姐妹 (Siblings): 具有相同父節點的節點
>
>Level（層級）:樹的第一層從根節點開始，稱為第 1 層。根據樹的結構，每個節點的層級是相對於根節點的深度
>
>深度（Depth）： 一個節點到根節點的唯一路徑上的節點數稱為節點的深度
>
>高度（Height）： 樹中任意節點的深度的最大值被稱為樹的高度
>
>子樹（Subtree）： 由樹中的節點和其所有後代節點構成的樹
>
>二元樹（Binary Tree）： 每個節點最多有兩個子節點的樹 (log n)、O(n)鏈表型
>
>二元搜尋樹(Binary Search Tree) : 左子樹中的所有節點都"小於"該節點，而其右子樹中的所有節點都"大於"該節點。並且不允許有相同值的節點存在，每個節點的值都必須是唯一的 O(log n)、O(n)鏈表型
>
>滿二元樹（Full Binary Tree）: 每個非葉節點的子節點都有兩個子節點，所有葉子節點都在同一層，除了最底層可能不是滿的外，其它每一層的節點數量都是最大可能的 O(log n)
Binary Search Tree
跌代循環查找、遞迴查找
```=
# BST O(logn)
class Node:
def __init__(self, value) -> None:
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self, value) -> None:
self.root = Node(value)
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return True
tmp_root = self.root
while True:
if new_node.value == tmp_root.value:
return False
elif new_node.value < tmp_root.value:
if tmp_root.left is None:
tmp_root.left = new_node
return True
tmp_root = tmp_root.left
else:
if tmp_root.right is None:
tmp_root.right = new_node
return True
tmp_root = tmp_root.right
# 迴圈，適合深度較大的樹，避免因過多的遞迴調用導致記憶體溢出（Stack Overflow）
def search(self, value):
tmp = self.root
while tmp is not None:
if value < tmp.value:
tmp = tmp.left
elif value > tmp.value:
tmp = tmp.right
else:
return True
return False
# 遞迴，根據當前節點的值與目標值的比較結果，遞迴地向左或右子樹搜尋，直到找到目標值或者到達 None
# 遞迴深度過大時，會導致記憶體溢出（Stack Overflow）
def search_r(self, current_root, value):
if current_root is None:
return False
if value == current_root.value:
return True
if value < current_root.value:
return self.search_r(current_root.left, value)
if value > current_root.value:
return self.search_r(current_root.right, value)
if __name__ == "__main__":
bst = BinarySearchTree(10)
bst.insert(5)
bst.insert(15)
print(bst.root.value) # 10
print(bst.root.left.value) # 5
print(bst.root.right.value) # 15
print()
print(bst.search(5)) # True
print(bst.search(12)) # False
print(bst.search_r(bst.root, 15)) # True
print(bst.search_r(bst.root, 8)) # False
```
```=
# 二分搜索 (Binary Search)
# 迴圈
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # 返回目標元素的索引
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 如果目標元素不在數組中，返回 -1
# 遞迴
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1 # 如果範圍無效，返回 -1
mid = (left + right) // 2
if arr[mid] == target:
return mid # 找到目標元素，返回索引
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right) # 搜索右半邊
else:
return binary_search_recursive(arr, target, left, mid - 1) # 搜索左半邊
#
arr = [1, 3, 5, 7, 9, 11, 13]
target = 11
result = binary_search(arr, target)
if result != -1:
print(f"binary_search：Element found at index: {result}")
else:
print("binary_search：Element not found in the array.")
result2 = binary_search_recursive(arr, target, 0, len(arr) - 1)
if result2 != -1:
print(f"binary_search_recursive：Element found at index: {result}")
else:
print("binary_search_recursive：Element not found in the array.")
```
<br/>
## Graphs 圖
>圖（Graph）: 用於表示物體之間的關係。圖由節點（Node）和邊（Edge）組成，圖可以用來模擬各種實際應用，社交網絡、網絡拓撲、路線規劃等
<br/>
>節點（Node）： 也被稱為頂點（Vertex），表示圖中的一個個體
>
>邊（Edge）： 連接兩個節點的線段，表示兩個物體之間的關係
>
>有向圖（Directed Graph）： 邊有方向的圖，從一個節點指向另一個節點
>
>無向圖（Undirected Graph）： 邊沒有方向的圖，邊是雙向的
>
>度（Degree）： 節點相連的邊的數量，對於有向圖分為入度（In-Degree）和出度（Out-Degree）
>
>路徑（Path）： 由節點和邊依次組成的序列
>
>Weighted Graph（權重圖）： 在這種圖中，每條邊都有一個關聯的權重或成本，這種權重可以代表距離、時間、成本等，用於解決需要考慮邊的權重的問題，如最短路徑、最小生成樹
>
>Unweighted Graph（非權重圖）： 在這種圖中，所有的邊都沒有權重或成本，用於表示只關心節點之間是否有連接關係的情況
>
>Cyclic Graph（循環圖）： 包含至少一個環（Cycle）的圖，一個環是一條起點和終點相同的路徑
>
>Acyclic Graph（無環圖）： 不包含任何環的圖，有向無環圖（DAG）是一種特殊的無環圖，它在應用中常常出現，如依賴關係圖
>
>Tree（樹）： 是一種連通的"有向無環圖"，任意兩個節點之間都有唯一的路徑。PS 不是所有的有向無環圖都是樹
<br/>
- 【無向圖】
-- Adjacency Matrix（鄰接矩陣） : 以0 1 表示圖是否有相連
PS 查看關聯較方便
```
A B C D
A 0 1 1 0
B 1 0 1 1
C 1 1 0 0
D 0 1 0 0
```
-- Adjacency List（鄰接表）: 列出有相連的點
PS 存儲空間較少
```
A -> [B, C]
B -> [A, C, D]
C -> [A, B]
D -> [B]
```
- 【有向圖】
-- Adjacency Matrix（鄰接矩陣） : 以0 1 表示圖是否有相連並指向
```=
A B C D
A 0 1 1 0
B 0 0 1 1
C 0 0 0 0
D 0 0 0 0
```
-- Adjacency List（鄰接表）: 列出有相連並指向的點
```=
A -> [B, C]
B -> [C, D]
C -> []
D -> []
```
- 【權重無向圖】
-- Adjacency Matrix（鄰接矩陣） : 以權重數字表示圖是否有相連
```=
A B C D
A 0 1 1 3
B 1 0 0 1
C 1 0 0 2
D 3 1 2 0
```
-- Adjacency List（鄰接表）: 列出有權重數字的點
```=
A: [(B, 1), (C, 1), (D, 3)]
B: [(A, 1), (D, 1)]
C: [(A, 1), (D, 2)]
D: [(A, 3), (B, 1), (C, 2)]
```
- 【權重有向圖】
-- Adjacency Matrix（鄰接矩陣） : 以權重數字表示圖是否有相連並指向
```=
A B C D
A 0 1 1 3
B 0 0 0 1
C 0 0 0 0
D 0 0 2 0
```
-- Adjacency List（鄰接表）: 列出有權重數字並指向的點
```=
A: [(B, 1), (C, 1), (D, 3)]
B: [(D, 1)]
C: []
D: [(C, 2)]
```
#### 添加、刪除
```=
# graph
class Graph():
def __init__(self):
self.adj_list = {}
def print_graph(self):
for node in self.adj_list:
print(node, ":", self.adj_list[node])
# O(1)
def add_node(self, node):
if node not in self.adj_list:
self.adj_list[node] = []
return True
return False
# O(1)
def add_edge(self, n1, n2):
if n1 in self.adj_list and n2 in self.adj_list:
if n2 not in self.adj_list[n1]:
self.adj_list[n1].append(n2)
self.adj_list[n2].append(n1)
return True
return False
# O(2n)/O(n)
def delete_edge(self, n1, n2):
if n1 in self.adj_list and n2 in self.adj_list:
try:
self.adj_list[n1].remove(n2)
self.adj_list[n2].remove(n1)
except:
pass
return True
return False
# O(n*e) * n為節點數、e為邊數
def delete_node(self, node):
if node not in self.adj_list:
return False
for other in self.adj_list[node]:
self.adj_list[other].remove(node)
del self.adj_list[node]
return True
if __name__ == "__main__":
graph = Graph()
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.print_graph()
print()
graph.add_edge('A','B')
graph.add_edge('A','B')
graph.add_edge('A','C')
graph.print_graph()
print()
graph.delete_edge('A','B')
graph.print_graph()
print()
graph.delete_node('A')
graph.print_graph()
```
Sign in with Wallet
Connect another wallet