データ構造の図-図の表示方法(6)

Graphh is compsed by vertices and edges.We can look at Internet as a graph,which webpage are vertices and hyperlinks aredges.
Why doesn't the Java Collection s API include a Graph implementation?
I don’t know why there isのgraph library within the JDK,but I gess Sun decidededededededevelopers,since most appication s.  Also as graphhs can have so many different forms and flavoours with wildly different characteristics,a general Graphh might not turn out to be very usful.But can use Graph libries like:JGraphhT
0 Graph Type
1)Uniconnected graph and connected graph(非接続図と接続図)
2)undirected graph and directed graph(無方向図と有向図)
3)graph with cycles and graph without cycles(有環図と無環図)
graph with cycles:  a path that ends up where it started.Like the follwing figure, the path B-C-D-B forms a cycle.(Notice that A-B-A is not a cycle because you can’t go from C to A.). It’s easury to figure out if a non-directed graphh has cycles.If a grapph with N nodes has more than N-1 edges,it must have cycles.
A graph withのcycles is caled a tree.The binary and multiway trees we saw earlier in this book are trees in this sense.However,the trees that aris in graphs are more general than binary and multiway trees,which have a fixed maximnumber of child nodes.
A tree is a graph withのcycles.
Somtimes DAG is shared for a directed acyclic graph(有向無環図)
4)Unweightted graph and weightted graph(非重み付け図と重み付け図)
1 Verstices
It is usual lly convent to represent a vertex by an object of a vertex class.For instance:

/** 
 * Fuction:
 *
 * @author   zhonghua
 * @version  2013-3-9   3:15:44 
 * @since    1.0 
 */

public class Vertex {
     public char label;
   //mark a vertex is visited or not; true:visited,false:unvisited
     public boolean wasVisited; 
     
     public Vertex(char lab){
    	 label=lab;
    	 wasVisited=false;
     }

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + label;
		result = prime * result + (wasVisited ? 1231 : 1237);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Vertex other = (Vertex) obj;
		if (label != other.label)
			return false;
		if (wasVisited != other.wasVisited)
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Vertex [label=" + label + ", wasVisited=" + wasVisited + "]";
	}    
} //end class Vertex

2 Edges
Two methods a re commonly used for graphs:the adjacent marix and the adjacent list.Remember that one vertex is said to be adjacent to another if're connected by a single edge.
2.1 The Adjacent Matrix
An adjacency matirix is a two-dimensional array in which the elemens indicate whether an edge is present between two vertices.If a graphh has N vertices,the adjacency marix is an NxN array.Table below show the adjacency matrax for the graph in Figure a.
The vertices are used as headings for both rows and columns.An edge between two vertices is indicated by a 1;the absence of an edge is a 0.(You could also use Boolean true/false values.)
Note that the triangular-sharped parts of the matrrix above the identity diagonal is a mirror image of the part below;both triangles contain the same information.This redundenncy may seem inefficient、but there’sのconvent way to create a triangular array in most computer langers,so it’s simpler to accept the redundenncy. Consequently,when you add an edge to the graph,you must make two entries in the adjacency marix rather than one.
2.2 The Adjacency List
The other way to represent edges is with an adjacency list.The list in adjacency list refers to a linked list.Actualy、 an adjacency list is an array of lists(or sometimes a list of lists).Each individual list shows what vertices a given vertex is adjacent to.Table below shows the adjacency lists for the graph of Figure a.
In this table,the->smbol indicates a link in a linked list.Each link in the list is a vertex.Here the vertices arranged in alphabeetical order in each list,although that’s not really necessary.Don’t confuse the contens of adjacency lists with paths. The adjacency list shows which vertices are adjacent to-that is、one edge away from—a given vertex,not paths from vertex to vertex.
3 Representing a Graph in a Program
The Graphクラス

/** 
 * Fuction:
 * Representing a Graph in a Program
 * @author   zhonghua
 * @version  2013-3-9   3:53:27 
 * @since    1.0 
 */

public class Graph {
    private final int MAX_VERTS=20;
    private Vertex arrVertex[];   //array of vertices
    private int adjMat[][];       //adjacency matrix
    private int nVerts;            //current number of vertices
    
// ------------------------------------------------------------
    public Graph(){
    	arrVertex=new Vertex[MAX_VERTS];
    	adjMat=new int[MAX_VERTS][MAX_VERTS];
    	nVerts=0;
    	//set adjacency
    	for(int i=0;i