Итератор смежных узлов

Самая распространённая операция в теории графов — обход смежных рёбер, при котором используется вершина для обхода связанных с ней смежных рёбер. Временная сложность обхода смежных рёбер в матрице смежности составляет 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 код файла:

package example.graph;

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:

package example.graph;

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];
    }
}
Другие расширения