Введение в структуры данных и алгоритмы с помощью Python

Python предоставляет типы данных, которые обеспечивают гибкий способ доступа и организации множества данных. Они называются структурами данных. Структуры данных — это специализированные средства организации и хранения данных в компьютерах таким образом, чтобы можно было более эффективно выполнять операции над хранимыми данными.
Структура данных — это особый способ организации данных в компьютере таким образом, чтобы их можно было эффективно использовать. Это специализированный формат для организации, обработки, поиска и хранения данных.
Алгоритм же представляет собой набор четко определенных инструкций по вычислению или решению конкретной задачи.

Основные структуры данных в Python включают:

1. Списки
2. Кортежи
3. Наборы
4. Словари

Есть некоторые структуры данных, которые определяются пользователем (не входят в типы данных Python). К ним относятся:

1. стек — LIFO
2. Очереди — FIFO
3. Связанные списки
4. хэш-таблицы
5. Деревья
6. Графы

1. Списки

Список — это значение, которое содержит несколько значений в упорядоченной последовательности. Список начинается с открывающей квадратной скобки и заканчивается закрывающей квадратной скобкой []. Значения внутри списка также называются элементами, которые разделяются запятыми. Например:

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

• Чтобы получить отдельные значения в списке, мы используем индексы. Пример:

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
# subjects[0] will evaluate to Maths
print(subjects[0]) # Maths 
# subjects[1] will evaluate to Physics
print(subjects[0]) # Physics 

Целое число внутри квадратных скобок, которое следует за списком, называется индексом. Первое значение в списке находится под индексом 0, второе — под индексом 1, третье — под индексом 2 и так далее.

ПРИМЕЧАНИЕ: Python выдаст вам сообщение об ошибке IndexError, если вы используете индекс, превышающий количество значений в вашем списке.

• Списки также могут содержать другие списки значений.

food = [['tea', 'coffee', 'water'], ['beef', 'pork', 'mutton', 'fish', 'chicken'], ['rice', 'pasta']]
beverage = food[0]
print(beverage) # ['tea', 'coffee', 'water']
# print individual value
print(food[1][3]) # 'fish'

Первый индекс определяет, какое значение списка использовать, а второй указывает на значение внутри значения списка. Пример:

• отрицательные индексы

Вы также можете использовать отрицательные целые числа для индекса. Целое значение -1 обозначает последний индекс в списке, значение -2 обозначает предпоследний индекс в списке и так далее. Пример:

num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
print(num[-1]) # 0
print(num[-2]) # 9
print(num[-5]) # 6

• Нарезка списка для получения вложенных списковНарезка может получить несколько значений из списка в виде нового списка. Слайс вводится между квадратными скобками, как индекс, но содержит два целых числа, разделенных двоеточием.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[1:4]) # ['Physics', 'Biology', 'Geography']

Первое целое число в срезе — это индекс, с которого начинается срез. Второе целое число — это индекс, которым заканчивается фрагмент, но он не будет включен.

Отсутствие первого индекса равносильно использованию 0 или начала списка. Отсутствие второго индекса равносильно использованию длины списка, что приведет к нарезке до конца списка.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[:3]) # ['Maths', 'Physics', 'Biology']
print(subjects[3:]) # ['Geography', 'History']

• Изменение значений в списке с индексами

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject[0] = 'Mathematics'
print(subject) # ['Mathematics', 'Physics', 'Biology', 'Geography', 'History']

• Добавление двух списков с помощью оператора +

core_subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects = core_subjects + supplementary_subjects
print(subjects)  
['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']

• Дублирование списка с помощью оператора *

num = [1, 3, 5]
print(num*3) # [1, 3, 5, 1, 3, 5, 1, 3, 5]

• Удаление значений из списков с помощью оператора del

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
del subjects[2]
print(subjects) # ['Maths', 'Physics', 'Geography', 'History']

• Использование циклов for со списками

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
for sub in subjects:
    print(sub)

• Операторы in и not inВы можете определить, находится ли значение в списке или нет, с помощью операторов in и not in.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

print('Physics' in subjects) # True

print('Physics' not in subjects) # False

print('Programming' in subjects) # False

print('Programming' not in subjects) # True

• Получение длины списка с помощью len()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(len(subjects))

• Множественное присваивание с помощью списков

Вы можете присвоить нескольким переменным значения из списка в одной строке кода.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
maths, physics, bio, geo, history = subjects
print(geo) # 'Geography'
print (physics) # 'Physics'

• Преобразование типов с помощью функций list()

line1 = 'hello'
line1_list = list(line1)
print(line1_list) # ['h', 'e', 'l', 'l', 'o']

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
subjects = list(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']

Методы списка

append() — Добавляет элемент в конец списка.
clear() — Удаляет все элементы из списка, оставляя его пустым.
copy() — Создает копию списка.
count() — подсчитывает, сколько раз элемент встречается в списке.
extend() — Добавляет элементы из одного списка в конец другого списка.
index() — Возвращает номер индекса (позицию) элемента в списке.
insert() — Вставляет элемент в список на определенную позицию.
pop() — Удаляет элемент из списка и предоставляет копию этого элемента, которую можно сохранить в переменной.
remove() — Удаляет один элемент из списка.
reverse() — изменяет порядок элементов в списке.
sort() — Сортирует список в порядке возрастания. Поместите reverse=True внутрь круглых скобок для сортировки по убыванию.

index()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subject.index('Physics')) # 1

append()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.append('Programming') 
print(subject) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming']

вставить()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.insert('Programming', 1) 
print(subject) # ['Maths', 'Programming', 'Physics', 'Biology', 'Geography', 'History']

удалить()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.remove('Biology') 
print(subject) # ['Maths', 'Physics', 'Geography', 'History']

ПРИМЕЧАНИЕ: Если значение появляется в списке несколько раз, будет удален только первый экземпляр значения.

сортировать()

# Arrange in alphabetical order
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.sort() 
print(subjects) # ['Biology', 'Geography', 'History', 'Maths', 'Physics' ]

# Arrange in numeric order
random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort() # [0, 1, 2, 3, 5, 5, 7, 8, 8]

• Вы также можете передать True для аргумента reverse ключевого слова, чтобы sort() сортировала значения в обратном порядке.

random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort(reverse=True) # [8, 8, 7, 5, 5, 3, 2, 1, 0]

• Вы не можете сортировать списки, в которых есть и числовые, и строковые значения, поскольку Python не знает, как сравнивать эти значения.
• sort() использует «ASCIIbetical order», а не алфавитный порядок для сортировки строк. Это означает, что заглавные буквы идут перед строчными.

spam = ['Alice', 'ants', 'Bob', 'badgers', 'Carol', 'cats']
spam.sort() # ['Alice', 'Bob', 'Carol', 'ants', 'badgers', 'cats']

• вам нужно отсортировать значения в обычном алфавитном порядке, передайте str.lower в качестве аргумента ключевого слова в вызове метода sort().

spam = ['a', 'z', 'A', 'Z']
spam.sort(key=str.lower) # ['a', 'A', 'z', 'Z']

pop()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

# remove last subject
last_subject = subjects.pop()
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography']
print(last_subject) # 'History'

# remove first subject
first_subject = subjects.pop(0)
print(subjects) # ['Physics', 'Biology', 'Geography']
print(first_subject) # 'Maths' 

count()

num = [5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7]
num_count = num.count(5)
print(num_count) # 4

extend()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects.extend(supplementary_subjects)
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']

очистить()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.clear()
print(subjects) # [ ]

reverse()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.reverse()
print(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']

копировать()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject_copy = subjects.copy()
print(subject_copy) # ['Maths', 'Physics', 'Biology', 'Geography', 'History']

2. Кортеж

Кортеж — это просто неизменяемый список. Другими словами, кортеж — это список, но после его определения вы не можете его изменить. Кортежи вводятся с помощью круглых скобок ( и ), а не квадратных скобок [ и ]. Пример:

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
num = (5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7)

Методы списка и техники, которые изменяют данные списка, не будут работать с кортежами, но другие методы будут работать:

print(num.count(5)) # 4
print(type(subjects)) # <class 'tuple'>
print(len(num)) # 12
print('Physics' in subjects) # True

Преобразование в типы кортежей с помощью функций tuple()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects = tuple(subjects)
print(subjects) # ('Maths', 'Physics', 'Biology', 'Geography', 'History')

3. Наборы

Наборы в Python также являются средством организации данных. Разница между набором и списком заключается в том, что элементы в наборе не имеют определенного порядка. Несмотря на то, что вы можете определить набор с элементами в определенном порядке, ни один из элементов не имеет индексных номеров для идентификации своих позиций.

Чтобы определить набор, используйте фигурные скобки там, где вы использовали бы квадратные скобки для списка и круглые скобки для кортежа. Например:

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
num = {5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7}

Вы не можете изменить порядок элементов в наборе, поэтому нельзя использовать .sort() для сортировки набора или .reverse() для изменения его порядка. Вы можете использовать len() для определения размера набора и оператор in для проверки существования элемента.

• add() — Вы можете добавить один новый элемент в набор.

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.add('Programming')
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming'}

• update() — добавление нескольких элементов в набор

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.update(['Programming', 'Sports', 'Communication'])
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication'}

• копировать() — копировать набор

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects_copy = subjects.copy('Programming')
print(subjects_copy) # {'Maths', 'Physics', 'Biology', 'Geography', 'History'}

4. Словарь

Как и список, словарь — это коллекция множества значений, но в отличие от индексов для списков, индексы для словарей могут использовать множество различных типов данных, а не только целые числа. Индексы для словарей называются ключами, а ключ и связанное с ним значение — парой ключ-значение.
В коде словарь обозначается скобками {}. Пример:

person = {
"name": "Elkanah",
"gender": "Male",
"Height": "5.9 Foot",
"Weight": "67 kg",
}

• Вы можете получить доступ к этим значениям через их ключи:

print(person["name"]) # Elkanah
print(person["height"]) # 5.9 Foot

• В отличие от списков, элементы в словарях неупорядочены. Не имеет значения, в каком порядке набираются пары ключ-значение в словаре:

person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person2 = {"Height": "5.9 Foot", "name": "Elkanah", "Weight": "67 kg", "gender": "Male",}

print(person==person1) # True

• Изменение значения ключа в словаре

person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person["name"] = "Malonza"
print(person) # {"name": "Malonza", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}

Методы словаря

clear() — Опустошает словарь, удаляя все ключи и значения.
copy() — Возвращает копию словаря.
fromkeys() — Возвращает новую копию словаря, но только с указанными ключами и значениями.
get() — Возвращает значение указанного ключа, или None, если он не существует.
items() — Возвращает список элементов в виде кортежа для каждой пары ключ-значение.
keys() — Возвращает список всех ключей в словаре.
pop() — Удаляет элемент, указанный ключом, из словаря и сохраняет его в переменной.
popitem() — Удаляет последнюю пару ключ-значение.
setdefault() — Возвращает значение указанного ключа. Если ключ не существует: вставляет ключ с указанным значением.
update() — Обновляет значение существующего ключа или добавляет новую пару ключ-значение, если указанного ключа еще нет в словаре.
values() — Возвращает список всех значений в словаре.

• Методы keys(), values() и items() — возвращают списочные значения ключей, значений или как ключей, так и значений словаря.

spam = {'color': 'red', 'age': 42}

v = spam.values()
print(v) # dict_values(['red', 42])

k = spam.keys()
print(k) # dict_keys(['color', 'age'])

kv = spam.items()
print(kv) # dict_items([('color', 'red'), ('age', 42)])

• Метод get() — принимает два аргумента: ключ значения, которое нужно получить, и запасное значение, которое нужно вернуть, если этот ключ не существует.

picnicItems = {'apples': 5, 'cups': 2}
print(picnicItems.get('cups', 0)) # 2
print(get('cups', 0)) # 2

• Метод setdefault() — устанавливает значение в словаре для определенного ключа, только если у этого ключа еще нет значения.

spam = {'name': 'Pooka', 'age': 5}

spam.setdefault('color', 'black')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.setdefault('color', 'white')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

• Метод update() — добавление нового элемента в словарь или изменение значения текущего ключа.

spam = {'name': 'Pooka', 'age': 5}

spam.update({'color': 'black'})
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.update({'color': 'white'})
print(spam) # {'color': 'white', 'age': 5, name: 'Pooka'}

• метод copy() — создание копии словаря данных для работы с ним.

spam = {'name': 'Pooka', 'age': 5}
spam_copy = spam.copy()
print(spam_copy) # {name: 'Pooka', 'age': 5}

• метод clear() — удалить все пары ключ-значение из словаря, не удаляя весь словарь.

spam = {'name': 'Pooka', 'age': 5}
spam.clear()
print(spam) # {}

• метод pop() — удаляет из словаря элемент, указанный ключом, и сохраняет его в переменной.

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.pop("color")
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # Black

• метод popitem() — Удаление последней пары ключ-значение из словаря.

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.popitem()
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # ('age', 5)

• метод fromkeys() — Возвращает новую копию словаря, но только с указанными ключами и значениями

spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
spam1 = dict.fromkeys(spam.keys())
print(spam1) # {'color': None, 'name': None, 'age': None}

results = dict.fromkeys(['Maths', 'Physics', 'Biology', 'Geography', 'History'])
print(results) # {'Maths': None, 'Physics': None, 'Biology': None, 'Geography': None, 'History': None}

5. Стек

Стек — это линейная структура данных, которая следует принципу Last In First Out (LIFO). Это означает, что последний элемент, вставленный в стек, удаляется. Стек имеет один конец, где происходит вставка и удаление, т.е. с вершины стека.
операции в стековых структурах данных

• push() — вставка (сохранение) элемента в стек
• pop() — удаление (доступ) элемента из стека
• peek() — получить верхний элемент данных стека, не удаляя его.
• isEmpty() — проверить, пуст ли стек.
• isFull() — проверить, заполнен ли стек.

Пример:

# Creating a stack
def stack():
    stack = []
    return stack

# Creating an empty stack
def isEmpty(stack):
    return len(stack) == 0

# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)

# Removing an element from the stack
def pop(stack):
    if (isEmpty(stack)):
        return "stack is empty"
    return stack.pop()

stack = stack()
push(stack, "me")
push(stack, "we")
push(stack, "us")

print("popped item: " + pop(stack))
print("stack after popping an element: ", stack)

'''output
pushed item: me
pushed item: we
pushed item: us
popped item: us
stack after popping an element:  ['me', 'we']
'''

6. Очереди

Очередь — это линейная структура данных, которая следует принципу «первый вошел — первый вышел» (FIFO). Это означает, что первый элемент, вставленный в стек, удаляется первым. Стек имеет два конца, один из которых предназначен для вставки (enqueue), а другой — для удаления (dequeue).

операции в структуре данных очереди

• enqueue() — добавить (сохранить) элемент в очередь.
• dequeue() — удаление (доступ) элемента из очереди.
• peek() — получает элемент, находящийся в начале очереди, не удаляя его.
• isFull() — проверяет, заполнена ли очередь.
• isEmpty() — Проверяет, пуста ли очередь.

Пример:

class Queue:

    def __init__(self):
        self.queue = []

    # Add an element
    def enqueue(self, item):
        self.queue.append(item)

    # Remove an element
    def dequeue(self):
        if len(self.queue) < 1:
            return None

        return self.queue.pop(0)

    # Check the first element in a Queue
    def peek(self):
        if len(self.queue) < 1:
            return None

        return self.queue[0]

    # Check if the Queue is Empty
    def isEmpty(self):
        return len(self.queue) < 1

    # Display  the queue
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)

q = Queue()

q.enqueue(0)
q.enqueue(2)
q.enqueue(0)
q.enqueue(2)
q.enqueue(2)

q.peek()
q.display()

q.dequeue()

print("After removing an element")
q.peek()
q.display()

''' output
0
[0, 2, 0, 2, 2]

After removing an element
2
[2, 0, 2, 2]
'''

7. Связанный список

Связанный список — это линейная структура данных, в которой данные соединены между собой с помощью ссылок. Он состоит из узлов, где каждый узел содержит поле данных и ссылку на следующий узел в списке.

Операции в связном списке

• Вставка — добавляет элемент в начало списка.
• Удаление — Удаляет элемент в начале списка.
• Отобразить — Отображение всего списка.
• Поиск — Поиск элемента по заданному ключу.
• Удалить — удаление элемента с помощью заданной клавиши.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None


class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()
'''output
Mon
Tue
Wed
'''

8. Хэш-таблицы

Хеш-таблица — это структура данных, реализующая абстрактный тип данных ассоциативного массива, структура, которая может сопоставлять ключи со значениями. Хеш-таблица использует хеш-функцию для вычисления индекса, также называемого хеш-кодом, в массиве ведер или слотов, из которых можно найти нужное значение.
В хэш-таблице данные хранятся в формате массива, где каждое значение данных имеет свой уникальный индекс. Доступ к данным становится очень быстрым, если мы знаем индекс нужных данных.

Операции в хэш-таблицах

• Поиск — поиск элемента в хэш-таблице.
• Insert — вставляет элемент в хэш-таблицу.
• Удалить — удаляет элемент из хэш-таблицы.

Пример

hashTable = [[],] * 10

def checkPrime(n):
    if n == 1 or n == 0:
        return 0

    for i in range(2, n//2):
        if n % i == 0:
            return 0

    return 1

def getPrime(n):
    if n % 2 == 0:
        n = n + 1

    while not checkPrime(n):
        n += 2

    return n

def hashFunction(key):
    capacity = getPrime(10)
    return key % capacity

def insertData(key, data):
    index = hashFunction(key)
    hashTable[index] = [key, data]

def removeData(key):
    index = hashFunction(key)
    hashTable[index] = 0

insertData(123, "make a circle")
insertData(456, "a big circle")
insertData(789, "like a sufuria")
print(hashTable)

removeData(123)
print(hashTable)

'''output

[[], [], [123, 'make a circle'], [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

[[], [], 0, [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

'''

9. Деревья

Дерево представляет собой узлы, соединенные ребрами, точнее двоичное дерево или двоичное дерево поиска. Двоичное дерево — это специальная структура данных, используемая для хранения данных. Бинарное дерево имеет специальное условие, согласно которому каждый узел может иметь максимум два дочерних узла.

Термины, используемые в двоичном дереве.

• Путь — Путь относится к последовательности узлов вдоль ребер дерева.
• Корень — Узел на вершине дерева называется корнем. В дереве существует только один корень и один путь от корневого узла к любому узлу.
• Родитель — Любой узел, кроме корневого, имеет одно ребро вверх к узлу, называемому родительским.
• Дочерний узел — узел, расположенный ниже данного узла и соединенный с ним ребром вниз, называется его дочерним узлом.
• Лист — Узел, не имеющий ни одного дочернего узла, называется листовым узлом.
• Поддерево — Поддерево представляет потомков узла.
• Посещение — Посещение означает проверку значения узла, когда управление находится на узле.
• Обход — Обход означает прохождение через узлы в определенном порядке.
• Уровни — Уровень узла представляет собой поколение узла. Если корневой узел находится на уровне 0, то его следующий дочерний узел находится на уровне 1, его внучатый узел — на уровне 2 и так далее.
• Ключи — Ключ представляет собой значение узла, на основе которого будет выполняться операция поиска узла.

Операции в бинарных деревьях

• Вставить — Вставляет элемент в дерево/создает дерево.
• Поиск — поиск элемента в дереве.
• Предварительный обход — обход дерева в предварительном порядке.
• Обход в порядке — обход дерева в порядке очереди.
• Postorder Traversal — обход дерева в порядке следования.

10. Графы

Граф — это наглядное представление набора объектов, в котором некоторые пары объектов соединены связями. Взаимосвязанные объекты представлены точками, называемыми вершинами, а связи, соединяющие вершины, называются ребрами.
Формально, граф — это пара множеств (V, E), где V — множество вершин, а E — множество ребер, соединяющих пары вершин.

Терминология в графах

• Вершина — каждая вершина графа представлена в виде вершины. В следующем примере помеченные круги представляют собой вершины. Таким образом, от A до G являются вершинами. Мы можем представить их с помощью массива, как показано на следующем рисунке. Здесь A можно определить по индексу 0. B может быть идентифицирован индексом 1 и так далее.
• Грани — Грани представляют собой путь между двумя вершинами или линию между двумя вершинами. В следующем примере линии от A к B, от B к C и так далее представляют собой ребра. Мы можем использовать двумерный массив для представления массива, как показано на следующем рисунке. Здесь AB можно представить как 1 в строке 0, столбце 1, BC как 1 в строке 1, столбце 2 и так далее, сохраняя остальные комбинации как 0.
• Смежность — Два узла или вершины являются смежными, если они соединены друг с другом ребром. В следующем примере B является смежной с A, C является смежной с B и так далее.
• Путь — Путь представляет собой последовательность ребер между двумя вершинами. В следующем примере ABCD представляет собой путь от A к D.

Операции в графах

• Добавить вершину — добавляет вершину в граф.
• Добавить ребро — добавляет ребро между двумя вершинами графа.
• Отобразить вершину — отображает вершину графа.