Adjacency lists to represent a graph using O space (number of edges)
I am trying to represent a graph (linked - not directed without weights) in java using adjacency lists (space to represent the graph should be O (m) where m is the number of edges) to find information about BFS. I am getting plot information from a txt called graph.txt. I'm not sure if I'm using O (m) space to save the graph, and also I'm not sure if this is a good way to save it in order to use BFS.
public class Vertex {
boolean visited = false;
int number;
ArrayList<Integer> adjList;
public Vertex(int i) {
this.number= i;
adjList = new ArrayList<Integer>();
}
public void addNeighbor(int i) {
this.adjList.add(i);
}
}
source to share
While you can of course make this view, you will need to access Vertex
it number
without looking for the entire graph. To do this, you need a list or array of v[]
objects Vertex
, so it v[i].number
always equals i
.
Since you will need this array / list anyway, you can pre-fill it with "empty" Vertex
objects and change the view to use a list of objects Vertex
instead of Integer
s, thereby reducing indirection:
public class Vertex {
int number;
List<Vertex> adjList = new ArrayList<Vertex>();
public Vertex(int i) {
this.number= i;
}
public void addNeighbor(Vertex v) {
adjList.add(v);
}
}
Note that saving visited
along with Vertex
is probably a bad idea because it visited
is part of the state of the algorithm, not part of the graph view. You should keep the visited
boolean array separate from your view and only for the duration of the BFS execution:
static void bfs(Vertex[] v, int start) {
boolean[] visited = new boolean[graph.length];
Queue<Vertex> q = new Deque<Vertex>();
q.add(v[start]);
while (q.peek() != null) {
Vertex c = q.remove();
if (visited[c.getNumber()]) {
continue;
}
// Do something with the current vertex c
...
// Mark c visited, and add its neighbors to the queue
visited[c.getNumber()] = true;
for (Vector a : c.neighbors()) {
q.add(a);
}
}
}
source to share
Yes, your view uses O (m) space. I have two different suggestions based on your view.
1. If you really want to represent a Vertex as a class, then let the list of adjacent vertices be List <Vertex> instead of List <Integer>
or
2. Since your Vertex class doesn't seem to contain any information other than the Integer value of faith, why not just use the Integer itself? Then the graph can be represented as
ArrayList<ArrayList<Integer>> graph;
Where graph [i] is the list of vertices associated with vertex i This makes it so you don't need to match from your integer id to the Vertex instance.
source to share