0

グラフのデータ構造を表すクラスをJavaで書いています。これは、無向、無加重グラフに固有であり、その目的は主にエッジテスト（ノードAがノードBに直接または間接的に接続されている）を目的としています。

indirectEdgeTestメソッドの実装についてサポートが必要です。以下のコードでは、このメソッドにコメントを付けただけで、falseを返しているので、コードはそのままコンパイルされます。

アルゴリズムを考え出すのに少し時間をかけましたが、これよりも単純なものは見つからないようです。必要以上に複雑になっているのではないかと心配しています。

  • 最初に直接接続をテストします
  • ノードaからノードbへの直接接続が存在しない場合：
    • ノードaに接続されているすべてのエッジについて：
      • エッジa->iを含まない新しいグラフを作成します
      • ノードiとbの間の間接接続について新しいグラフをテストします

擬似コードまたは実際のJavaコードのいずれかがあなたの答えに歓迎されます。これが私が持っているコードです：

class Graph {

    // This is for an undirected, unweighted graph
    // This implementation uses an adjacency matrix for speed in edge testing 

    private boolean[][] edge;
    private int numberOfNodes;

    public Graph(int numNodes) {

        // The indices of the matrix will not be zero-based, for clarity,
        // so the size of the array will be increased by 1.

           edge = new boolean[numNodes + 1][numNodes + 1];
           numberOfNodes = numNodes;
    }

    public void addEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = true;
                edge[b][a] = true;
            }
        }
    }

    public void removeEdge(int a, int b) {
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                edge[a][b] = false;
                edge[b][a] = false;
            }
        }
    }

    public boolean directEdgeTest(int a, int b) {

        // if node a and node b are directly connected, return true 

        boolean result = false;
        if (a <= numberOfNodes && a >= 1) {
            if (b <= numberOfNodes && b >= 1) {
                if (edge[a][b] == true) {
                    result = true;
                }
            }
        }
        return result;
    }

    public boolean indirectEdgeTest(int a, int b) {

        // if there exists a path from node a to node b, return true 

            // implement indirectEdgeTest algorithm here.

            return false;
    }
}
4

3 に答える 3

2

えーと、そのアプローチはひどく非効率に聞こえます。これはどうですか：

void walk(Node orgin, Set<Node> visited) {
    for (Node n : origin.neighbours) {
        if (!visited.contains(n)) {
            visited.add(n);
            walk(n, visited);
        }
    }
}


boolean hasPath(Node origin, Node target) {
    Set<Node> reachables = new HashSet<Node>();
    walk(origin, reachables);
    return reachables.contains(target);
}

また、隣接行列を使用することは、スパースグラフ内のノードの隣接を効率的に反復することができないため、グラフトラバーサルに使用するのは疑わしいです。

その方法が頻繁に使用され、グラフがめったに変更されない場合は、接続された領域に事前に分解し、ノードごとにそれが属する領域を保存することで、クエリを高速化できます。次に、2つのノードが同じリージョンに属している場合、それらは接続されます。

編集：グラフを最もよく表す方法を明確にするため。直接エッジテストの場合、隣接行列が推奨されます。パステストの場合、領域への分解はです。後者は、グラフが変化しても最新の状態を維持するのは簡単ではありませんが、文献にはこのためのアルゴリズムがある可能性があります。あるいは、隣接リストはグラフトラバーサル、つまりパステストに使用できますが、接続された領域への分解を直接記録するよりも効率が低くなります。隣接セットを使用して、スパースグラフでのより効率的なネイバー反復と一定時間のエッジテストを組み合わせることもできます。

情報を冗長に保存して、クエリの種類ごとに、調整された個別のデータ構造を維持することもできることに注意してください。

于 2010-08-23T19:57:59.927 に答える
1

あなたの解決策は機能しますが、より良い解決策はルート「a」ノードからスパニングツリーを構築することです。このようにして、特定のエッジだけが欠落している複数のサブグラフではなく、最終的に検討するツリーが1つだけになります。

アイデアが浮かんだら、それをどのように実装するかはあなた次第です。アルゴリズムを合理的な方法で実装できると仮定すると、接続を検索するためのツリーは1つだけである必要があります。これにより、処理が大幅に高速化されます。

于 2010-08-23T19:53:41.330 に答える
1

私はメリトンの答えを信用していますが、アイデアを動作するJavaクラスと単体テストにコード化したので、誰かが再利用可能なコードを探している場合に備えて、ここで別の答えを提供します。

メリトンありがとう。ダイレクトエッジテストとパステストを区別することが重要であり、特定のタイプのテストにより適したグラフの実装が異なることに同意します。パステストの場合、隣接リストは隣接行列表現よりもはるかに効率的であるように思われます。

以下の私のコードはおそらくそれができるほど効率的ではありませんが、今のところそれは私の問題を解決しています。誰かが提案する改善があれば、遠慮なくしてください。

コンパイルするには：javac Graph.java

実行するには：java GraphTest

class Graph {

    private java.util.ArrayList<Node> nodeList;
    private int numberOfNodes;

    public Graph(int size) {
        nodeList = new java.util.ArrayList<Node>(size + 1);
        numberOfNodes = size;

        for (int i = 0; i <= numberOfNodes; i++) {
            nodeList.add(new Node());
        }
    }

    public void addEdge(int a, int b) {
        if (a >= 1 && a <= numberOfNodes) {
            if (b >= 1 && b <= numberOfNodes) {
                nodeList.get(a).addNeighbour(nodeList.get(b));
                nodeList.get(b).addNeighbour(nodeList.get(a));
            }
         }
    }

    public void walk(Node origin, java.util.Set<Node> visited) {
        for (Node n : origin.getNeighbours()) {
            if (!visited.contains(n)) {
                visited.add(n);
                walk(n, visited);
            }
        }
    }

    public boolean hasPath(Node origin, Node target) {
        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        walk(origin, reachables);
        return reachables.contains(target);
    }

    public boolean hasPath(int a, int b) {

        java.util.Set<Node> reachables = new java.util.HashSet<Node>();
        Node origin = nodeList.get(a);
        Node target = nodeList.get(b);
        walk(origin, reachables);
        return reachables.contains(target);       
    }
}

class Node {

    private java.util.Set<Node> neighbours;

    public Node() {
        neighbours = new java.util.HashSet<Node>();
    }

    public void addNeighbour(Node n) {
        neighbours.add(n);
    }

    public java.util.Set<Node> getNeighbours() {
        return neighbours;
    }
}

class GraphTest {

    private static Graph g;

    public static void main(String[] args) {

        g = new Graph(6);

        g.addEdge(1,5);
        g.addEdge(4,1);
        g.addEdge(4,3);
        g.addEdge(3,6);

        printTest(1, 2);
        printTest(1, 4); 
        printTest(6, 1);   
    }

    public static void printTest(int a, int b) {

        System.out.print("Are nodes " + a + " and " + b + " connected?");
        if (g.hasPath(a, b)) {
            System.out.println(" YES.");
        } else {
            System.out.println(" NO.");
        }
    }
}
于 2010-08-24T17:28:49.147 に答える