Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import time
- def dfs(g, ex, node):
- print("Входим в вершину " + str(node + 1))
- print('Помечаем вершину ' + str(node + 1))
- ex.add(node)
- for i in range(len(g)):
- if g[node][i] == 1 and i not in ex:
- dfs(g, ex, i)
- print('Возвращаемся в вершину ' + str(node + 1))
- if __name__ == '__main__':
- print('Привет! Эта программа служит для обхода графа в глубину.\nЧтобы выйти, введите q на любом этапе\n')
- buffer = ''
- g_count = 0
- e_count = 0
- g = []
- ex = set()
- while True:
- buffer = input('Введите количество вершин:\n')
- if buffer.lower() == 'q':
- break
- try:
- g_count = int(buffer)
- except ValueError:
- print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
- continue
- if g_count <= 0:
- print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
- continue
- g = [[0 for j in range(0, g_count)] for i in range(0, g_count)]
- buffer = input('Введите количество ребер:\n')
- if buffer.lower() == 'q':
- break
- try:
- e_count = int(buffer)
- except ValueError:
- print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
- continue
- if e_count <= 0:
- print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
- continue
- buffer = input('Граф ориентированный? (Y/N):\n')
- if buffer.lower() == 'q':
- break
- is_oriented = buffer.lower() == 'y'
- print('\nВводите связанные ребра:')
- flag = False
- for i in range(0, e_count):
- buffer = input()
- if buffer.lower() == 'q':
- break
- try:
- a, b = map(int, buffer.split())
- except ValueError:
- print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
- flag = True
- break
- if a <= 0 or b <= 0 or a > g_count or b > g_count:
- print('Вы ввели неверные данные! Пожалуйста, попробуйте снова.\n')
- flag = True
- break
- a -= 1
- b -= 1
- g[a][b] = 1
- if not is_oriented:
- g[b][a] = 1
- if flag:
- continue
- start = 0
- buffer = input('С какой вершины начинать обход:\n')
- if buffer.lower() == 'q':
- break
- try:
- start = int(buffer)
- except ValueError:
- print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
- continue
- if start <= 0 or start > g_count:
- print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
- continue
- start -= 1
- print('Получившаяся матрица смежности:')
- for i in g:
- print((len(i) * '{:d} ').format(*i))
- print('')
- start_time = time.time_ns()
- dfs(g, ex, start)
- end_time = time.time_ns()
- print('Затраченное ввремя - ' + str((end_time - start_time) / 1000000) + 'мс.\n\n')
- print('Спасибо!')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement