public class GraphNode {
int label;
ArrayList neighbors;
GraphNode(int x) { label = x; neighbors = new ArrayList(); }
};
Or represented by both node and edges if edges have different weights.
public class Vertex {
final private String id;
final private String name;
public Vertex(String id, String name) {
this.id = id;
this.name = name;
}
//getter and setter methods
}
public class Edge {
private final String id;
private final Vertex source;
private final Vertex destination;
private final int weight;
public Edge(String id, Vertex source, Vertex destination, int weight) {
this.id = id;
this.source = source;
this.destination = destination;
this.weight = weight;
}
//getter and setter methods
}
public class Graph {
private final List vertexes;
private final List edges;
public Graph(List vertexes, List edges) {
this.vertexes = vertexes;
this.edges = edges;
}
public List getVertexes() {
return vertexes;
}
public List getEdges() {
return edges;
}
With above data setup, then some simple task like: searching for neighbors of one vertex is like:
private ListgetNeighbors(Vertex node) { List neighbors = new ArrayList (); for (Edge edge : edges) { if (edge.getSource().equals(node)) { neighbors.add(edge.getDestination()); } } return neighbors; }
The distance between two nodes is:
private int getDistance(Vertex node, Vertex target) {
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& edge.getDestination().equals(target)) {
return edge.getWeight();
}
}
throw new RuntimeException("Should not happen");
}
- Question: finds the shortest path from a source to all destination in a directed graph Answer: classical Dijkstra algorithm, refer to Tutorial and Wiki.
Question: Permutation
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Answer:
Solution#1
public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] num) { if (num==null) return null; return permuteHelper(num, 0); } //create a helper method to avoid cut elements from array num public ArrayList<ArrayList<Integer>> permuteHelper(int[] num, int startIdx) { int length=num.length; ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if(length==startIdx) { ArrayList<Integer> emptyList = new ArrayList<Integer>(); result.add(emptyList); return result; } int firstNum = num[startIdx]; ArrayList<ArrayList<Integer>> subPermutations = permuteHelper(num, startIdx+1); for(ArrayList<Integer> subPers: subPermutations) { for (int i=0; i<=subPers.size(); i++) { ArrayList<Integer> newArray = addElementToIth(subPers,i,firstNum); result.add(newArray); } } return result; } //creating a new ArrayList by inserting newNum at its 'idx' index place public ArrayList<Integer> addElementToIth(ArrayList<Integer> arrList, int idx, int newNum) { ArrayList<Integer> newArr = new ArrayList<Integer>(); int length = arrList.size(); for(int i=0; i<=length; i++) { if(i==idx) { newArr.add(newNum); } //check if i<=length to avoid outOfIndex error if(i!=length) { newArr.add(arrList.get(i)); } } return newArr; } }
public class DijkstraAlgorithm {
private final List nodes;
private final List edges;
private Set settledNodes;
private Set unSettledNodes;
private Map predecessors;
private Map distance;
public DijkstraAlgorithm(Graph graph) {
// create a copy of the array so that we can operate on this array
this.nodes = new ArrayList(graph.getVertexes());
this.edges = new ArrayList(graph.getEdges());
}
public void execute(Vertex source) {
settledNodes = new HashSet();
unSettledNodes = new HashSet();
distance = new HashMap();
predecessors = new HashMap();
distance.put(source, 0);
unSettledNodes.add(source);
while (unSettledNodes.size() > 0) {
Vertex node = getMinimum(unSettledNodes);
settledNodes.add(node);
unSettledNodes.remove(node);
findMinimalDistances(node);
}
}
private void findMinimalDistances(Vertex node) {
List adjacentNodes = getNeighbors(node);
for (Vertex target : adjacentNodes) {
if (getShortestDistance(target) > getShortestDistance(node)
+ getDistance(node, target)) {
distance.put(target, getShortestDistance(node)
+ getDistance(node, target));
predecessors.put(target, node);
unSettledNodes.add(target);
}
}
}
private int getDistance(Vertex node, Vertex target) {
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& edge.getDestination().equals(target)) {
return edge.getWeight();
}
}
throw new RuntimeException("Should not happen");
}
private List getNeighbors(Vertex node) {
List neighbors = new ArrayList();
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& !isSettled(edge.getDestination())) {
neighbors.add(edge.getDestination());
}
}
return neighbors;
}
private Vertex getMinimum(Set vertexes) {
Vertex minimum = null;
for (Vertex vertex : vertexes) {
if (minimum == null) {
minimum = vertex;
} else {
if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
minimum = vertex;
}
}
}
return minimum;
}
private boolean isSettled(Vertex vertex) {
return settledNodes.contains(vertex);
}
private int getShortestDistance(Vertex destination) {
Integer d = distance.get(destination);
if (d == null) {
return Integer.MAX_VALUE;
} else {
return d;
}
}
/*
* This method returns the path from the source to the selected target and
* NULL if no path exists
*/
public LinkedList getPath(Vertex target) {
LinkedList path = new LinkedList();
Vertex step = target;
// check if a path exists
if (predecessors.get(step) == null) {
return null;
}
path.add(step);
while (predecessors.get(step) != null) {
step = predecessors.get(step);
path.add(step);
}
// Put it into the correct order
Collections.reverse(path);
return path;
}
