Итератор смежных узлов
Самая распространённая операция в теории графов — обход смежных рёбер, при котором используется вершина для обхода связанных с ней смежных рёбер. Временная сложность обхода смежных рёбер в матрице смежности составляет O(V), в то время как список смежности позволяет находить их напрямую, что эффективнее.

Итерация по матрице смежности:
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<Integer>();
for(int i = 0 ; i < n ; i ++ )
if( g[v][i] )
adjV.add(i);
return adjV;
}
...
Итерация списка смежности:
// Возвращает все смежные рёбра вершины в графе
// Поскольку Java использует механизм ссылок, возврат Vector не влечёт дополнительных накладных расходов,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
...
Для этих двух способов представления графа мы можем абстрагировать интерфейс, чтобы сформировать каркас этого набора алгоритмов, не задумываясь о том, лежит ли в основе список смежности или матрица смежности.
В этом разделе пишется тестовый пример GraphReadTest, который реализует отображение графа путём вызова абстрактного интерфейса и может быть просмотрен в пакете read.
* Абстрактный интерфейс графа
*/
public interface Graph {
public int V();
public int E();
public void addEdge( int v , int w );
boolean hasEdge( int v , int w );
void show();
public Iterable<Integer> adj(int v);
}
Пример кода на Java
Загрузка пакета исходного кода:Скачать
(1) Итерация по матрице смежности
src/example/graph/DenseGraphIterater.java код файла:
import java.util.Vector;
/**
* Итерация по матрице смежности
*/
public class DenseGraphIterater {
// Количество узлов
private int n;
// Количество рёбер
private int m;
// Является ли граф ориентированным
private boolean directed;
// Конкретные данные графа
private boolean[][] g;
// конструктор
public DenseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g инициализируется как boolean-матрица n*n, каждый g[i][j] равен false, что означает отсутствие рёбер
// false — значение по умолчанию для переменных типа boolean
g = new boolean[n][n];
}
// Возвращает количество узлов
public int V(){ return n;}
// Возвращает количество рёбер
public int E(){ return m;}
// Добавить ребро в граф
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = истина;
if( !directed )
g[w][v] = истина;
m ++;
}
// Проверить, существует ли ребро из v в w в графе
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
// Возвращает все смежные рёбра вершины в графе
// Поскольку Java использует механизм ссылок, возврат Vector не влечёт дополнительных накладных расходов,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<Integer>();
for(int i = 0 ; i < n ; i ++ )
if( g[v][i] )
adjV.add(i);
return adjV;
}
}
(2) Итерация по списку смежности
код файла src/example/graph/SparseGraphIterater.java:
import java.util.Vector;
/**
* Итерация по списку смежности
*/
public class SparseGraphIterater {
private int n; // Количество узлов
private int m; // Количество рёбер
private boolean directed; // Является ли граф ориентированным
private Vector<Integer>[] g; // Конкретные данные графа
// конструктор
public SparseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // Инициализация без рёбер
this.directed = directed;
// g инициализируется как n пустых векторов, то есть каждый g[i] пуст, т. е. рёбер нет
g = (Vector<Integer>[])new Вектор[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
public int V(){ return n;} // Возвращает количество узлов
public int E(){ return m;} // Возвращает количество рёбер
// Добавить ребро в граф
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].добавьте(w);
if( v != w && !directed )
g[w].добавьте(v);
m ++;
}
// Проверить, существует ли ребро из v в w в графе
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
// Возвращает все смежные рёбра вершины в графе
// Поскольку Java использует механизм ссылок, возврат Vector не влечёт дополнительных накладных расходов,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}