有向圖和無向圖 - Java

我正在實現一些算法來教我自己關於圖的方法以及如何使用它們。你會推薦什麼是在Java中做到這一點的最佳方式？有向圖和無向圖 - Java

我只是想問你，如果你能給出一個簡短的幫助很簡單的類定義有向圖和加權有向圖嗎？

我查看了網頁，但我不想要它的實現，只是類的簡短定義....你認爲是最好的數據結構使用？相鄰列表？

對於無向圖我把它定義爲如下：

public interface Graph { 
    Collection vertices(); // returns a collection of all the 
     // Vertex objects in the graph 
    Collection edges(); // returns a collection of all the 
    // Edge objects in the graph 
    Collection incidentEdges(Vertex v); // returns a collection of 
     // Edges incident to v 
    boolean isAdjacent(Vertex v, Vertex w); // return true if v and  
}     // w are adjacent 

public class Vertex { 
    public boolean visited; // initially false for all vertices 
} 

public class Edge { 
    Vertex v1, v2;  // undirected edge 
    Vertex opposite(Vertex v); // given a vertex return the one 
}   // at the other end of this edge

來源

2013-02-17 Patric

[有向圖的數據結構允許快速節點刪除？]的可能的副本（http://stackoverflow.com/questions/5084421/data-structure-for-directed-graphs-allowing-fast-node-deletion） – Perception 2013-02-17 12:37:33

下面是一個簡單的實現（這應該是很多基本用例不夠好）：

public class Graph { 
    public List<Node> nodes = new ArrayList<Node>(); 
}     

public class Node{ 
    public List<Node> neighbors = new ArrayList<Node>(); 
//here you can add stuff like "public boolean visited;", if your algorithm requires it 
}

（這只是一個例子 - 有很多方法來實現圖結構）。

來源

2013-02-17 14:22:35

要使用的數據結構取決於您的代碼的用途...列表通常做得很好，但如果圖形高度連接（大多數節點連接到大多數節點），則列表是麻煩，而且通常會優選某種矩陣。例如，要使用矩陣，保留節點的向量，然後使用整數的2維向量來引用節點。另外，爲了製作一個輕量級類，您不必爲節點聲明一個類：您可以提供添加節點和邊的函數，並且您可以用整數標識這些元素。

如果您計劃對它們進行子類化（例如，在執行顯示圖形的GUI時可能會有用），那麼具有Node或Edge類可能是合適的，但是如果您需要某些算法的圖形，整數更快更簡單。

來源

2013-02-17 14:41:46 AkiRoss

有向圖和無向圖 - Java

回答

相關問題