http://www.algolist.net/Data_structures/Graph/Internal_representation
Adjacency matrix
Java implementation using a dictionary (HashMap)
http://www.sanfoundry.com/java-program-describe-representation-graph-using-adjacency-list/
https://gist.github.com/tnhansel/11441647
http://opendatastructures.org/ods-java/12_2_AdjacencyLists_Graph_a.html
int n;
List<Integer>[] adj;
AdjacencyLists(int n0) {
n = n0;
adj = (List<Integer>[])new List[n];
for (int i = 0; i < n; i++)
adj[i] = new ArrayStack<Integer>(Integer.class);
}
Adjacency matrix
Advantages. Adjacency matrix is very convenient to work with. Add (remove) an edge can be done in O(1) time, the same time is required to check, if there is an edge between two vertices. Also it is very simple to program and in all our graph tutorials we are going to work with this kind of representation.
Disadvantages.
- Adjacency matrix consumes huge amount of memory for storing big graphs. All graphs can be divided into two categories, sparse and dense graphs. Sparse ones contain not much edges (number of edges is much less, that square of number of vertices, |E| << |V|2). On the other hand, dense graphs contain number of edges comparable with square of number of vertices. Adjacency matrix is optimal for dense graphs, but for sparse ones it is superfluous.
- Next drawback of the adjacency matrix is that in many algorithms you need to know the edges, adjacent to the current vertex. To draw out such an information from the adjacency matrix you have to scan over the corresponding row, which results in O(|V|) complexity. For the algorithms like DFS or based on it, use of the adjacency matrix results in overall complexity of O(|V|2), while it can be reduced to O(|V| + |E|), when using adjacency list.
- The last disadvantage, we want to draw you attention to, is that adjacency matrix requires huge efforts for adding/removing a vertex. In case, a graph is used for analysis only, it is not necessary, but if you want to construct fully dynamic structure, using of adjacency matrix make it quite slow for big graphs.
public class Graph {
private boolean adjacencyMatrix[][];
private int vertexCount;
public Graph(int vertexCount) {
this.vertexCount = vertexCount;
adjacencyMatrix = new boolean[vertexCount][vertexCount];
}
public void addEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {
adjacencyMatrix[i][j] = true;
adjacencyMatrix[j][i] = true;
}
}
public void removeEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {
adjacencyMatrix[i][j] = false;
adjacencyMatrix[j][i] = false;
}
}
public boolean isEdge(int i, int j) {
if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)
return adjacencyMatrix[i][j];
else
return false;
}
}
Adjacency list
Advantages. Adjacent list allows us to store graph in more compact form, than adjacency matrix, but the difference decreasing as a graph becomes denser. Next advantage is that adjacent list allows to get the list ofadjacent vertices in O(1) time, which is a big advantage for some algorithms.
Disadvantages.
- Adding/removing an edge to/from adjacent list is not so easy as for adjacency matrix. It requires, on the average, O(|E| / |V|) time, which may result in cubical complexity for dense graphs to add all edges.
- Check, if there is an edge between two vertices can be done in O(|E| / |V|) when list of adjacent vertices is unordered or O(log2(|E| / |V|)) when it is sorted. This operation stays quite cheap.
- Adjacent list doesn't allow us to make an efficient implementation, if dynamically change of vertices number is required. Adding new vertex can be done in O(V), but removal results in O(E) complexity.
To sum up, adjacency list is a good solution for sparse graphs and lets us changing number of vertices more efficiently, than if using an adjacent matrix. But still there are better solutions to store fully dynamic graphs.
https://algocoding.wordpress.com/2014/08/24/adjacency-list-representation-of-a-graph-python-java/
Java implementation using an ArrayList of ArrayLists
ArrayList<ArrayList<Integer>> adjLists = new ArrayList<ArrayList<Integer>>();HashMap<Integer, ArrayList<Integer>> adjLists_dict = new HashMap<Integer, ArrayList<Integer>>();http://www.sanfoundry.com/java-program-describe-representation-graph-using-adjacency-list/
https://gist.github.com/tnhansel/11441647
| public class GraphAdjacencyList { | |
| /* Makes use of Map collection to store the adjacency list for each vertex.*/ | |
| private Map<Integer, List<Integer>> Adjacency_List; | |
| /* | |
| * Initializes the map to with size equal to number of vertices in a graph | |
| * Maps each vertex to a given List Object | |
| */ | |
| public GraphAdjacencyList(int number_of_vertices) | |
| { | |
| Adjacency_List = new HashMap<Integer, List<Integer>>(); | |
| for (int i = 1 ; i <= number_of_vertices ; i++) | |
| { | |
| Adjacency_List.put(i, new LinkedList<Integer>()); | |
| } | |
| } | |
| /* Adds nodes in the Adjacency list for the corresponding vertex */ | |
| public void setEdge(int source , int destination) | |
| { | |
| if (source > Adjacency_List.size() || destination > Adjacency_List.size()) | |
| { | |
| System.out.println("the vertex entered in not present "); | |
| return; | |
| } | |
| List<Integer> slist = Adjacency_List.get(source); | |
| slist.add(destination); | |
| List<Integer> dlist = Adjacency_List.get(destination); | |
| dlist.add(source); | |
| } | |
| /* Returns the List containing the vertex joining the source vertex */ | |
| public List<Integer> getEdge(int source) | |
| { | |
| if (source > Adjacency_List.size()) | |
| { | |
| System.out.println("the vertex entered is not present"); | |
| return null; | |
| } | |
| return Adjacency_List.get(source); | |
| } | |
| } |
int n;
List<Integer>[] adj;
AdjacencyLists(int n0) {
n = n0;
adj = (List<Integer>[])new List[n];
for (int i = 0; i < n; i++)
adj[i] = new ArrayStack<Integer>(Integer.class);
}
