2、可以采用一样的链表组结构。只是因为是有向图,所以加入元素的时候不用考虑对称节点的问题。在实现上其实也更加简化。 下面是一个关于有向图的简单定义实现: Java代码 1.public class Digraph { 2. private final int vertices; 3. private int edges; 4. private List> adj; 5. 6. public Digraph(int vertices) { 7. if(vertices < 0)
3、 throw new IllegalArgumentException( 8. "Number of vertices in a Digraph must be nonnegative"); 9. this.vertices = vertices; 10. this.edges = 0; 11. adj = new ArrayList>(); 12. for(int i = 0; i < vertices; i++) { 13.
4、 adj.add(new LinkedList()); 14. } 15. } 16. 17. public void addEdge(int v, int w) { 18. if(v < 0
5、
6、 v >= vertices) 19. throw new IndexOutOfBoundsException( 1. "vertex " + v + " not in bound."); 2. if
7、(w < 0
8、
9、 w >= vertices) 3. throw new IndexOutOfBoundsException( 4. "vertex " + w + " not in bound."); 5. adj.get(v).add(w); 6. edges++; 7. } 8.} 这部分代码很简单,无需解释。 有了这部分定义之后,我们再来考虑后面的几个典型的问题。 环的存在和检测 和前面无向图的过程有点类似,我们要检测一个图中间是否存在环,肯定