Поиск подключения в графике - PullRequest
Новая
       14

Поиск подключения в графике

0 голосов
/ 26 мая 2018

Я смотрел это учебное пособие по подключенным компонентам Принстонского университета и пытался запустить код, указанный на моем компьютере (пропустите код до 13 минут).Код должен определить все различные связанные компоненты графа и назначить каждой вершине идентификатор, который определяет, к какому компоненту он принадлежит.Я сделал примерный график для его проверки, см. Здесь:

! [Визуальное представление] [1]

Когда я запускаю приведенный ниже код, он печатает идентификаторы, которые будут 0,0,1,2,3но они должны быть 0,0,0,1,1.Есть идеи, что я делаю не так? 

public class ConnectedComponents {
    public boolean[] marked;
    public int[] id;
    public int count;


    public ConnectedComponents() {
        //Make a Graph with 5 vertices, and 4 edges
        Graph g = new Graph(5, false, false);
        g.addEdge(0, 1); g.addEdge(0, 2);g.addEdge(1, 2); 
        g.addEdge(3, 4);

        int numVertices = g.getNumberOfVertices();
        marked = new boolean[numVertices];
        id = new int[numVertices];
        for(int v = 0; v < numVertices; v++) {
            if(!marked[v]) {
                dfs(g, v);
                count++;
            }
        }
    }

    public void dfs(Graph g, int v) {
        marked[v] = true;
        id[v] = count;
        // loops through each vertex that's connected to v
        for(int w: g.getEdgeMatrix()[v]) {
            if(!marked[w]) {
                dfs(g, w);
            }
        }
    }

    public int id(int v) {
        return id[v];
    }

    public static void main(String [] args){
        ConnectedComponents cc = new ConnectedComponents();
        for(int i = 0; i < cc.id.length; i++) {
            System.out.println(cc.id[i]);
        }
    }

}

https://i.stack.imgur.com/vhTxD.jpg

1 Ответ

0 голосов
/ 26 мая 2018

Благодаря реализации addEdge ваша DFS эффективно работает с ориентированным графом.Измените его, чтобы добавить обратные края.

...