Pemodelan Graf

public class TestGraph { public static void main(String[] args) { String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"}; // Edge array for graph int[][] edges = { {0, 1}, {0, 3}, {0, 5}, {1, 0}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {2, 4}, {2, 10}, {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10}, {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7}, {6, 5}, {6, 7}, {7, 4}, {7, 5}, {7, 6}, {7, 8}, {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11}, {9, 8}, {9, 11}, {10, 2}, {10, 4}, {10, 8}, {10, 11}, {11, 8}, {11, 9}, {11, 10} }; Graph graph1 = new UnweightedGraph<>(vertices, edges); System.out.println("The number of vertices in graph1: " + graph1.getSize()); System.out.println("The vertex with index 1 is " + graph1.getVertex(1)); System.out.println("The index for Miami is " + graph1.getIndex("Miami")); System.out.println("The edges for graph1:"); graph1.printEdges(); // List of Edge objects for graph String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"}; java.util.ArrayList edgeList = new java.util.ArrayList<>(); edgeList.add(new AbstractGraph.Edge(0, 2)); edgeList.add(new AbstractGraph.Edge(1, 2)); edgeList.add(new AbstractGraph.Edge(2, 4)); edgeList.add(new AbstractGraph.Edge(3, 4)); // Create a graph with 5 vertices Graph graph2 = new UnweightedGraph<>(java.util.Arrays.asList(names), edgeList); System.out.println("\nThe number of vertices in graph2: " + graph2.getSize()); System.out.println("Te edges for graph2:"); graph2.printEdges(); } }

public interface Graph { /** Return the number of vertices in the graph */ public int getSize(); /** Return the vertices in the graph */ public java.util.List getVertices(); /** Return the object for the specified vertex index */ public V getVertex(int index); /** Return the index for the specified vertex object */ public int getIndex(V v); /** Return the neighbors of vertex with the specified index */ public java.util.List getNeighbors(int index); /** Return the degree for a specified vertex */ public int getDegree(int v); /** Print the edges */ public void printEdges(); /** Clear the graph */ public void clear(); /** Add a vertex to the graph */ public void addVertex(V vertex); /** Add an edge to the graph */ public void addEdge(int u, int v); /** Obtain a depth-first search tree starting from v */ public AbstractGraph.Tree dfs(int v); /** Obtain a breadth-first search tree starting from v */ public AbstractGraph.Tree bfs(int v); }

import java.util.*; public abstract class AbstractGraph implements Graph { protected List vertices = new ArrayList<>(); // Store vertices protected List> neighbors = new ArrayList<>(); // Adjacency lists /** Construct an empty graph */ protected AbstractGraph() {} /** Construct a graph from vertices and edges stored in arrays */ protected AbstractGraph(V[] vertices, int[][] edges) { for(int i = 0; i < vertices.length; i++) addVertex(vertices[i]); createAdjacencyLists(edges, vertices.length); } /** Construct a graph from vertices and edges stored in List */ protected AbstractGraph(List vertices, List edges) { for(int i = 0; i < vertices.size(); i++) addVertex(vertices.get(i)); createAdjacencyLists(edges, vertices.size()); } /** Construct a graph for integer vertices 0, 1, 2 and edge list */ protected AbstractGraph(List edges, int numberOfVertices) { for(int i = 0; i < numberOfVertices; i++) addVertex((V)(new Integer(i))); // vertices is {0, 1, ...} createAdjacencyLists(edges, numberOfVertices); } /** Construct a graph from integer vertices 0, 1, and edge array */ protected AbstractGraph(int[][] edges, int numberOfVertices) { for(int i = 0; i < numberOfVertices; i++) addVertex((V)(new Integer(i))); // vertices is {0, 1, ...} createAdjacencyLists(edges, numberOfVertices); } /** Create adjacency lists for each vertex */ private void createAdjacencyLists(int[][] edges, int numberOfVertices) { for(int i = 0; i < edges.length; i++) { addEdge(edges[i][0], edges[i][1]); } } /** Create adjacency lists for each vertex */ private void createAdjacencyLists(List edges, int numberOfVertices) { for(Edge edge: edges) { addEdge(edge.u, edge.v); } } @Override /** Return the number of vertices in the graph */ public int getSize() { return vertices.size(); } @Override /** Return the vertices in the graph */ public List getVertices() { return vertices; } @Override /** Return the object for the specified vertex */ public V getVertex(int index) { return vertices.get(index); } @Override /** Return the index for the specified vertex object */ public int getIndex(V v) { return vertices.indexOf(v); } @Override /** Return the neighbors of the specified vertex */ public List getNeighbors(int index) { List result = new ArrayList<>(); for(Edge e: neighbors.get(index)) result.add(e.v); return result; } @Override /** Return the degree for a specified vertex */ public int getDegree(int v) { return neighbors.get(v).size(); } @Override /** Print the edges */ public void printEdges() { for(int u = 0; u < neighbors.size(); u++) { System.out.print(getVertex(u) + " (" + u + "): "); for(Edge e: neighbors.get(u)) { System.out.print("(" + getVertex(e.u) + ", " + getVertex(e.v) + ") "); } System.out.println(); } } @Override /** Clear the graph */ public void clear() { vertices.clear(); neighbors.clear(); } @Override /** Add a vertex to the graph */ public void addVertex(V vertex) { if(!vertices.contains(vertex)) { vertices.add(vertex); neighbors.add(new ArrayList()); } } /** Add an edge to the graph */ protected boolean addEdge(Edge e) { if(e.u < 0 || e.u > getSize() - 1) throw new IllegalArgumentException("No such index: " + e.u); if(e.v < 0 || e.v > getSize() - 1) throw new IllegalArgumentException("No such index: " + e.v); if(!neighbors.get(e.u).contains(e)) { neighbors.get(e.u).add(e); return true; } else { return false; } } @Override /** Add an edge to the graph */ public void addEdge(int u, int v) { addEdge(new Edge(u, v)); } /** Edge inner class inside the AbstractGraph class */ public static class Edge { public int u; // Starting vertex of the edge public int v; // Ending vertex of the edge /** Construct an edge for (u, v) */ public Edge(int u, int v) { this.u = u; this.v = v; } public boolean equals(Object o) { return u == ((Edge)o).u && v == ((Edge)o).v; } } @Override /** Obtain a DFS tree starting from vertex v */ public Tree dfs(int v) { List searchOrder = new ArrayList<>(); int[] parent = new int[vertices.size()]; for(int i = 0; i < parent.length; i++) parent[i] = -1; // Initialize parent[i] to -1 // Mark visited vertices boolean[] isVisited = new boolean[vertices.size()]; // Recursively search dfs(v, parent, searchOrder, isVisited); // Return a search tree return new Tree(v, parent, searchOrder); } /** Recursive method for DFS search */ private void dfs(int u, int[] parent, List searchOrder, boolean[] isVisited) { // Store the visited vertex searchOrder.add(u); isVisited[u] = true; // Vertex v visited for(Edge e: neighbors.get(u)) { if(!isVisited[e.v]) { parent[e.v] = u; // The parent of vertex e.v is u dfs(e.v, parent, searchOrder, isVisited); // Recursive search } } } @Override /** Starting bfs search from vertex v */ public Tree bfs(int v) { List searchOrder = new ArrayList<>(); int[] parent = new int[vertices.size()]; for(int i = 0; i < parent.length; i++) parent[i] = -1; // Initialize parent[i] to -1 java.util.LinkedList queue = new java.util.LinkedList<>(); // list used as queue boolean[] isVisited = new boolean[vertices.size()]; queue.offer(v); // Enqueue v isVisited[v] = true; // Mark it visited while(!queue.isEmpty()) { int u = queue.poll(); // Dequeue to u searchOrder.add(u); // u searched for(Edge e: neighbors.get(u)) { if(!isVisited[e.v]) { queue.offer(e.v); // Enqueue w parent[e.v] = u; // The parent of w is u isVisited[e.v] = true; // Mark it visited } } } return new Tree(v, parent, searchOrder); } /** Tree inner class inside the AbstractGraph class */ public class Tree { private int root; // The root of the tree private int[] parent; // Store the parent of each vertex private List searchOrder; // Store the search order /** Construct a tree with root, parent, and searchOrder */ public Tree(int root, int[] parent, List searchOrder) { this.root = root; this.parent = parent; this.searchOrder = searchOrder; } /** Return the root of the tree */ public int getRoot() { return root; } /** Return the parent of vertex v */ public int getParent(int v) { return parent[v]; } /** Return an array representing search order */ public List getSearchOrder() { return searchOrder; } /** Return number of vertices found */ public int getNumberOfVerticesFound() { return searchOrder.size(); } /** Return the path of vertices from a vertex to the root */ public List getPath(int index) { ArrayList path = new ArrayList<>(); do { path.add(vertices.get(index)); index = parent[index]; } while(index != -1); return path; } /** Print a path from the root vertex v */ public void printPath(int index) { List path = getPath(index); System.out.print("A path from " + vertices.get(root) + " to " + vertices.get(index) + ": "); for(int i = path.size() - 1; i >= 0; i--) System.out.print(path.get(i) + " "); } /** Print the whole tree */ public void printTree() { System.out.println("Root is: " + vertices.get(root)); System.out.print("Edges: "); for(int i = 0; i < parent.length; i++) { if(parent[i] != -1) { // Display an edge System.out.print("(" + vertices.get(parent[i]) + "' " + vertices.get(i) + ") "); } } System.out.println(); } } }

import java.util.*; public class UnweightedGraph extends AbstractGraph { /** Construct an empty graph */ public UnweightedGraph() {} /** Construct a graph from vertices and edges stored in arrays */ public UnweightedGraph(V[] vertices, int[][] edges) { super(vertices, edges); } /** Construct a graph from vertices and edges stored in List */ public UnweightedGraph(List vertices, List edges) { super(vertices, edges); } /** Construct a graph for integer vertices 0, 1, 2, and edge list */ public UnweightedGraph(List edges, int numberOfVertices) { super(edges, numberOfVertices); } /** Construct a graph from integer vertices 0, 1, and edge array */ public UnweightedGraph(int[][] edges, int numberOfVertices) { super(edges, numberOfVertices); } }