learning/python/графы/поиск в ширину.py

# Матрица смежности
# [y][x] - существование пути (ребра) из y в x (опционально - вместо существования bool вес int)
# При нумерации с 1 при этом методе существует несоответствие номеров узлов и индексов (индекс = номер - 1)
graph = (
	(0, 1, 1, 0, 0, 0, 1),
	(1, 0, 1, 1, 0, 0, 0),
	(1, 1, 0, 0, 0, 0, 0),
	(0, 1, 0, 0, 1, 0, 0),
	(0, 0, 0, 1, 0, 1, 0),
	(0, 0, 0, 0, 1, 0, 1),
	(1, 0, 0, 0, 0, 1, 0)
)


# Поиск в ширину

visited_nodes = [0, 0, 0, 0, 0, 0, 0]  # 1 - обнаружена, 2 - посещена

queue = []  # Список узлов, которые нужно посетить
queue.append(0)  # Стартовый узел

while len(queue):  # Пока есть узлы, которые надо посетить
	node1 = queue.pop(0)
	visited_nodes[node1] = 2

	for node2 in range(7):
		if graph[node1][node2] == 1 and visited_nodes[node2] == 0:  # Узел смежный и не обнаружен
			queue.append(node2)
			visited_nodes[node2] = 1



# Поиск кратчайшего пути в невзвешенном графе (из точки 3 в 5)

class Edge:
	def __init__(self, begin, end):
		self.begin = begin
		self.end = end

	def __str__(self):
		return f"Edge({self.begin + 1}, {self.end + 1})"


def find_edges(graph, starting_point, stopping_point):
	visited_nodes = [0, 0, 0, 0, 0, 0, 0]  # 1 - обнаружена, 2 - посещена
	edges = []

	queue = []  # Список узлов, которые нужно посетить
	queue.append(starting_point)  # Стартовый узел
	while len(queue):  # Пока есть узлы, которые надо посетить
		node1 = queue.pop(0)
		visited_nodes[node1] = 2
		print('Checking node %s' % node1)

		for node2 in range(7):
			print(f'Checking path to {node2}')
			if graph[node1][node2] == 1 and visited_nodes[node2] == 0:  # Узел смежный и не обнаружен
				print('Path exists and is undetected. Saving')

				queue.append(node2)
				visited_nodes[node2] = 1
				edges.append(Edge(node1, node2))

				if node2 == stopping_point:
					print('Found stop, returning')
					return edges

	return edges


start = 2
req = 4
edges = find_edges(graph, start, req)

print('\nResulting list: ')
for i in edges:
	print(i)

print("\nPath:")
while len(edges):
	edge = edges.pop(-1)
	if edge.end == req:
		req = edge.begin
		print(edge)




# ==================================================================



# Список смежности
# ключ - номер узла, значение - список узлов, с которыми есть связь
print('\n\n\n\n\n\nСписок смежности')

graph = {
	1: (2, 3, 7),
	2: (1, 3, 4),
	3: (1, 2),
	4: (2, 5),
	5: (4, 6),
	6: (5, 7),
	7: (1, 6)
}


# Поиск в ширину
visited_nodes = [0, 0, 0, 0, 0, 0, 0]  # 1 - обнаружена, 2 - посещена

queue = []
queue.append(1)

while len(queue):
	node1 = queue.pop()
	visited_nodes[node1 - 1] = 2

	for node2 in graph.get(node1):
		# Проверка на смежность в этом методе не нужна, потому что в списке уже содержатся смежные узлы.
		if visited_nodes[node2 - 1] == 0:
			visited_nodes[node2 - 1] = 1
			queue.append(node2)



# Поиск кратчайшего пути в невзвешенном графе (из точки 3 в 5)

class Edge:
	def __init__(self, begin, end):
		self.begin = begin
		self.end = end

	def __str__(self):
		return f"Edge({self.begin}, {self.end})"


def find_edges(graph, starting_point, stopping_point):
	visited_nodes = [0, 0, 0, 0, 0, 0, 0]  # 1 - обнаружена, 2 - посещена

	queue = []
	queue.append(starting_point)
	edges = []

	while len(queue):
		node1 = queue.pop(0)
		visited_nodes[node1 - 1] = 2
		print(f'Checking node {node1}')

		for node2 in graph.get(node1):
			print(f'Checking existing path to {node2}')
			# Проверка на смежность в этом методе не нужна, потому что в списке уже содержатся смежные узлы.
			if visited_nodes[node2 - 1] == 0:
				print('Path is undetected. Saving')

				visited_nodes[node2 - 1] = 1
				queue.append(node2)
				edges.append(Edge(node1, node2))

				if node2 == stopping_point:
					print('Found stop, returning')
					return edges

	return edges


start = 3
req = 5
edges = find_edges(graph, start, req)
print('\nResulting list: ')
for i in edges:
	print(i)

print("\nPath:")
while len(edges):
	edge = edges.pop(-1)
	if edge.end == req:
		req = edge.begin
		print(edge)