directed graph

A directed graph {digraph for short) G consists of a set of vertices Fand a set of arcs E.

Ориентированный граф (или сокращенно орграф) G = (V, Е) состоит из множества вершин V и множества дуг Е.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

The interdependences among the inherited and synthesized attributes at the nodes in a parse tree can be depicted by a directed graph called a dependency graph,

Зависимости между наследуемыми и синтезируемыми атрибутами в узлах дерева разбора могут быть показаны с помощью направленного графа, называемого графом зависимости.

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey / Compilers: Principles, Techniques, and ToolsАхо, Альфред В.,Ульман, Джеффри,Сети, Рави / Компиляторы: принципы, технологии, инструменты

Компиляторы: принципы, технологии, инструменты

Ахо, Альфред В.,Ульман, Джеффри,Сети, Рави

© Addison-Wesley Publishing Company, Inc., 1985

© 2001

© Издательский дом "Вильямс", 2001

Compilers: Principles, Techniques, and Tools

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey

© 2001 by PEARSON EDUCATION NORTH ASIA LIMITED and PEOPLE'S POSTS & TELECOMMUNICATIONS PUBLISHING HOUSE

© 1986

A path in a directed graph is any sequence of arcs where the final vertex of one is the initial vertex of the next one.

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

Christofides, Nicos / Graph Theory. An Algorithmic ApproachКристофидес, Никос / Теория графов. Алгоритмический подход

Теория графов. Алгоритмический подход

Кристофидес, Никос

© 1975 by Academic Press Inc. (London)Ltd.

© Перевод на русский язык, «Мир», 1978

Graph Theory. An Algorithmic Approach

Christofides, Nicos

© 1975 by ACADEMIC PRESS INC. (LONDON) LTD.

It is also quite obvious that not every directed graph has a spanning directed tree, as can, for example, be seen from the graph of Fig. 7.3.

Также очевидно, что не всякий ориентированный граф содержит остовное ориентированное дерево. Это подтверждает граф, изображенный на рис. 7.3.

Christofides, Nicos / Graph Theory. An Algorithmic ApproachКристофидес, Никос / Теория графов. Алгоритмический подход

Теория графов. Алгоритмический подход

Кристофидес, Никос

© 1975 by Academic Press Inc. (London)Ltd.

© Перевод на русский язык, «Мир», 1978

Graph Theory. An Algorithmic Approach

Christofides, Nicos

© 1975 by ACADEMIC PRESS INC. (LONDON) LTD.

In addition to the tree arcs, there are three other types of arcs defined by a depth-first search of a directed graph.

В добавление к дугам дерева существуют еще три типа дуг, определяемых в процессе обхода орграфа методом поиска в глубину.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

We shall now present an algorithm to find the strongly connected components of a given directed graph G.

Теперь рассмотрим алгоритм нахождения сильно связных компонент для заданного ориентированного графа G.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

Directed graph.

Ориентированный граф

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

Directed graph with arc costs.

Ориентированный граф с помеченными дугами

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

A dag for a basic block (or just dag) is a directed acyclic graph with the following labels on nodes:

Даг базового блока (далее просто даг) представляет собой направленный ациклический граф со следующими метками узлов.

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey / Compilers: Principles, Techniques, and ToolsАхо, Альфред В.,Ульман, Джеффри,Сети, Рави / Компиляторы: принципы, технологии, инструменты

Компиляторы: принципы, технологии, инструменты

Ахо, Альфред В.,Ульман, Джеффри,Сети, Рави

© Addison-Wesley Publishing Company, Inc., 1985

© 2001

© Издательский дом "Вильямс", 2001

Compilers: Principles, Techniques, and Tools

Aho, Alfred V.,Sethi, Ravi,Ullman, Jeffrey

© 2001 by PEARSON EDUCATION NORTH ASIA LIMITED and PEOPLE'S POSTS & TELECOMMUNICATIONS PUBLISHING HOUSE

© 1986

The ratio of the computing times of the two versions for non-directed graphs with vertex degrees in the range 3-5 is shown in Fig. 10.7.

Зависимость отношения времен вычисления при использовании этих двух алгоритмов для неориентированных графов со степенями вершин 3-5 приведена на рис. 10.7.

Christofides, Nicos / Graph Theory. An Algorithmic ApproachКристофидес, Никос / Теория графов. Алгоритмический подход

Теория графов. Алгоритмический подход

Кристофидес, Никос

© 1975 by Academic Press Inc. (London)Ltd.

© Перевод на русский язык, «Мир», 1978

Graph Theory. An Algorithmic Approach

Christofides, Nicos

© 1975 by ACADEMIC PRESS INC. (LONDON) LTD.

Measured in terms of the relationships they can represent, dags are more general than trees but less general than arbitrary directed graphs.

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

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000

For simplicity in notation we will only consider graphs which are nondirected, since any extension to directed graphs is straightforward.

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

Christofides, Nicos / Graph Theory. An Algorithmic ApproachКристофидес, Никос / Теория графов. Алгоритмический подход

Теория графов. Алгоритмический подход

Кристофидес, Никос

© 1975 by Academic Press Inc. (London)Ltd.

© Перевод на русский язык, «Мир», 1978

Graph Theory. An Algorithmic Approach

Christofides, Nicos

© 1975 by ACADEMIC PRESS INC. (LONDON) LTD.

This chapter presents the basic data structures that can be used to represent directed graphs. Some basic algorithms for determining the connectivity of directed graphs and for finding shortest paths are also presented.

В этой главе рассмотрены основные структуры данных, которые применяются для представление ориентированных графов, а также описаны некоторые основные алгоритмы определения связности ориентированных графов и нахождения кратчайших путей.

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон / СтруктурыAho, Alfred V.,Ullman, Jeffrey,Hopcroft, John / Data Structures and Algorithms

Data Structures and Algorithms

Aho, Alfred V.,Ullman, Jeffrey,Hopcroft, John

© Addison-Wesley Publishing Company, Inc

Структуры

Ахо, Альфред В.,Ульман, Джеффри,Хопкрофт, Джон

© Издательский дом "Вильямс", 2000

© Addison-Wesley Publishing Company, Inc

© 2000