Как найти цикл в графе python - Сайт, где вы сможете решить свои вопросы

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Python

from collections import defaultdict

class Graph():

def __init__(self, vertices):

self.graph = defaultdict(list)

self.V = vertices

def addEdge(self, u, v):

self.graph[u].append(v)

def isCyclicUtil(self, v, visited, recStack):

visited[v] = True

recStack[v] = True

for neighbour in self.graph[v]:

if visited[neighbour] == False:

if self.isCyclicUtil(neighbour, visited, recStack) == True:

return True

elif recStack[neighbour] == True:

return True

recStack[v] = False

return False

def isCyclic(self):

visited = [False] * self.V

recStack = [False] * self.V

for node in range(self.V):

if visited[node] == False:

if self.isCyclicUtil(node, visited, recStack) == True:

return True

return False

g = Graph(4)

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

if g.isCyclic() == 1:

print "Graph has a cycle"

else:

print "Graph has no cycle"

Please refer complete article on Detect Cycle in a Directed Graph for more details!

Last Updated :
19 Apr, 2023

Like Article

Save Article

Источник

My own implementation (non-recursive so without cycle length limit):

from collections import defaultdict


def has_cycle(graph):
    try:
        next(_iter_cycles(graph))
    except StopIteration:
        return False
    return True


def _iter_cycles(edges):
    """Iterate over simple cycles in the directed graph."""
    if isinstance(edges, dict):
        graph = edges
    else:
        graph = defaultdict(set)
        for x, y in edges:
            graph[x].add(y)
    SEP = object()
    checked_nodes = set()  # already checked nodes
    for start_node in graph:
        if start_node in checked_nodes:
            continue
        nodes_left = [start_node]
        path = []         # current path from start_node
        node_idx = {}     # {node: path.index(node)}
        while nodes_left:
            node = nodes_left.pop()
            if node is SEP:
                checked_node = path.pop()
                del node_idx[checked_node]
                checked_nodes.add(checked_node)
                continue
            if node in checked_nodes:
                continue
            if node in node_idx:
                cycle_path = path[node_idx[node]:]
                cycle_path.append(node)
                yield cycle_path
                continue
            next_nodes = graph.get(node)
            if not next_nodes:
                checked_nodes.add(node)
                continue
            node_idx[node] = len(path)
            path.append(node)
            nodes_left.append(SEP)
            nodes_left.extend(next_nodes)


assert not has_cycle({0: [1, 2], 1: [3, 4], 5: [6, 7]})
assert has_cycle([(0, 1), (1, 0), (1, 2), (2, 1)])


def assert_cycles(graph, expected):
    detected = sorted(_iter_cycles(graph))
    if detected != expected:
        raise Exception('expected cycles:n{}ndetected cycles:n{}'.format(expected, detected))


assert_cycles([('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')], [['C', 'D', 'C']])
assert_cycles([('A', 'B'),('B', 'A'),('B', 'C'),('C', 'B')], [['A', 'B', 'A'], ['B', 'C', 'B']])

assert_cycles({1: [2, 3], 2: [3, 4]}, [])
assert_cycles([(1, 2), (1, 3), (2, 3), (2, 4)], [])

assert_cycles({1: [2, 4], 2: [3, 4], 3: [1]}, [[1, 2, 3, 1]])
assert_cycles([(1, 2), (1, 4), (2, 3), (2, 4), (3, 1)], [[1, 2, 3, 1]])

assert_cycles({0: [1, 2], 2: [3], 3: [4], 4: [2]}, [[2, 3, 4, 2]])
assert_cycles([(0, 1), (0, 2), (2, 3), (3, 4), (4, 2)], [[2, 3, 4, 2]])

assert_cycles({1: [2], 3: [4], 4: [5], 5: [3]}, [[3, 4, 5, 3]])
assert_cycles([(1, 2), (3, 4), (4, 5), (5, 3)], [[3, 4, 5, 3]])

assert_cycles({0: [], 1: []}, [])
assert_cycles([], [])

assert_cycles({0: [1, 2], 1: [3, 4], 5: [6, 7]}, [])
assert_cycles([(0, 1), (0, 2), (1, 3), (1, 4), (5, 6), (5, 7)], [])

assert_cycles({0: [1], 1: [0, 2], 2: [1]}, [[0, 1, 0], [1, 2, 1]])
assert_cycles([(0, 1), (1, 0), (1, 2), (2, 1)], [[0, 1, 0], [1, 2, 1]])

EDIT:

I found that while has_cycle seems to be correct,
the _iter_cycles does not iterate over all cycles!

Example in which _iter_cycles does not find all cycles:

assert_cycles([
        (0, 1), (1, 2), (2, 0),  # Cycle 0-1-2
        (0, 2), (2, 0),          # Cycle 0-2
        (0, 1), (1, 4), (4, 0),  # Cycle 0-1-4
    ],
    [
        [0, 1, 2, 0],  # Not found (in Python 3.7)!
        [0, 1, 4, 0],
        [0, 2, 0],
    ]
)

Источник

Для заданного связного неориентированного Graph проверьте, содержит ли он какой-либо цикл или нет.

Например, следующий graph содержит цикл 2–5–10–6–2:

Потренируйтесь в этой проблеме

Рекомендуем прочитать:

Типы ребер, участвующих в DFS, и связь между ними

1. Использование БФС

Когда мы делаем Поиск в ширину (BFS) из любой вершины v в неориентированном Graph мы можем встретить крест-накрест который указывает на ранее обнаруженную вершину, которая не является ни предком, ни потомком текущей вершины. Каждое “поперечное ребро” определяет цикл в неориентированном Graph. Если поперечный край x —> y, то так как y уже обнаружен, у нас есть путь от v к y (или из y к v так как graph неориентированный), где v является начальной вершиной BFS. Итак, мы можем сказать, что у нас есть путь v ~~ x ~ y ~~ v что образует цикл. (Здесь, ~~ представляет еще одно ребро в пути, и ~ представляет собой прямое ребро).

Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

C++

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

// Структура данных для хранения ребра Graph

struct Edge {

int src, dest;

};

// Класс для представления graphического объекта

class Graph

{

public:

// вектор векторов для представления списка смежности

vector<vector<int>> adjList;

// Конструктор Graphа

Graph(vector<Edge> const &edges, int n)

{

// изменить размер вектора, чтобы он содержал `n` элементов типа `vector<int>`

adjList.resize(n);

// добавляем ребра в неориентированный graph

for (auto &edge: edges)

{

adjList[edge.src].push_back(edge.dest);

adjList[edge.dest].push_back(edge.src);

}

};

// Узел для хранения информации о вершинах и их родителях в BFS

struct Node {

int v, parent;

};

// Выполнить BFS на Graph, начиная с вершины `src` и

// возвращаем true, если цикл найден в Graph

bool BFS(Graph const &graph, int src, int n)

{

// чтобы отслеживать, открыта вершина или нет

vector<bool> discovered(n);

// помечаем исходную вершину как обнаруженную

discovered[src] = true;

// создаем queue для выполнения BFS и

// поставить исходную вершину в queue

queue<Node> q;

q.push({src, –1});

// цикл до тех пор, пока queue не станет пустой

while (!q.empty())

{

// удаляем передний узел из очереди и печатаем его

Node node = q.front();

q.pop();

// делаем для каждого ребра (v, u)

for (int u: graph.adjList[node.v])

{

if (!discovered[u])

{

// помечаем как обнаруженное

discovered[u] = true;

// создаем узел queue, содержащий информацию

// о вершине и поставить ее в queue

q.push({ u, node.v });

}

// `u` обнаружен, а `u` не является родителем

else if (u != node.parent)

{

// мы нашли пересечение, т.е. цикл найден

return true;

}

// пересечений в Graph не обнаружено

return false;

}

int main()

{

// инициализируем ребра

vector<Edge> edges =

{

{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {4, 8},

{4, 9}, {3, 6}, {3, 7}, {6, 10}, {6, 11}, {5, 9}

// ребро {5, 9} вводит в graph цикл

};

// общее количество узлов в Graph (от 0 до 11)

int n = 12;

// строим graph из заданных ребер

Graph graph(edges, n);

// Выполняем обход BFS в связных компонентах Graph

if (BFS(graph, 0, n)) {

cout << “The graph contains a cycle”;

}

else {

cout << “The graph doesn’t contain any cycle”;

}

return 0;

}

Скачать Выполнить код

результат:

The graph contains a cycle

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

import java.util.*;

// Класс для хранения ребра Graph

class Edge

{

int source, dest;

public Edge(int source, int dest)

{

this.source = source;

this.dest = dest;

}

// Класс для представления graphического объекта

class Graph

{

// Список списков для представления списка смежности

List<List<Integer>> adjList = null;

// Конструктор

Graph(List<Edge> edges, int n)

{

adjList = new ArrayList<>();

for (int i = 0; i < n; i++) {

adjList.add(new ArrayList<>());

}

// добавляем ребра в неориентированный graph

for (Edge edge: edges)

{

int src = edge.source;

int dest = edge.dest;

adjList.get(src).add(dest);

adjList.get(dest).add(src);

}

// Узел для хранения информации о вершинах и их родителях в BFS

class Node

{

int v, parent;

Node(int v, int parent)

{

this.v = v;

this.parent = parent;

}

class Main

{

// Выполнить BFS на Graph, начиная с вершины `src` и

// возвращаем true, если цикл найден в Graph

public static boolean BFS(Graph graph, int src, int n)

{

// чтобы отслеживать, открыта вершина или нет

boolean[] discovered = new boolean[n];

// помечаем исходную вершину как обнаруженную

discovered[src] = true;

// создаем queue для выполнения BFS и

// поставить исходную вершину в queue

Queue<Node> q = new ArrayDeque<>();

q.add(new Node(src, –1));

// цикл до тех пор, пока queue не станет пустой

while (!q.isEmpty())

{

// удаляем передний узел из очереди и печатаем его

Node node = q.poll();

// делаем для каждого ребра (v, u)

for (int u: graph.adjList.get(node.v))

{

if (!discovered[u])

{

// помечаем как обнаруженное

discovered[u] = true;

// создаем узел queue, содержащий информацию

// о вершине и поставить ее в queue

q.add(new Node(u, node.v));

}

// `u` обнаружен, а `u` не является родителем

else if (u != node.parent)

{

// мы нашли пересечение, т.е. цикл найден

return true;

}

// пересечений в Graph не обнаружено

return false;

}

public static void main(String[] args)

{

// Список ребер Graph

List<Edge> edges = Arrays.asList(

new Edge(0, 1), new Edge(0, 2), new Edge(0, 3),

new Edge(1, 4), new Edge(1, 5), new Edge(4, 8),

new Edge(4, 9), new Edge(3, 6), new Edge(3, 7),

new Edge(6, 10), new Edge(6, 11), new Edge(5, 9)

// ребро (5, 9) вводит в graph цикл

);

// общее количество узлов в Graph (от 0 до 11)

int n = 12;

// строим graph из заданных ребер

Graph graph = new Graph(edges, n);

// Выполняем обход BFS в связных компонентах Graph

if (BFS(graph, 0, n)) {

System.out.println(“The graph contains a cycle”);

}

else {

System.out.println(“The graph doesn’t contain any cycle”);

}

Скачать Выполнить код

результат:

The graph contains a cycle

Python

from collections import deque

# Класс для представления graphического объекта

class Graph:

# 1ТП4Т Конструктор

def __init__(self, edges, n):

# Список списков для представления списка смежности

self.adjList = [[] for _ in range(n)]

# добавляет ребра в неориентированный graph

for (src, dest) in edges:

self.adjList[src].append(dest)

self.adjList[dest].append(src)

# Выполнить BFS на Graph, начиная с вершины `src` и

# возвращает true, если цикл найден в Graph

def BFS(graph, src, n):

# для отслеживания обнаружена вершина или нет

discovered = [False] * n

# пометить исходную вершину как обнаруженную

discovered[src] = True

# создать queue для выполнения BFS

q = deque()

# ставит в queue исходную вершину и ее родительскую информацию

q.append((src, –1))

# Цикл # до тех пор, пока queue не станет пустой

while q:

# удалить передний узел из очереди и распечатать его

(v, parent) = q.popleft()

# делаем для каждого ребра (v, u)

for u in graph.adjList[v]:

if not discovered[u]:

# пометить как обнаруженный

discovered[u] = True

# построить узел queue, содержащий информацию

# о вершине и поставить ее в queue

q.append((u, v))

# `u` обнаружен, а `u` не является родителем

elif u != parent:

# мы нашли перекрестное ребро, т.е. найден цикл

return True

# пересечений на Graphе не обнаружено

return False

if __name__ == ‘__main__’:

# Список ребер Graph

edges = [

(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (4, 8),

(4, 9), (3, 6), (3, 7), (6, 10), (6, 11), (5, 9)

# Ребро # (5, 9) вводит цикл в graph

]

# общее количество узлов в Graph (от 0 до 11)

n = 12

# строит graph по заданным ребрам

graph = Graph(edges, n)

# Выполнение обхода BFS в связанных компонентах Graph

if BFS(graph, 0, n):

print(‘The graph contains a cycle’)

else:

print(‘The graph doesn’t contain any cycle’)

Скачать Выполнить код

результат:

The graph contains a cycle

2. Использование ДФС

Следующий graph содержит цикл 8—9—11—12—8:

Когда мы делаем Поиск в глубину (DFS) из любой вершины v в неориентированном Graph мы можем встретить задний край который указывает на одного из предков текущей вершины v в дереве ДФС. Каждое “заднее ребро” определяет цикл в неориентированном Graph. Если задний край x —> y, то так как y является предком узла x, у нас есть путь от y к x. Итак, мы можем сказать, что у нас есть путь y ~~ x ~ y что образует цикл. (Здесь, ~~ представляет еще одно ребро в пути, и ~ представляет собой прямое ребро).

Ниже приведена реализация на C++, Java и Python, основанная на приведенной выше идее:

C++

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

// Структура данных для хранения ребра Graph

struct Edge {

int src, dest;

};

// Класс для представления graphического объекта

class Graph

{

public:

// вектор векторов для представления списка смежности

vector<vector<int>> adjList;

// Конструктор Graphа

Graph(vector<Edge> const &edges, int n)

{

// изменить размер вектора, чтобы он содержал `n` элементов типа `vector<int>`

adjList.resize(n);

// добавляем ребра в неориентированный graph

for (auto &edge: edges)

{

adjList[edge.src].push_back(edge.dest);

adjList[edge.dest].push_back(edge.src);

}

};

// Выполняем поиск в глубину на Graph и возвращаем true, если на Graph найдено какое-либо обратное ребро

bool DFS(Graph const &graph, int v, vector<bool> &discovered, int parent)

{

// помечаем текущий узел как обнаруженный

discovered[v] = true;

// делаем для каждого ребра (v, w)

for (int w: graph.adjList[v])

{

// если `w` не обнаружен

if (!discovered[w])

{

if (DFS(graph, w, discovered, v)) {

return true;

}

// если `w` обнаружен, а `w` не является родителем

else if (w != parent)

{

// мы нашли обратное ребро (цикл)

return true;

}

// Обратных ребер на Graphе не обнаружено

return false;

}

int main()

{

// инициализируем ребра

vector<Edge> edges =

{

{0, 1}, {0, 6}, {0, 7}, {1, 2}, {1, 5}, {2, 3},

{2, 4}, {7, 8}, {7, 11}, {8, 9}, {8, 10}, {10, 11}

// ребро (10, 11) вводит в graph цикл

};

// общее количество узлов в Graph (от 0 до 11)

int n = 12;

// строим graph из заданных ребер

Graph graph(edges, n);

// чтобы отслеживать, открыта вершина или нет

vector<bool> discovered(n);

// Выполняем обход в глубину из первой вершины

if (DFS(graph, 0, discovered, –1)) {

cout << “The graph contains a cycle”;

}

else {

cout << “The graph doesn’t contain any cycle”;

}

return 0;

}

Скачать Выполнить код

результат:

The graph contains a cycle

Java

100

101

import java.util.*;

// Класс для хранения ребра Graph

class Edge

{

int source, dest;

public Edge(int source, int dest)

{

this.source = source;

this.dest = dest;

}

// Класс для представления graphического объекта

class Graph

{

// Список списков для представления списка смежности

List<List<Integer>> adjList = null;

// Конструктор

Graph(List<Edge> edges, int n)

{

adjList = new ArrayList<>(n);

for (int i = 0; i < n; i++) {

adjList.add(i, new ArrayList<>());

}

// добавляем ребра в неориентированный graph

for (Edge edge: edges)

{

int src = edge.source;

int dest = edge.dest;

adjList.get(src).add(dest);

adjList.get(dest).add(src);

}

class Main

{

// Функция для обхода DFS на Graphе на Graphе

public static boolean DFS(Graph graph, int v, boolean[] discovered, int parent)

{

// помечаем текущий узел как обнаруженный

discovered[v] = true;

// делаем для каждого ребра (v, w)

for (int w: graph.adjList.get(v))

{

// если `w` не обнаружен

if (!discovered[w])

{

if (DFS(graph, w, discovered, v)) {

return true;

}

// если `w` обнаружен, а `w` не является родителем

else if (w != parent)

{

// мы нашли обратное ребро (цикл)

return true;

}

// Обратных ребер на Graphе не обнаружено

return false;

}

public static void main(String[] args)

{

// Список ребер Graph

List<Edge> edges = Arrays.asList(

new Edge(0, 1), new Edge(0, 6), new Edge(0, 7),

new Edge(1, 2), new Edge(1, 5), new Edge(2, 3),

new Edge(2, 4), new Edge(7, 8), new Edge(7, 11),

new Edge(8, 9), new Edge(8, 10), new Edge(10, 11)

// ребро (10, 11) вводит в graph цикл

);

// общее количество узлов в Graph (от 0 до 11)

int n = 12;

// строим graph из заданных ребер

Graph graph = new Graph(edges, n);

// чтобы отслеживать, открыта вершина или нет

boolean[] discovered = new boolean[n];

// Выполняем обход в глубину из первой вершины

if (DFS(graph, 0, discovered, –1)) {

System.out.println(“The graph contains a cycle”);

}

else {

System.out.println(“The graph doesn’t contain any cycle”);

}

Скачать Выполнить код

результат:

The graph contains a cycle

Python

# Класс для представления graphического объекта

class Graph:

# 1ТП4Т Конструктор

def __init__(self, edges, n):

# Список списков для представления списка смежности

self.adjList = [[] for _ in range(n)]

# добавляет ребра в неориентированный graph

for (src, dest) in edges:

self.adjList[src].append(dest)

self.adjList[dest].append(src)

# Функция для обхода DFS на Graphе на Graphе

def DFS(graph, v, discovered, parent=–1):

# пометить текущий узел как обнаруженный

discovered[v] = True

# делаем для каждого ребра (v, w)

for w in graph.adjList[v]:

#, если `w` не обнаружен

if not discovered[w]:

if DFS(graph, w, discovered, v):

return True

#, если `w` обнаружен, а `w` не является родителем

elif w != parent:

# мы нашли задний край (цикл)

return True

# Обратных ребер на Graphе не обнаружено

return False

if __name__ == ‘__main__’:

# Список ребер Graph

edges = [

(0, 1), (0, 6), (0, 7), (1, 2), (1, 5), (2, 3),

(2, 4), (7, 8), (7, 11), (8, 9), (8, 10), (10, 11)

# Ребро # (10, 11) вводит цикл в graph

]

# общее количество узлов в Graph (от 0 до 11)

n = 12

# строит graph по заданным ребрам

graph = Graph(edges, n)

# для отслеживания обнаружена вершина или нет

discovered = [False] * n

# Выполнить обход DFS из первой вершины

if DFS(graph, 0, discovered):

print(‘The graph contains a cycle’)

else:

print(‘The graph doesn’t contain any cycle’)

Скачать Выполнить код

результат:

The graph contains a cycle

Временная сложность приведенных выше решений равна O(V + E), куда V а также E – общее количество вершин и ребер в Graph соответственно.

Источник

find_cycle(G, source=None, orientation=None)[source]#

Returns a cycle found via depth-first traversal.

The cycle is a list of edges indicating the cyclic path.
Orientation of directed edges is controlled by orientation.

Parameters:

Ggraph: A directed/undirected graph/multigraph.
sourcenode, list of nodes: The node from which the traversal begins. If None, then a source
is chosen arbitrarily and repeatedly until all edges from each node in
the graph are searched.
orientationNone | ‘original’ | ‘reverse’ | ‘ignore’ (default: None): For directed graphs and directed multigraphs, edge traversals need not
respect the original orientation of the edges.
When set to ‘reverse’ every edge is traversed in the reverse direction.
When set to ‘ignore’, every edge is treated as undirected.
When set to ‘original’, every edge is treated as directed.
In all three cases, the yielded edge tuples add a last entry to
indicate the direction in which that edge was traversed.
If orientation is None, the yielded edge has no direction indicated.
The direction is respected, but not reported.

Returns:

edgesdirected edges: A list of directed edges indicating the path taken for the loop.
If no cycle is found, then an exception is raised.
For graphs, an edge is of the form (u, v) where u and v
are the tail and head of the edge as determined by the traversal.
For multigraphs, an edge is of the form (u, v, key), where key is
the key of the edge. When the graph is directed, then u and v
are always in the order of the actual directed edge.
If orientation is not None then the edge tuple is extended to include
the direction of traversal (‘forward’ or ‘reverse’) on that edge.

Raises:

NetworkXNoCycle: If no cycle was found.

Examples

In this example, we construct a DAG and find, in the first call, that there
are no directed cycles, and so an exception is raised. In the second call,
we ignore edge orientations and find that there is an undirected cycle.
Note that the second call finds a directed cycle while effectively
traversing an undirected graph, and so, we found an “undirected cycle”.
This means that this DAG structure does not form a directed tree (which
is also known as a polytree).

>>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
>>> nx.find_cycle(G, orientation="original")
Traceback (most recent call last):
    ...
networkx.exception.NetworkXNoCycle: No cycle found.
>>> list(nx.find_cycle(G, orientation="ignore"))
[(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]

Источник

Графы: разные виды представления графов. Алгоритмы Дейкстры и Флойда: реализация на Python. Минимальное остовное
дерево

Раскрашивание графов

Обход вершин графа

Поиск в глубину – ПВГ (Depth First Search – DFS)

Метод обхода графа при котором в первую очередь переход делается из последней посещённой вершины (вершины
хранятся в
стеке). Обход в глубину получается естественным образом при рекурсивном обходе графа.

# Смежность вершин
inc = {
    1: [2, 8],
    2: [1, 3, 8],
    3: [2, 4, 8],
    4: [3, 7, 9],
    5: [6, 7],
    6: [5],
    7: [4, 5, 8],
    8: [1, 2, 3, 7],
    9: [4],
}

visited = set()  # Посещена ли вершина?


# Поиск в глубину - ПВГ (Depth First Search - DFS)
def dfs(v):
    if v in visited:  # Если вершина уже посещена, выходим
        return
    visited.add(v)  # Посетили вершину v
    for i in inc[v]:  # Все смежные с v вершины
        if not i in visited:
            dfs(i)


start = 1
dfs(start)  # start - начальная вершина обхода
print(visited)

Поиск в ширину – ПВШ (Breadth First Search – BFS)

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

Порядок обхода вершин при поиске в ширину

# Смежность вершин
inc = {
    1: [2, 8],
    2: [1, 3, 8],
    3: [2, 4, 8],
    4: [3, 7, 9],
    5: [6, 7],
    6: [5],
    7: [4, 5, 8],
    8: [1, 2, 3, 7],
    9: [4],
}

visited = set()  # Посещена ли вершина?
Q = []  # Очередь
BFS = []

# Поиск в ширину - ПВШ (Breadth First Search - BFS)
def bfs(v):
    if v in visited:  # Если вершина уже посещена, выходим
        return
    visited.add(v)  # Посетили вершину v
    BFS.append(v)  # Запоминаем порядок обхода
    # print("v = %d" % v)
    for i in inc[v]:  # Все смежные с v вершины
        if not i in visited:
            Q.append(i)
    while Q:
        bfs(Q.pop(0))

start = 1
bfs(start)  # start - начальная вершина обхода
print(BFS)  # Выводится: [1, 2, 8, 3, 7, 4, 5, 9, 6]

Поиск кратчайших путей в графах (объединение разделов по Дейкстре и Флойду)

Алгоритм Дейкстры

Алгоритм Дейкстры (Dijkstra’s algorithm) —
алгоритм на графах,
находящий кратчайшее расстояние от одной из вершин графа до всех остальных.
Алгоритм работает только для графов без рёбер отрицательного веса (без рёбер с отрицательной “длиной”).

Примеры формулировки задачи

Вариант 1. Дана сеть автомобильных дорог, соединяющих города. Некоторые дороги односторонние.
Найти кратчайшие пути от заданного города до каждого другого города (если двигаться можно только по
дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира,
для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A.
Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Идея алгоритма Дейкстры

Алгоритм состоит и 2 повторяющихся шагов:

Добавление новой вершины (“Расти” – GROW)
“Релаксация”, т.е. пересчёт расстояний до других вершин с учётом добавленной вершины
(RELAX).

Более подробное описание:

Обозначения:

Граф $G = (V,E)$, где $V$ – вершины, $E$ – рёбра.

$v_0$ – начальная вершина (от которой мы ищем кратчайшее растояние до всех остальных)

$R_i$ – известное нам расстояние от вершиеы $v_0$ до вершины $i$-ой.

$D$ – множество вершин до которых мы знаем кратчайшее расстояние от $v_0$.

Граф $G=(V,E)$, где $V$ – вершины, $E$ – рёбра.

$v_0$ – начальная вершина

$R_i$ – кратчайщее расстояние от $v_0$ до $i$-ой вершины

$v=v_0$

$D = [v_0]$

Повторять

Инициализация алгоритма:

$D = {}$ – пустое множество.

$R_{v_0} = 0$ – расстояние от $v_0$ до $v_0$ = 0.

$v = v_0$ – расти будем от вершины $v$.

Повторять (общий шаг алгоритма)

$GROW(V/D,v)$ – Добавляем вершину $v$ из множества $V/D$ в множество $D$.

$RELAX(V/D,v)$ – пробегаем достижимые из $v$ вершины до которых мы ещё не знаем кратчайшее расстояние
и
обновляем расстояния $R_i$ от вершины $v$.

$v$ – вершина с минимальным $R$ из множества $V/D$.

Пока удаётся расти (операция $GROW$ добавляет вершину).

Алгоритм

Каждой вершине $v$ из $V$ сопоставим значение $a[v]$ — минимальное известное расстояние от
этой
вершины до начальной $s$.
Алгоритм работает пошагово — на каждом шаге он рассматривает одну вершину и пытается улучшить текущее
расстояние
до
этой вершины.
Работа алгоритма завершается, когда все вершины посещены, либо когда вычислены расстояния до всех вершин,
достижимых
из начальной.

Инициализация. Значение $a[s]$ самой начальной вершины полагается равным 0, значение
остальных вершин —
бесконечности (в программировании это реализуется присваиванием большого, к примеру, максимально возможного
для
данного типа, значения).
Это отражает то, что расстояния от $s$ до других вершин пока неизвестны.

Шаг алгоритма.
Если все вершины посещены, алгоритм завершается.
В противном случае, из ещё не посещённых вершин выбирается вершина v, имеющая минимальное расстояние
от
начальной вершины $s$ и добавляется в список посещенных. Эта вершина находится, используя перебор всех
непосещенных вершин. При этом суммируется расстояние от старта до одной из посещенных вершин u до
непосещенной $v$. Для первого шага $s$ – единственная посещенная вершина с расстоянием от старта
(то
есть от себя самой), равным 0.

const MaxN = 1000; { Максимальное количество вершин }
var 
  a : array [1..MaxN] of extended; { Найденные кратчайшие расстояния }
  b : array [1..MaxN] of boolean; { Вычислено ли кратчайшее расстояние до вершины }
  p : array [1..MaxN,1..MaxN] of extended; { Матрица смежности }
begin
  { До всех вершин расстояние - бесконечность }
  for i := 1 to n do a[i] := Inf;
  a[s] := 0.0; { И только до начальной вершины расстояние 0 }
  for i := 1 to n do b[i] := false; { Ни до одной вершины мы ещё не нашли кратчайшее расстояние }
  j := s; { Добавляемая вершина (стартовая) }
  repeat
    l := j;
    b[l] := True; { Добавили вершину }
    { Оббегаем все вершины смежные с только что добавленной }
    min := Inf; { Будем искать вершину с минимальным расстоянием от стартовой }
    for i := 1 to n do 
      if not b[i] then begin         
        { Если есть путь короче чем известный в i-ую вершину через l-тую, то запоминаем его }  
        if a[i] < a[l] + p[l][i] then a[i] := a[l] + p[l][i];
        { Если расстояние в эту вершину минимально, то запоминаем её как следующий кандидат на добавление }   
        if a[i] < min then begin min := a[i]; j := i; end;
      end;
  until min = Inf;
  for i := 1 to n do
    if a[i] >= Inf then 
      write('-1 ') { Вершины нельзя достичь из начальной }
    else  
      write(a[i],' '); { Расстояние от начальной вершины = a[i] }
 end;

Алгоритм Флойда

Алгоритм Флойда — Уоршелла —
динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного
графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Пусть вершины графа пронумерованы от 1 до $n$ и введено обозначение $d_{ij}^k$ для длины кратчайшего пути от $i$
до
$j$, который кроме самих вершин $i,; j$ проходит только через вершины $1 ldots k$.
Очевидно, что $d_{i j}^{0}$ – длина (вес) ребра $(i,;j)$, если таковое существует (в противном случае его длина
может быть обозначена как $infty$)

Существует два варианта значения $d_{i j}^{k},;k in mathbb (1,;ldots,;n)$:

Кратчайший путь между $i,;j$ не проходит через вершину $k$, тогда $d_{i j}^{k}=d_{i j}^{k-1}$
Существует более короткий путь между $i,;j$, проходящий через $k$, тогда он сначала идёт от $i$ до $k$, а
потом от $k$ до $j$. В этом случае, очевидно, $d_{i j}^{k}=d_{i k}^{k-1} + d_{k j}^{k-1}$

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для $d_{i j}^k$ имеет вид:

$d_{i j}^0$ – длина ребра $(i,;j)$

$d_{i j}^{k} = min (d_{i j}^{k-1},; d_{i k}^{k-1} + d_{k j}^{k-1})$

Алгоритм Флойда – Уоршелла последовательно вычисляет все значения $d_{i j}^{k}$,
$forall i,; j$ для $k$ от 1 до $n$.
Полученные значения $d_{i j}^{n}$ являются длинами кратчайших путей между вершинами $i,; j$.

for k := 1 to n do { k - промежуточная вершина } 
  for i := 1 to n do { из i-ой вершины } 
    for j := 1 to n do { в j-ую вершину } 
      W[i][j] = min(W[i][j], W[i][k] + W[k][j]);

Алгоритм Прима

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного
неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже
переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево
разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву
присоединяется
самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.

Вход: Связный неориентированный граф $G(V,E)$

Выход: Множество $T$ рёбер минимального остовного дерева

Обозначения:

$d_i$ — расстояние от $i$-й вершины до построенной части дерева
$p_i$ — предок $i$-й вершины, то есть такая вершина $u$, что $(i,u)$ самое короткое рёбро соединяющее $i$ с
вершиной из построенного дерева.
$w(i,j)$ — вес ребра $(i,j)$
$Q$ — приоритетная очередь вершин графа, где ключ – $d_i$
$T$ — множество ребер минимального остовного дерева

Псевдокод:

$T gets $ {}

Для каждой вершины $i in V$: $d_i gets infty$, $p_i gets nil$

$d_1 gets 0$

$Q gets V$

$v gets Extract.min(Q) $

Пока $Q$ не пуста:

Для каждой вершины $u$ смежной с $v$:

Если $u in Q$ и $w(v,u) < d[u]$: $d_u gets w(v,u)$, $p_u gets v$

$ v gets Extract.Min(Q)$

$ T gets T+(p[v],v)$

Поиск особых путей в графах

Поиск эйлерова цикла в графе

Поиск гамильтонова цикла в графе

Топологическая сортировка

Реализация через DFS.

Источник

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Python

1. Использование БФС

C++

Java

Python

2. Использование ДФС

C++

Java

Python

Графы: разные виды представления графов. Алгоритмы Дейкстры и Флойда: реализация на Python. Минимальное остовное дерево

Раскрашивание графов

Обход вершин графа

Поиск в глубину – ПВГ (Depth First Search – DFS)

Поиск в ширину – ПВШ (Breadth First Search – BFS)

Поиск кратчайших путей в графах (объединение разделов по Дейкстре и Флойду)

Алгоритм Дейкстры

Алгоритм Флойда

Алгоритм Прима

Поиск особых путей в графах

Поиск эйлерова цикла в графе

Поиск гамильтонова цикла в графе

Топологическая сортировка

Вам также может понравиться

Как найти картинку с нужным размером

Как найти файл конфигурации mysql

Как найти скорость объекта через скорость сближения

Добавить комментарий Отменить ответ

Графы: разные виды представления графов. Алгоритмы Дейкстры и Флойда: реализация на Python. Минимальное остовное
дерево