グラフ-隣接行列表示
4195 ワード
1,隣接行列は有向図を示す
2,隣接行列無方向図
public class AdjacencyWDigraph extends Graph {
int n; // number of vertices
int e; // number of edges
Object[][] a; // adjacency array
public AdjacencyWDigraph(int theVertices) {
if (theVertices < 0)
throw new IllegalArgumentException(
"number of vertices must be >= 0");
n = theVertices;
a = new Object[n + 1][n + 1];
}
public AdjacencyWDigraph() {
this(0);
}
public int vertices() {
return n;
}
public int edges() {
return e;
}
public boolean existsEdge(int i, int j) {
if (i < 1 || j < 1 || i > n || j > n || a[i][j] == null)
return false;
else
return true;
}
public void putEdge(Object theEdge) {
WeightedEdge edge = (WeightedEdge) theEdge;
int v1 = edge.vertex1;
int v2 = edge.vertex2;
if (v1 < 1 || v2 < 1 || v1 > n || v2 > n || v1 == v2)
throw new IllegalArgumentException("(" + v1 + "," + v2
+ ") is not a permissible edge");
if (a[v1][v2] == null) // new edge
e++;
a[v1][v2] = edge.weight;
}
public void removeEdge(int i, int j) {
if (i >= 1 && j >= 1 && i <= n && j <= n && a[i][j] != null) {
a[i][j] = null;
e--;
}
}
public int degree(int i) {
throw new NoSuchMethodError();
}
public int outDegree(int i) {
if (i < 1 || i > n)
throw new IllegalArgumentException("no vertex " + i);
int sum = 0;
for (int j = 1; j <= n; j++)
if (a[i][j] != null)
sum++;
return sum;
}
public int inDegree(int i) {
if (i < 1 || i > n)
throw new IllegalArgumentException("no vertex " + i);
int sum = 0;
for (int j = 1; j <= n; j++)
if (a[j][i] != null)
sum++;
return sum;
}
public void output() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
System.out.print(a[i][j] + " ");
System.out.println();
}
}
public Iterator iterator(int i) {
if (i < 1 || i > n)
throw new IllegalArgumentException("no vertex " + i);
return new VertexIterator(i);
}
private class VertexIterator implements Iterator {
private int v; // the vertex being iterated
private int nextVertex;
public VertexIterator(int i) {
v = i;
for (int j = 1; j <= n; j++)
if (a[v][j] != null) {
nextVertex = j;
return;
}
nextVertex = n + 1;
}
public boolean hasNext() {
return nextVertex <= n;
}
public Object next() {
if (nextVertex <= n) {
int u = nextVertex;
for (int j = u + 1; j <= n; j++)
if (a[v][j] != null) {
nextVertex = j;
return new WeightedEdgeNode(u, a[v][u]);
}
// no next adjacent vertex for v
nextVertex = n + 1;
return new WeightedEdgeNode(u, a[v][u]);
} else
throw new NoSuchElementException("no next vertex");
}
/** unsupported method */
public void remove() {
throw new UnsupportedOperationException();
}
}
}
2,隣接行列無方向図
public class AdjacencyWGraph extends AdjacencyWDigraph {
public AdjacencyWGraph(int theVertices) {
super(theVertices);
}
public AdjacencyWGraph() {
this(0);
}
public void putEdge(Object theEdge) {
WeightedEdge edge = (WeightedEdge) theEdge;
int v1 = edge.vertex1;
int v2 = edge.vertex2;
if (v1 < 1 || v2 < 1 || v1 > n || v2 > n || v1 == v2)
throw new IllegalArgumentException("(" + v1 + "," + v2
+ ") is not a permissible edge");
if (a[v1][v2] == null) // new edge
e++;
a[v1][v2] = edge.weight;
a[v2][v1] = edge.weight;
}
public void removeEdge(int i, int j) {
if (i >= 1 && j >= 1 && i <= n && j <= n && a[i][j] != null) {
a[i][j] = null;
a[j][i] = null;
e--;
}
}
public int degree(int i) {
if (i < 1 || i > n)
throw new IllegalArgumentException("no vertex " + i);
int sum = 0;
for (int j = 1; j <= n; j++)
if (a[i][j] != null)
sum++;
return sum;
}
public int outDegree(int i) {
return degree(i);
}
public int inDegree(int i) {
return degree(i);
}
}