13Oct

## Breadth First Search, Depth First Search and Dijkstra in Graphs Represented as Matricies

So in my previous post a year ago. My graphing was actually based around small cases. Cases where verticies and edges could be represented as objects; however, in the real world this completely not optimal and does not work…

Dijkstra’s

```**
* This method performs a breadth first search. It will color all nodes,
* list discovery times, and specify the discovery node. This can be used
* information can then be accessed from the graph class.
* @param startNode
* The Vertex at which to start the search
*/
private void dijsktra(int sx, int sy, int ex, int ey){
int height = this.allNodes.length;
int width = this.allNodes.length;
nodes = new Node[height][width];
PriorityQueue<Node> q = new PriorityQueue<Node>(10000);
q.offer(new Node(sx,sy,1,null,0,-1));
out:
while(!q.isEmpty()){
Node u = q.poll();
for (int i=0; i<dy.length;i++){
int x = u.x+dx[i];
int y = u.y+dy[i];
if (x >= 0 && x < width && y >= 0 && y < height && allNodes[y][x] != 'x'){
Node a = new Node(x,y,1,u,u.weightFromStart+direction(i),i);
if(Math.abs(a.weightFromStart-u.weightFromStart)>epsilon){
if (nodes[y][x]!=null && a.compareTo(nodes[y][x])==1){
q.remove(nodes[y][x]);
nodes[y][x] = a;
q.offer(a);
}
else if (nodes[y][x]==null){
nodes[y][x] = a;
q.offer(a);
}
}
}
}
}
}

```

char label may have been assignment specific. I don’t remember what it is for. I believe it is just the label I wanted to mark things with.

```private static void bfs(int starti, int startj, char label){
int height = maze.length;
int width = maze.length;
//set color
discovery[starti][startj]=1;
//set discovery time
discovery[starti][startj]=0;
//create queue
ArrayBlockingQueue<Integer[]> q = new ArrayBlockingQueue<Integer[]>(10000);
Integer[] a = {starti,startj};
q.offer(a);
while(!q.isEmpty())
{
Integer[] u = q.poll();
for (int i=0;i<dx.length;i++){
if ((u+dx[i]<height && u+dy[i]<width)&&(((u+dx[i]>=0 && u+dy[i]>=0)&&(maze[u+dx[i]][u+dy[i]]!='x'&&maze[u][u]!='x'))&&discovery[u+dx[i]][u+dy[i]]==0)){
//color
discovery[u+dx[i]][u+dy[i]] = 1;
//disc time
discovery[u+dx[i]][u+dy[i]] = discovery[u][u] + 1;
//pi
discovery[u+dx[i]][u+dy[i]] = u;
discovery[u+dx[i]][u+dy[i]] = u;
//update queue
Integer[] b = {u+dx[i],u+dy[i]};
q.offer(b);
}
}
discovery[u][u] = 2;
if (maze[u][u]!='x')
maze[u][u] = label;
}
}

```

Actually I don’t have depth first, but it is pretty similar. I am just you could figure it out :)!

Maybe I will include Kruskals and Prims sometime. I have those coded too. Hope this helps someone.