Java - Komponenten aus einem Graph berechnen / Algorithmus?

2 Antworten

Smirror
18.06.2021, 10:34

Hab leider noch nie mit Wegematrizen gearbeitet, aber für mich sieht es so aus, als müsste man für die Menge der beteiligten Knoten einer Komponente einfach die Spalten für jede Zeile durchgehen und schauen wo eine 1 steht. Diese Knoten fügt man dann einer Menge hinzu. Und dann muss man halt noch darauf achten, dass es nicht mehrere gleiche Komponenten geben kann, also pro Zeile schauen, ob es diese Komponente schon gibt.

Ich bin mir aber nicht sicher, ob man aus der Wegematrix ablesen kann, dass (in deinem Beispiel jetzt) nur Kanten zwischen (1,3) und (1,4) existieren.

Soweit ich es verstanden hab, gibt die Wegmatrix an, ob man von einem Knoten irgendwie, also nicht nur auf direktem Weg zum anderen Knoten kommen kann.

Ich denke die Adjazenzmatrix könnte da helfen die direkten Kanten zwischen den Knoten bzw. die Knoten mit einer direkten Kante innerhalb einer Komponente zu bestimmen.
Woher ich das weiß:Hobby – Beschäftige mich in meiner Freizeit viel mit Computern
Smirror  19.06.2021, 12:03

Hab das mal als Programm implementiert, so wie ich denke, dass du es haben möchtest, vielleicht hilft dir das ja irgendwie.

Graph.java

import java.util.ArrayList;

class Graph {
 
  public Graph() {
    // die Wegematrix
    int[][] wegeMatrix = {
      {1,0,1,1,0},
      {0,1,0,0,1},
      {1,0,1,1,0},
      {1,0,1,1,0},
      {0,1,0,0,1}};

      // berechne Komponenten
      ArrayList<Komponent> komponenten = berechneKomponenten(wegeMatrix);

      // Gebe Komponenten aus
      for(int i=0;i<komponenten.size();i++) {
        System.out.println("Komponente "+i +": "+komponenten.get(i));
      }
  }

  // Methode zum Berechnen der Komponenten
  public ArrayList<Komponent> berechneKomponenten(int[][] w) {
    // initialisiere eine Liste von Komponenten
    ArrayList<Komponent> komponenten = new ArrayList();
    for(int zeile=0;zeile<w.length;zeile++) {
      // erstelle eine Komponente pro Zeile
      Komponent k = new Komponent();
      for (int spalte=0;spalte<w[0].length;spalte++) {
        if(w[zeile][spalte] == 1) {
          // wenn in der Wegematrix eine 1, dann speichere
          // eine Node in der aktuellen Komponente mit
          // jeweiligem Char und index
          int index = spalte;
          Node n = new Node((char)(spalte+65), index);
          k.addNode(n);
        }
      }
      // Sofern die Komponente nicht in der Liste
      // existiert, füge sie hinzu
      if(!komponenten.contains(k)){
        komponenten.add(k);
      }
    }
    // vollständige Liste der Komponenten zurückgeben
    return komponenten;
  }
}

Node.java

class Node {

  protected char c;
  protected int index;

  public Node(char c, int index) {
    this.c = c;
    this.index = index;
  }

  public String toString() {
    return ""+(index+1);
  }

  public boolean equals(Object other) {
    if(!(other instanceof Node)) return false;
    return ((Node)other).c == this.c;
  }

  public int hash(){
    return (int) this.c;
  }
}

Komponent.java

import java.util.ArrayList;

class Komponent {

  protected ArrayList<Node> nodes = new ArrayList();

  public void addNode(Node n) {
    if(!nodes.contains(n)){
      nodes.add(n);
    }
  }

  public boolean equals(Object other) {
    if(!(other instanceof Komponent)) return false;
    Komponent k = (Komponent) other;
    if(k.nodes.size() != this.nodes.size()){
      return false;
    }else {
      for (int i=0; i<this.nodes.size(); i++) {
        if(!(this.nodes.get(i).equals(k.nodes.get(i)))) return false;
      }
    }
    return true;
  }

  public int hash(){
    int i = 0;
    for(int k=0;k<nodes.size();k++){
      i+= Math.pow(2,(int) (nodes.get(k).c));
    }
    return i;
  }

  public String toString() {
    String r = "{";
    for(int i=0;i<this.nodes.size();i++) {
      Node n = this.nodes.get(i);
      if(i==this.nodes.size()-1) {
        r += n.toString()+"";
      }else {
        r += n.toString()+",";
      }
    }
    return r+"}";
  }
}
0
dahjonny
18.06.2021, 10:58

Ich habe mal Binärbaumen als Code realisiert..und ich glaube, dass es eine ähnliche herangehensweise ist. Also wenn du es mit einer Matrix machen willst, kannst du einfach wie @Smirror beschrieben machen...in Java kann man ja einfach Matrizen anlegen.

Zu den Knoten, würde ich eine eigene Klassen Implementieren (nodes).
Woher ich das weiß:Studium / Ausbildung