Универсальный Граф с помощью матрицы смежности - Ява


Основная цель представления графа с помощью матрицы смежности, является способ, чтобы проверить вершин и существование своего соседа в постоянная времени пропорциональна \$\mathcal{о}(н)\$.

В различные учебники, которые я видел, графики содержат только integer вершины и это будет прямо вперед, чтобы представлять их в \$в \в раз\$ целое 2Д массив для сопоставления вершин.

В реальном мире, мы должны хранить пользовательские типа Object как вершину графа. Для этого я создал реализацию графа с матрицей смежности. Можете ли вы пожалуйста, дайте мне знать любые отзывы / улучшения?

//V - type of Object stored on graph vertices
public class GraphAM<V> {

    //Maps vertex with its adjacency matrix index. O(1) to retrieve index of a vertex
    private Map<V, Integer> vertices;
    //To get vertex using index at O(1) time
    private List<V> verticesLookup;

    //adjacency matrix
    private int[][] adj;

    private int index;

    public GraphAM(int numVertices) {
        adj = new int[numVertices][numVertices];
        index = 0;
        vertices = new HashMap<>();
        verticesLookup = new ArrayList<>();
    }

    public void addEdge(V from, V to) {
        addVertex(from);
        addVertex(to);

        int fromIndex = vertices.get(from);
        int toIndex = vertices.get(to);
        adj[fromIndex][toIndex] = 1;
    }

    private void addVertex(V v) {
        if(!vertices.containsKey(v)) {
            vertices.put(v, index);
            verticesLookup.add(index, v);
            index++;
        }
    }

    public void bfs(V start) {
        Queue<V> queue = new LinkedList<>();
        boolean[] visited = new boolean[vertices.size()]; 

        queue.add(start);
        int index = vertices.get(start);
        visited[index] = true;

        while(!queue.isEmpty()) {
            V v = queue.poll();
            System.out.print(v + " ");

            List<V> adjacentVertices = getAdjacentVertices(v);
            for(V a : adjacentVertices) {
                int adjInd = vertices.get(a);
                if(!visited[adjInd]) {
                    queue.add(a);
                    visited[adjInd] = true;
                }
            }

        }

    }

    public void dfs(V start) {
        boolean[] visited = new boolean[vertices.size()];
        dfs(start, visited);
    }

    private void dfs(V v, boolean[] visited) {
        System.out.print(v + " ");
        int index = vertices.get(v);
        visited[index] = true;

        List<V> adjacentVertices = getAdjacentVertices(v);
        for(V a : adjacentVertices) {
            int aIndex = vertices.get(a);
            if(!visited[aIndex]) {
                dfs(a, visited);
            }
        }
    }

    private List<V> getAdjacentVertices(V v) {
        int index = vertices.get(v);
        List<V> result = new ArrayList<>();
        for(int i=0; i<adj[index].length; i++) {
            if(adj[index][i] == 1) {
                result.add(verticesLookup.get(i));
            }
        }
        return result;
    }

}

Основной класс

class Main {

  public static void main(String[] args) {
            GraphAM<Integer> g = new GraphAM<>(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);

            System.out.println("Following is Breadth First Traversal "+
                    "(starting from vertex 2)");

            g.bfs(2);

            System.out.println("\nFollowing is Depth First Traversal "+
                    "(starting from vertex 2)");

            g = new GraphAM<>(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);

            g.dfs(2);
    }

}


1724
3
задан 24 марта 2018 в 10:03 Источник Поделиться
Комментарии
1 ответ


  • Можно упростить сопоставления вы используете, чтобы получить от вершины к его Связанный объект. Вместо использования List<V>, который может только гарантия \$\mathcal{о}(н)\$ подстановки времени, вы могли бы просто использовать массив.

  • Замечания учли, что известно, должны быть удалены, комментарии, которые могут оказаться устаревшими через рефакторинг должен подсказать, что рефакторинг:

    public class GraphAM<V> {
    private Map<V, Integer> vertexToIndex;
    private V[] indexToVertex;

    private int[][] adjacencyMatrix;
    private int index;


  • vertices (ака vertexToIndex может быть инициализирован с нетерпением.

  • все частные поля (кроме индекса) должны быть отмечены final.

  • Вместо передачи numVertices конструктор, вы должны рассмотреть возможность прохождения Collection<V>, что снимает необходимость разбираться с добавление вершины в addEdge.

  • Наконец, вместо использования boolean[] для visited, а Set<V> значительно более очевидным. Он может прийти хоть с малой производительности.

  • Наконец, функции поиска не ищите ничего... они просто выполнении исчерпывающий обхода и, соответственно, бесполезными в их нынешнем виде...

2
ответ дан 24 марта 2018 в 11:03 Источник Поделиться