Способи задання графів

Хмельницький національний університет

Факультет інформаційних технологій

Кафедра кібербезпеки

ЛАБОРАТОРНА РОБОТА № 7

Дисципліна Алгоритми та структури даних

Спеціальність                               125 –Кібербезпека                                   

на тему Способи задання графів.

ЛРКБЗІ.7512376.24.01.02 ПЗ

Виконав:  студентка 2 курсу,  група КБЗІ-24-1                 Євгенія ПРОКОПЕНКО

                                                        Підпис                     Ініціали, прізвище

Перевірив:                                                               ______         Ігор МУЛЯР

                                           Науковий ступінь, вчене звання                      Підпис                  Ініціали, прізвище

Хмельницький 2026

Мета: Набуття практичних вмінь і навичок при представленні заданих графів різними способами та можливістю їх комп’ютерної реалізації.

Варіант 2

Завдання до лабораторної роботи

1.12 Задано речення. Скласти програму, яка визначає і виводить на екран речення, в якому слова розташовані в зворотному порядку.

Для неорієнтованих та орієнтованих графів зі своїх варіантів (варіант вибирається згідно номера по журналу, варіанти завдань наведено у додатку) виконати наступні завдання:

1. Створити програму, яка буде зберігати в комп’ютері заданий орієнтований і неорієнтований граф наступними способами: - - - а) матрицею суміжності в) списком ребер г) списком суміжності. Передбачити зчитування графу з клавіатури у вигляді списку ребер іменованих вершин. Передбачити вивід кожного представлення у файл та на екран.

2. Написати програму, яка виконуватиме наступні завдання: - за заданою матрицею суміжності, зчитаною з файлу побудувати список суміжності; - за заданою матрицею суміжності, зчитаною з файлу побудувати список ребер;

3. Виконати обходи графів в глибину з використанням стеку (для непарних варіантів) та в ширину з використанням черги (для парних варіантів). Номер варіанту вибирати згідно номера по журналу.

Завдання 1 Варіант 2

import sys
from collections import deque

class GraphLab:
   def __init__(self, directed=False):
       self.directed = directed
       self.vertices = []
       self.edges = []
       self.adj_matrix = []
       self.adj_list = {}
       self.vertex_map = {}

   def input_graph_from_edges(self):
       print("Введіть ребра у форматі 'v1 v2' (наприклад, 'a b').")
       print("Для завершення введення натисніть Enter на порожньому рядку.")

       raw_edges = []
       unique_vertices = set()

       while True:
           try:
               line = input()
               if not line.strip():
                   break
               parts = line.split()
               if len(parts) == 2:
                   u, v = parts
                   raw_edges.append((u, v))
                   unique_vertices.add(u)
                   unique_vertices.add(v)
           except EOFError:
               break

       self.vertices = sorted(list(unique_vertices))
       self.edges = raw_edges

       self.vertex_map = {v: i for i, v in enumerate(self.vertices)}

       self.build_adj_matrix()
       self.build_adj_list_from_edges()

   def build_adj_matrix(self):
       n = len(self.vertices)
       self.adj_matrix = [[0] * n for _ in range(n)]

       for u, v in self.edges:
           i = self.vertex_map[u]
           j = self.vertex_map[v]

           self.adj_matrix[i][j] = 1

           if not self.directed:
               self.adj_matrix[j][i] = 1

   def build_adj_list_from_edges(self):
       self.adj_list = {v: set() for v in self.vertices}
       for u, v in self.edges:
           self.adj_list[u].add(v)
           if not self.directed and u != v:
               self.adj_list[v].add(u)

       for v in self.adj_list:
           self.adj_list[v] = sorted(list(self.adj_list[v]))

   def save_representations(self, filename="graph_output.txt"):
       output = []
       output.append("-" * 20)
       output.append(f"Тип графа: {'Орієнтований' if self.directed else 'Неорієнтований'}")
       output.append("-" * 20)

       output.append("\n1. Список ребер:")
       for u, v in self.edges:
           output.append(f"({u}, {v})")

       output.append("\n2. Матриця суміжності:")
       output.append("  " + " ".join(self.vertices))
       for i, row in enumerate(self.adj_matrix):
           row_str = " ".join(map(str, row))
           output.append(f"{self.vertices[i]} {row_str}")

       output.append("\n3. Список суміжності:")
       for v in self.vertices:
           neighbors = ", ".join(self.adj_list.get(v, []))
           output.append(f"{v}: [{neighbors}]")

       full_text = "\n".join(output)
       print(full_text)

       with open(filename, "w", encoding="utf-8") as f:
           f.write(full_text)
       print(f"\n[Info] Дані збережено у файл {filename}")

       with open("matrix_only.txt", "w") as f:
           f.write(" ".join(self.vertices) + "\n")
           for row in self.adj_matrix:
               f.write(" ".join(map(str, row)) + "\n")

   def task2_convert_from_matrix_file(self, filename="matrix_only.txt"):
       print(f"\n--- Завдання 2: Зчитування матриці з файлу {filename} ---")
       try:
           with open(filename, "r") as f:
               lines = f.readlines()

           names = lines[0].strip().split()
           matrix = []
           for line in lines[1:]:
               if line.strip():
                   matrix.append(list(map(int, line.strip().split())))

           print("Матрицю зчитано успішно.")

           print("\nа) Побудова списку суміжності з матриці:")
           new_adj_list = {}
           for i in range(len(names)):
               u = names[i]
               neighbors = []
               for j in range(len(names)):
                   if matrix[i][j] == 1:
                       neighbors.append(names[j])
               new_adj_list[u] = neighbors
               print(f"{u}: {neighbors}")

           print("\nб) Побудова списку ребер з матриці:")
           new_edge_list = []
           n = len(names)

           for i in range(n):
               for j in range(n):
                   if matrix[i][j] == 1:
                       if not self.directed:
                           if i <= j:
                               new_edge_list.append((names[i], names[j]))
                       else:
                           new_edge_list.append((names[i], names[j]))

           print(new_edge_list)

       except FileNotFoundError:
           print("Файл з матрицею не знайдено. Спочатку виконайте Завдання 1.")

   def bfs(self, start_node):

       print(f"\n--- Завдання 3: BFS (Пошук в ширину) починаючи з {start_node} ---")

       if start_node not in self.vertices:
           print("Помилка: такої вершини немає в графі.")
           return

       visited = set()
       queue = deque([start_node])
       visited.add(start_node)

       traversal_order = []

       print(f"{'Крок':<5} | {'Вершина':<10} | {'Черга':<30}")
       print("-" * 50)

       step = 1
       while queue:
           q_str = str(list(queue))

           current = queue.popleft()
           traversal_order.append(current)

           print(f"{step:<5} | {current:<10} | {q_str:<30}")

           neighbors = self.adj_list[current]

           for neighbor in neighbors:
               if neighbor not in visited:
                   visited.add(neighbor)
                   queue.append(neighbor)

           step += 1

       print(f"\nРезультат обходу BFS: {traversal_order}")


if __name__ == "__main__":
   print("Варіант 2. Лабораторна робота №7.")

   ctype = input("Оберіть граф (1 - Неорієнтований, 2 - Орієнтований): ")
   is_directed = True if ctype == '2' else False

   graph = GraphLab(directed=is_directed)

   graph.input_graph_from_edges()
   graph.save_representations()

   graph.task2_convert_from_matrix_file()

   start_v = input("\nВведіть початкову вершину для BFS (наприклад, 'a'): ")
   graph.bfs(start_v)