Graph.java
public class Graph
{
private ST> st;
private
int E;
public Graph()
{
st = new ST>();
}
public Graph(In in, String delimiter)
{
st = new ST>();
while (in.hasNextLine())
{
String line = in.readLine();
String[] names = line.split(delimiter);
for (int i = 1; i < names.length; i++)
{
addEdge(names[0], names[i]);
}
}
}
public int V()
{
return st.size();
}
public int E()
{
return E;
}
public int degree(String v)
{
if (!st.contains(v)) throw new RuntimeException(v + " is not a
vertex");
else return st.get(v).size();
}
public void addEdge(String v, String w)
{
if (!hasEdge(v, w)) E++;
if (!hasVertex(v)) addVertex(v);
if (!hasVertex(w)) addVertex(w);
st.get(v).add(w);
st.get(w).add(v);
}
public void addVertex(String v)
{
if (!hasVertex(v)) st.put(v, new SET());
}
public Iterable vertices()
{
return st;
}
public Iterable adjacentTo(String v)
{
if (!hasVertex(v)) return new SET();
else
return st.get(v);
}
public boolean hasVertex(String v)
{
return st.contains(v);
}
public boolean hasEdge(String v, String w)
{
if (!hasVertex(v)) return false;
return st.get(v).contains(w);
}
public String toString()
{
String s = "";
for (String v : st)
{
s += v + ": ";
for (String w : st.get(v))
{
s += w + " ";
}
s += "\n";
}
return s;
}
public static void main(String[] args)
{
Graph G = new Graph();
G.addEdge("A", "B");
G.addEdge("A", "C");
G.addEdge("C", "D");
G.addEdge("D", "E");
G.addEdge("D", "G");
G.addEdge("E", "G");
G.addVertex("H");
StdOut.println(G);
for (String v : G.vertices())
{
StdOut.print(v + ": ");
for (String w : G.adjacentTo(v))
{
StdOut.print(w + " ");
}
StdOut.println();
}
}
}
No comments:
Post a Comment