Nähe matrix in java oder c++ zu finden angeschlossenen Knoten

Ich bin da ein problem, wo ich N Knoten im Graphen, die miteinander verbunden sind, um einander dann gegeben eine matrix, die Listen unten ein Knoten mit einem anderen (1, wenn es ist, 0, wenn nicht). Ich Frage mich, wie man am besten Ansatz dieses problem. Ich denke, dass diese Nachbarschaft-matrix? Aber wie würde ich das umsetzen, dass ...

Im Grunde, was ich versuche, um aus dieser herauszufinden, ob ein bestimmter Knoten verbunden ist, zu allen anderen Knoten in einem gegebenen Satz 'S'. Und ob die ausgewählten Objekte sind die clique oder nicht...

Wäre ich dankbar für Hinweise.

InformationsquelleAutor Omnipresent | 2008-12-08

c++graph-theory java

7

Können Sie diese umsetzen mit einem 2-dimensionales array von booleans. Also, wenn Knoten i an Knoten j, dann myarray[i][j] wahr wären. Wenn Ihr die Kanten nicht gerichtet", dann myarray[j][i] ist true, wenn myarray[i][j] ist.

Diese können auch erweitert werden, um gewichtete Kanten durch Verwendung von integers (oder einen anderen numerischen Typ) statt Boolesche Werte als Elemente des Arrays.

InformationsquelleAutor lemnisca
3

Der einfachste Weg, dies zu tun wäre, um eine quadratische matrix (2d-array), Boolesche Werte zeigen die Anwesenheit oder Abwesenheit einer Verbindung oder ganze zahlen darstellen, die Kosten des traversal. Für eine spärliche Grafik, jedoch kann man bessere Kompression durch die Verwendung von jagged arrays und dann speichern, welche Knoten benachbart zu der ersten. In Java würde ich wahrscheinlich tun dies durch eine List<List<Integer>> wo die äußere Liste entspricht den Knoten in Frage, und der inneren Liste werden alle Knoten benachbart zu dieser.

Vorausgesetzt, Sie entscheiden, zu verwenden eine standard - (unkomprimiert) matrix, die Sie herausfinden könnten, ob ein Knoten i benachbart zu jedem Knoten j in einer Liste zu iterieren Sie durch die Liste, und klicken Sie dann auf der Suche nach Einem[i][j]. Wenn einer von Ihnen sind false ist, dann ist es nicht neben jedem Element in der Liste, ansonsten ist es wahr. Für eine clique, Sie müssen nur tun Sie dies für jedes Element in der Liste (hat er den Fall, wo i=j und einige Optimierungen für eine ungerichtete graph).

Ein Beispiel (wieder in Java)
```
public boolean isClique(boolean[][] A, List<Integer> nodes){
  for(int i : nodes){
    for(int j : nodes){
      if(i != j){
        if(!A[i][j]) return false;
      }
    }
  }
  return true;
}
```
Optimierungen und eine Lösung für das Max-Clique-problem sind Links als übung für den Leser.

InformationsquelleAutor James

Versuchen Sie dies:

public class AdjacencyMatrix {

private String [] nodes;

private int [][] matrix;

public AdjacencyMatrix(String [] nodes,int [][] matrix){
    this.nodes = nodes;
    this.matrix = matrix;
}

boolean isSymmetric(){
    boolean sym = true;
     for(int i=0;i<matrix.length;i++){
         for(int j=i+1; j < matrix[0].length ; j++){
             if (matrix[i][j] != matrix[j][i]){
                 sym = false;
                 break;
             }
         }
     }
     return sym;
}

public Graph createGraph(){
    Graph graph = new Graph();
     Node[] NODES = new Node[nodes.length];

    for (int i=0; i<nodes.length; i++){
        NODES[i] =  new Node(nodes[i]);
        graph.addNode(NODES[i]);
    }

    for(int i=0;i<matrix.length;i++){            
         for(int j=i;j<matrix[0].length;j++){
             int distance = matrix[i][j];
             if (distance != 0){                     
                 graph.addEdge(new Edge(NODES[i], NODES[j], distance));
             } 
         }
    }

    return graph;
}


public long pathLength(int[] path){
    long sum = 0;
    for (int i=0; i<path.length - 1; i++){
        if (matrix[path[i]][path[i+1]] != 0)
            sum += matrix[path[i]][path[i+1]];
        else {
            sum = 0;
            break;
        }
    }

    return sum;
}


public static void main(String[] args){
    String[] nodes = {"A", "B", "C", "D", "E"};
    int [][] matrix= {  {0, 2, 2, 1, 0}, 
                        {2, 0, 1, 0, 0}, 
                        {2, 1, 0, 0, 1}, 
                        {1, 0, 0, 0, 4}, 
                        {0, 0, 1, 4, 7}};
    AdjacencyMatrix am = new AdjacencyMatrix(nodes, matrix);
    Graph graph  = am.createGraph();
    int[] a = {0, 2, 4, 4, 3, 0};
    int[] b = {0, 1, 2, 4, 4, 3, 0};
    graph.writeGraph(); 
    am.pathLength(a);
    am.pathLength(b);
}

}

Hey-Lösung gibt Fehler für die Graph-Klasse/interface. So haben Sie eine andere Datei für Sie?. Vielen Dank im Voraus

InformationsquelleAutor

2

Tipp: So haben Sie Ihre Nachbarschaft-matrix M die Ihnen sagt, wenn zwei Knoten sind direkt miteinander verbunden. Dann was bedeutet M^2 bietet Ihnen? Es sagt Ihnen, wenn es ist ein Weg der Länge 2 zwischen zwei Knoten.

Ich lasse Sie sich vorstellen, was sind M^3,... , M^inf (wenn Sie erreichen die fixpoint)

InformationsquelleAutor Piotr Lesnicki
1

Verwendung Ihres angrenzens matrix, die Anwendung der Floyd-Warshall-Algorithmus geben Sie alle Ihre Pfade zwischen den Knoten. Dann können Sie prüfen, ob bestimmte Sätze.

InformationsquelleAutor Robin
0

Möchten Sie vielleicht die Verwendung bitset oder bit_vector statt bool[][].

Wenn Sie nicht ein jagged array, und Ihre verbindungen sind symmetrisch, wrappen mit einem accessor-basierend auf MIN() & MAX() [Makros]. Das speichern der gleichen Daten in beiden Orten ist ein Rezept für Schmerz. Schließlich, array[i][j] != array[j][i].
```
E.g: getValue( int i, int j ) { return array [ MIN(i,j) ] [ MAX(i,j) ] }
```
InformationsquelleAutor Mr.Ree

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.