Подсчет шагов между узлами с использованием списка смежности

Question

adj_list={1:[2,4],2:[1,3,4,8],3:[2,6,8,7],4:[1,5,2],5:[4,6],6:[3,9,5],7:[3,8,9,10],8:[2,3,7],9:[6,7,10],10:[7,9]}

def func(x,y):
t=0
xx=x
global i
for i in range(len(adj_list[xx])):
    if y in adj_list[xx]:
        t=t+1
        # print(x,y,t)
        break
    else:
        if xx<y:
            t = t + 1
            xx = xx + 1
    i=0
print(x,y,t)

func(1,6)

I кроме вывода типа:

func(1,10) :1-2-3-7-10(4) or 1-2-8-7-10(4) 

4 не должно быть шагов с 1 по 10

Answer 1

Вы можете использовать networkx для этого.Начните с построения сети, используя keys в качестве узлов и значения как edges.Однако для ребер потребуется немного дополнительной работы, учитывая, что ребра должны быть списками кортежей, содержащих (source_node, dest_node).

Таким образом, способ справиться с этим - получить все значения ключа комбинаций из всех записей в словаре.

Для узлов вам просто потребуется:

nodes = list(adj_list.keys())

Теперь давайте получим список ребер из словаря.Для этого вы можете использовать следующее понимание списка:

edges = [(k,val) for k, vals in adj_list.items() for val in vals]
# [(1, 2), (1, 4), (2, 1), (2, 3), (2, 4)...

Итак, этот список содержит записи в dict в виде простого списка кортежей:

1: [2, 4]         ->    (1, 2), (1, 4)
2: [1, 3, 4, 8]   ->    (2, 1), (2, 3), (2, 4), (2, 8)
...

Теперь давайте построим сетьс соответствующими узлами и ребрами:

import networkx as nx
G=nx.Graph()
G.add_edges_from(edges)
G.add_nodes_from(nodes)

---

Построив сеть, чтобы найти шаги между различными узлами, вы можете использовать shortest_path, что дастВы точно самый короткий путь между двумя заданными узлами.Поэтому, если вы хотите найти кратчайший путь между узлами 1 и 10:

nx.shortest_path(G, 1,10)
# [1, 2, 3, 7, 10]

Если вас интересует длина, просто возьмите len из списка.Давайте посмотрим на другой пример:

nx.shortest_path(G, 1,6)
# [1, 2, 3, 6]

---

Это легче проверить путем непосредственного построения сети:

nx.draw(G, with_labels = True)
plt.show()

---

Где в случае кратчайшего пути между узлами 1 и 10, как можно видеть, промежуточные узлы [1, 2, 3, 7, 10]:

Answer 2

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

def count_steps(current_vertex, destination, steps=0, calling=0):
    """
    Counts the number of steps between two nodes in an adjacent array
    :param current_vertex: Vertex to start looking from
    :param destination: Node we want to count the steps to
    :param steps: Number of steps taken so far (only used from this method, ignore when calling)
    :param calling: The node that called this function (only used from this method, ignore when calling)
    :return: 
    """
    # Start at illegal value so we know it can be changed
    min_steps = -1
    # Check every vertex at the current index
    for vertex in adj_list[current_vertex]:
        if destination in adj_list[current_vertex]:
            # We found the destination in the current array of vertexes
            return steps + 1
        elif vertex > calling:
            # Make sure the vertex we will go to is greater than wherever we want to go so we don't end up in a loop
            counted = count_steps(vertex, destination, steps + 1, current_vertex)
            if counted != -1 and (min_steps == -1 or counted < min_steps):
                # If this is actually the least amount of steps we have found
                min_steps = counted
    return min_steps

Обратите внимание, что когда мы находим место назначения в массиве текущей вершины, мы добавляем его.Это потому, что потребуется еще один шаг, чтобы на самом деле добраться до найденного нами узла.

Answer 3

Если вы ищете наименьшее количество шагов, чтобы добраться от определенного узла к любому другому узлу, я бы предложил Алгоритм Дейкстры .Это не проблема, которая разрешима в одном цикле, она требует очереди значений, которая учитывает самое короткое количество шагов.