如何实现 下面两个类中的强连通分量(SCC)与最短路径(shortestPath)
package graphs;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
public class AdjacencyListGraph<T> extends Graph<T> {
Map<T, Vertex> keyToVertex;
private class Vertex {
T key;
List<Vertex> successors;
List<Vertex> predecessors;
Vertex(T key) {
this.key = key;
this.successors = new ArrayList<Vertex>();
this.predecessors = new ArrayList<Vertex>();
}
}
AdjacencyListGraph(Set<T> keys) {
this.keyToVertex = new HashMap<T, Vertex>();
for (T key : keys) {
Vertex v = new Vertex(key);
this.keyToVertex.put(key, v);
}
}
@Override
public int size() {
return this.keyToVertex.size();
}
@Override
public int numEdges() {
int count = 0;
for (Vertex v : this.keyToVertex.values()) {
count += v.successors.size();
}
return count;
}
@Override
public boolean addEdge(T from, T to) {
if (!this.keyToVertex.containsKey(from)) {
throw new NoSuchElementException("Could not find vertex with key " + from.toString());
}
if (!this.keyToVertex.containsKey(to)) {
throw new NoSuchElementException("Could not find vertex with key " + to.toString());
}
Vertex fromV = this.keyToVertex.get(from);
Vertex toV = this.keyToVertex.get(to);
List<Vertex> fromSuccs = fromV.successors;
List<Vertex> toPreds = toV.predecessors;
if (fromSuccs.contains(toV)) {
return false;
}
fromSuccs.add(toV);
toPreds.add(fromV);
return true;
}
@Override
public boolean hasVertex(T key) {
return this.keyToVertex.containsKey(key);
}
@Override
public boolean hasEdge(T from, T to) throws NoSuchElementException {
if (!this.keyToVertex.containsKey(from)) {
throw new NoSuchElementException("Could not find vertex with key " + from.toString());
}
if (!this.keyToVertex.containsKey(to)) {
throw new NoSuchElementException("Could not find vertex with key " + to.toString());
}
Vertex fromV = this.keyToVertex.get(from);
Vertex toV = this.keyToVertex.get(to);
List<Vertex> fromSuccs = fromV.successors;
List<Vertex> toPreds = toV.predecessors;
if (fromSuccs.contains(toV)) {
return true;
}
return false;
}
@Override
public boolean removeEdge(T from, T to) throws NoSuchElementException {
if (!this.keyToVertex.containsKey(from)) {
throw new NoSuchElementException("Could not find vertex with key " + from.toString());
}
if (!this.keyToVertex.containsKey(to)) {
throw new NoSuchElementException("Could not find vertex with key " + to.toString());
}
Vertex fromV = this.keyToVertex.get(from);
Vertex toV = this.keyToVertex.get(to);
if (!this.hasEdge(from, to)) {
return false;
}
List<Vertex> fromSuccs = fromV.successors;
List<Vertex> toPreds = toV.predecessors;
fromSuccs.remove(toV);
toPreds.remove(fromV);
if (!fromSuccs.contains(toV)) {
return true;
}
return false;
}
@Override
public int outDegree(T key) {
return this.keyToVertex.get(key).successors.size();
}
@Override
public int inDegree(T key) {
return this.keyToVertex.get(key).predecessors.size();
}
@Override
public Set<T> vertexSet() {
Set<T> vertexSet = new HashSet<T>();
for (T v : this.keyToVertex.keySet()) {
vertexSet.add(v);
}
return vertexSet;
}
@Override
public List<T> successorList(T key) {
List<T> successorList = new ArrayList<T>();
for (Vertex v : this.keyToVertex.get(key).successors) {
successorList.add(v.key);
}
return successorList;
}
@Override
public List<T> predecessorList(T key) {
List<T> predecessorList = new ArrayList<T>();
for (Vertex v : this.keyToVertex.get(key).predecessors) {
predecessorList.add(v.key);
}
return predecessorList;
}
@Override
public Iterator<T> successorIterator(T key) {
return new theIterator(this.successorList(key));
}
@Override
public Iterator<T> predecessorIterator(T key) {
return new theIterator(this.predecessorList(key));
}
private class theIterator implements Iterator<T> {
List<T> target;
int index = 0;
public theIterator(List<T> theList) {
this.target = theList;
}
@Override
public boolean hasNext() {
return this.index < this.target.size();
}
@Override
public T next() {
if (hasNext()) {
this.index += 1;
return this.target.get(this.index - 1);
}
return null;
}
}
@Override
public Set<T> stronglyConnectedComponent(T key) {
this.keyToVertex.get(key);
// TODO
return null;
}
@Override
public List<T> shortestPath(T startLabel, T endLabel) {
// TODO
return null;
}
}
以及
package graphs;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
public class AdjacencyMatrixGraph<T> extends Graph<T> {
Map<T, Integer> keyToIndex;
List<T> indexToKey;
int[][] matrix;
AdjacencyMatrixGraph(Set<T> keys) {
int size = keys.size();
this.keyToIndex = new HashMap<T, Integer>();
this.indexToKey = new ArrayList<T>();
this.matrix = new int[size][size];
// need to populate keyToIndex and indexToKey with info from keys
for (T each : keys) {
this.indexToKey.add(each);
}
for (int i = 0; i < size; i++) {
this.keyToIndex.put(this.indexToKey.get(i), i);
}
}
@Override
public int size() {
return this.keyToIndex.size();
}
@Override
public int numEdges() {
int count = 0;
for (int i = 0; i < this.matrix.length; i++) {
for (int j = 0; j < this.matrix[i].length; j++) {
count += this.matrix[i][j];
}
}
return count;
}
@Override
public boolean addEdge(T from, T to) {
if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
throw new NoSuchElementException();
}
int iFrom = this.keyToIndex.get(from);
int iTo = this.keyToIndex.get(to);
if (this.matrix[iFrom][iTo] == 1) {
return false;
}
this.matrix[iFrom][iTo] = 1;
return true;
}
@Override
public boolean hasVertex(T key) {
return this.keyToIndex.containsKey(key);
}
@Override
public boolean hasEdge(T from, T to) throws NoSuchElementException {
if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
throw new NoSuchElementException();
}
int iFrom = this.keyToIndex.get(from);
int iTo = this.keyToIndex.get(to);
return this.matrix[iFrom][iTo] == 1;
}
@Override
public boolean removeEdge(T from, T to) throws NoSuchElementException {
if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) {
throw new NoSuchElementException();
}
int iFrom = this.keyToIndex.get(from);
int iTo = this.keyToIndex.get(to);
if (this.matrix[iFrom][iTo] == 0) {
return false;
}
this.matrix[iFrom][iTo] = 0;
return true;
}
@Override
public int outDegree(T key) {
int iFrom = this.keyToIndex.get(key);
int l = this.matrix[iFrom].length;
int out = 0;
for (int i = 0; i < l; i++) {
out += this.matrix[iFrom][i];
}
return out;
}
@Override
public int inDegree(T key) {
int iTo = this.keyToIndex.get(key);
int l = this.matrix.length;
int in = 0;
for (int i = 0; i < l; i++) {
in += this.matrix[i][iTo];
}
return in;
}
@Override
public Set<T> vertexSet() {
Set<T> vertexSet = new HashSet<T>();
for (T v : this.indexToKey) {
vertexSet.add(v);
}
return vertexSet;
}
@Override
public List<T> successorList(T key) {
int iFrom = this.keyToIndex.get(key);
List<T> successorList = new ArrayList<T>();
for (int i = 0; i < this.matrix[iFrom].length; i++) {
if (this.matrix[iFrom][i] == 1) {
successorList.add(this.indexToKey.get(i));
}
}
return successorList;
}
@Override
public List<T> predecessorList(T key) {
int iTo = this.keyToIndex.get(key);
List<T> predecessorList = new ArrayList<T>();
for (int i = 0; i < this.matrix.length; i++) {
if (this.matrix[i][iTo] == 1) {
predecessorList.add(this.indexToKey.get(i));
}
}
return predecessorList;
}
@Override
public Iterator<T> successorIterator(T key) {
return new successorIterator(this.keyToIndex.get(key));
}
private class successorIterator implements Iterator<T> {
int iFrom;
int index = 0;
public successorIterator(int iFrom) {
this.iFrom = iFrom;
}
@Override
public boolean hasNext() {
while (true) {
if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iFrom].length) {
return false;
}
if (AdjacencyMatrixGraph.this.matrix[this.iFrom][this.index] == 1) {
return true;
}
this.index++;
}
}
@Override
public T next() {
if (hasNext()) {
this.index++;
return AdjacencyMatrixGraph.this.indexToKey.get(this.index - 1);
}
return null;
}
}
@Override
public Iterator<T> predecessorIterator(T key) {
return new predecessorIterator(this.keyToIndex.get(key));
}
private class predecessorIterator implements Iterator<T> {
int iTo;
int index = 0;
public predecessorIterator(int iTo) {
this.iTo = iTo;
}
@Override
public boolean hasNext() {
while (true) {
if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iTo].length) {
return false;
}
if (AdjacencyMatrixGraph.this.matrix[this.index][this.iTo] == 1) {
return true;
}
this.index++;
}
}
@Override
public T next() {
if (hasNext()) {
this.index += 1;
return AdjacencyMatrixGraph.this.indexToKey.get(this.index);
}
return null;
}
}
boolean[] visited = new boolean[this.size()];
@Override
public Set<T> stronglyConnectedComponent(T key) {
// TODO
return null;
}
@Override
public List<T> shortestPath(T startLabel, T endLabel) {
// TODO
return null;
}
}