Генерация связанного графа Java - PullRequest
Новая
       17

Генерация связанного графа Java

0 голосов
/ 27 октября 2018

Я хочу написать функцию, которая получает набор вершин, а затем развивает ребро между 2 вершинами и повторяет это до тех пор, пока граф не станет связным графом). Как я могу узнать, когда график стал связанным?

1 Ответ

0 голосов
/ 27 октября 2018

Это было бы основной идеей: каждый раз, когда вы добавляете новое ребро, вы запускаете BFS или DFS для проверки подключения. Это решение может быть дополнительно оптимизировано. 

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Set;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class Main {

public static boolean isConnected(SimpleGraph<Integer, DefaultEdge> graph) {
    Set<Integer> vertexSet = graph.vertexSet();
    if(vertexSet.size()==0) {
        //graph is connected by definition
        return true;
    }

    if(vertexSet.size()-1>graph.edgeSet().size()) {
        //not enough edges, must be disconnected
        return false;
    }

    Set<Integer> traversed = new HashSet<>();
    Deque<DefaultEdge> toTraverse = new LinkedList<DefaultEdge>();

    //pick one random element to start search
    Integer startVertex = vertexSet.iterator().next();

    traversed.add(startVertex);
    graph.edgesOf(startVertex).forEach(x->toTraverse.addLast(x));
    while(traversed.size()!=vertexSet.size() && toTraverse.size()!=0) {
        DefaultEdge currentEdge = toTraverse.pollFirst();
        Integer src = graph.getEdgeSource(currentEdge);
        Integer dst = graph.getEdgeSource(currentEdge);

        //it can be at most one new vertex
        Integer targetVertex = traversed.contains(src)?dst:src;
        if(!traversed.contains(targetVertex)) {
            traversed.add(targetVertex);
            //BFS
            graph.edgesOf(targetVertex).forEach(x->toTraverse.addLast(x));

            //DFS
            //graph.edgesOf(targetVertex).forEach(x->toTraverse.addFirst(x));
        }
    }

    if(traversed.size()==vertexSet.size()) {
        return true;
    }else {
        return false;
    }
}

public static SimpleGraph<Integer, DefaultEdge> buildGraph(int numberOfVertices) {
    SimpleGraph<Integer, DefaultEdge> g =
            new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);
    for(int i = 0; i < numberOfVertices; i++) {
        g.addVertex(i);
    }
    Random r = new Random();
    do {
        int a = r.nextInt(numberOfVertices);
        int b = r.nextInt(numberOfVertices);
        while(a == b) {
            b = r.nextInt(numberOfVertices);
        }
        g.addEdge(a, b);
    }while(!isConnected(g));
    return g;

}

public static void main(String[] args) {
    SimpleGraph<Integer, DefaultEdge> g = buildGraph(10);
    System.out.println("Number of edges");
    System.out.println(g.edgeSet().size());
    System.out.println("Edges:");
    for(DefaultEdge e: g.edgeSet()){
        String a = g.getEdgeSource(e).toString();
        String b = g.getEdgeTarget(e).toString();
        System.out.println(a+" "+b);
    }
}

}

Для произвольного графа проверка связности требует не менее O (V) (V - количество вершин, E - количество ребер). BFS и DFS работают в O (V + E). Это может быть хорошо, если вы хотите создавать сравнительно небольшие графики. Вот умная идея, как это сделать. В начале вы создаете V отдельных графиков. Теперь вы хотите добавить ребро между A и B, вы найдете график, где принадлежит A, и другой, где принадлежит B. Если это два разных графика, объедините их. Повторяйте этот процесс, пока не останется только один график.

...