CSE/IT 213 - BFS & Linked Lists

New Mexico Tech

October 14, 2011

Breadth-First Searching (BFS)

The idea: visit all the vertices that are adjacent to a
starting vertex, then all vertices two edges apart, and so
on, until all vertices in the same connected component
as the starting vertex are visited. If there are remaining
unvisited vertices, restart the algorithm at an arbitrary
vertex of another connected component of the graph.

Pseudo-code BFS
//Input Graph G = (V,E)
//Output: Graph G with vertices marked with
//consecutive integers in the order they are visted
Mark each vertex v in V with a 0
//0 means vertex unvisited
count <-- 0
for each vertex v in V do
if v is marked with 0
bfs(v)
2

bfs(v)
//visits all the unvisited vertices adjacent to v
//by a path and numbers them in order they
//are visited via the global variable count
count <-- count + 1
mark v with count and initialize a queue with v
while queue is not empty
//front vertex - the vertex first in line in the queue
for each vertex w in V adjacent to the front vertex
if w is marked with 0
count <-- count + 1
add w to the queue
remove front vertex from queue

Linked Lists
Goal: Design a link list in Java
Nodes a node an object that contains data as well as
references to another node.
Nodes have at least two fields one which holds the
address of another node
Nodes are self-referential or recursive data structures

public class Node {

public String data;
public Node next;
public Node() {
this.data = "";
this.next = null;
}
public Node(String s) {
this.data = s;
this.next = null;
}
}
4

To use:
Node p = new Node("Apple");
Node q = new Node("Google");
p.next = q; //Apple points to Google node
//p.next holds the address of the Google node

import java.util.*;
public class Chain {
private class Node
{
5

private String data;

private Node next;
public Node() {
data = "";
next = null;
}
public Node(String s) {
this.data = s;
this.next = null;
}
}
private Node front; //hold address of first node

public Chain() {
Scanner input = new Scanner (System.in);
String name;
Node q, r;
System.out.print("Enter name: Press <Enter> to end");
name = input.nextLine();
//create first node
front = new Node(name);
q = front;
System.out.print("Enter name: ");
name = input.nextLine();

while(!name.equals("")) {
r = new Node(name); //get new node
q.next = r; //link prev. node
q = r; //move q to new node
System.out.print("Enter name: ");
name = input.nextLine();
}
}
public void printChain()
{
Node q = front;
System.out.println("the cahin of nodes are:");
while (q != null) {
System.out.println(q.data);

q = q.next;
}
}
public static void main(String[] args) {
Chain chain = new Chain();
chain.printChain();
}
}

What is that private class Node doing inside the class?

Node is called an inner class
Node exists only for Chains convenience.
Use inner classes when class only has meaning within
the context of another class

Inner Classes
Methods of inner class have direct access to variables
and methods of the surrounding outer class.
The methods of the outer class can only access the an
inner class field or or invoke an inner class method only
via an object of the inner class.

This is wrong
public class BadOuter {
private class Inner
{
private String inStr;
}
public void setName(String name) {
inStr = name; //wrong
}
}

The fix
public class GoodOuter {
private class Inner
{
private String inStr;
}
public void setName(String name) {
Inner inner = new Inner();
inner.inStr = name;
}
}
9

Can do better. The list works only for data of types

strings.
Abstract Linked List
What constitutes a Linked List Interface?

10

The interface
public interface ListInterface<E> {
/** insert x into position index */
void add(int index, E x);
/** adds x to the end of the list */
void add(E x);
/**removes all objects from the list */
void clear();
/** returns true if x is a member of the list */
boolean contains(E x);
11

/** returns the object at position index */

E get (int index);
/**returns true if list is empty */
boolean isEmpty();
/** if x is a memebr of the list
* removes the first occurence of
* x from the list. */
boolean remove(E x);
/**removes and return the object a postion index */
E remove (int index);
/** replaces the object at index at position index

* returns the replaced object */

E set (int index, E x);
/**returns the number of objects ccurrently in list */
int size();
}

The Linked List LList<E> implementation

public class LList<E> implements ListInterface<E> {
private class Node
{
private E data;
private Node next;
public Node() {
this.data = null;
this.next = null;
}
public Node(E x) {
12

this.data = x;
this.next = null;
}
} //end Node
//instance variable
//list locators
private Node front, rear, current;
private int length; //size of list
public LList() {
this.front = this.rear = this.current = null;
this.length = 0;
}

/** insert x into position index */

public void add(int index, E x) {
if (index > this.length) {
System.out.println("index out of range
in add(int index, E x)");
System.exit(0);
}
Node p = new Node(x);
//add to front of list
if (index == 0) {
p.next = front;
front = p;
if(rear == null)

rear = front;
current = front;
length++;
return;
}
//add at rear of list
if( index == length) {
add(x);
return;
}
//add other place
Node q = front;
for(int i = 0; i < index - 1; i++)

q = q.next;
Node r = q.next;
q.next = p;
p.next = r;
current = front;
length++;
}

/** adds x to the end of the list */

public void add(E x) {
Node p = new Node(x);
if(rear == null)
front = rear = p;
else {

rear.next = p;
rear = p;
}
current = front;
length++;
}
/**removes all objects from the list */
public void clear() {
front = rear = null;
length = 0;
}
/** returns true if x is a member of the list */

public boolean contains(E x) {

Node p = front;
for(int i = 0; i < length; i++) {
if(x.equals(p.data)) //equals method from E class
//maybe overridden
return true;
p = p.next;
}
return false;
}
/** returns the object at position index */
public E get (int index) {
if (index > this.length) {
System.out.println("index out of range

in get(int index)");
System.exit(0);
}
Node p = front;
for(int i = 0; i< index; i++)
p = p.next;
return p.data;
}
/**returns true if list is empty */
public boolean isEmpty() {
return length == 0;
}

/** if x is a memebr of the list

* removes the first occurence of
* x from the list. */
public boolean remove(E x) {
Node p = front;
Node q = null;
while(!(p == null) && !x.equals(p.data)) {
q = p; //q trails p by one
p = p.next;
}
if (p == null)
return false;
if (!(q == null)) //if x is in first node q is null
q.next = p.next;

if (p == front)
front = front.next;
if (p == rear)
rear = q;
length--;
return true;
}
/**removes and return the object a position index */
public E remove (int index) {
if (index > this.length) {
System.out.println("index out of range
in remove(int index)");

System.exit(0);
}
Node p = front;
Node q = null;
for (int i =0; i <index; i++) {
q = p; //q trails p by one
p = p.next;
}
if (current == p)
current = p.next;
if (!(q == null)) //if x is in first node q is null
q.next = p.next;
if (p == front)
front = front.next;

if (p == rear)
rear = q;
length--;
return p.data;
}
/** replaces the object at index at position index
* returns the replaced object */
public E set (int index, E x) {
if (index > this.length) {
System.out.println("index out of range
in set(int index)");
System.exit(0);
}

Node p = front;
for(int i = 0; i< index; i++)
p = p.next;
E tmp = p.data;
p.data = x;
return tmp;
}
/**returns the number of objects ccurrently in list */
public int size() {
return length;
}

public void reset() {

current = front;
}
//reeturns true if a call to next will be successful
public boolean hasNext() {
if(current == null)
return false;
return true;
}
//returns data of current node
//moves current to next node
public E next() {
if(current == null) {

System.out.println("Error in hasNext");
System.exit(0);
}
E tmp = current.data;
current = current.next;
return tmp;
}
}

public class LLTest {

public static void main(String[] args) {
final int SIZE = 10000;
LList<Integer> list = new LList<Integer>();
long start = System.currentTimeMillis();
for(int i = 0; i < SIZE; i++)
list.add(i); //add to rear
long end = System.currentTimeMillis();
for (int i = 0; i < 10; i++)
System.out.println(list.get(i));
13

System.out.println("Time to add to rear of

list = " + (end - start));
list.clear();
System.out.println();
start = System.currentTimeMillis();
for(int i = 0; i < SIZE; i++)
list.add(0,i); //add to front
end = System.currentTimeMillis();
System.out.println(list.size());
for (int i = 0; i < 10; i++)
System.out.println(list.get(i));
System.out.println("Time to add to front of

list = " + (end - start));

}
}

0
1
2
3
4
5
6
7
8

9
Time to add to rear of list = 5
10000
9999
9998
9997
9996
9995
9994
9993
9992
9991
9990
Time to add to front of list = 5

Why next() and hasNext()?

Much more efficient than get
public class LLTest {
public static void main(String[] args) {
final int SIZE = 10000;
LList<Integer> list = new LList<Integer>();
for(int i = 0; i < SIZE; i++)
list.add(i); //add to rear
long start = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++)
14

list.get(i);
long end = System.currentTimeMillis();
System.out.println("Time for get = " + (end - start));
System.out.println();
start = System.currentTimeMillis();
while(list.hasNext()) {
list.next();
}
end = System.currentTimeMillis();

System.out.println("Time for hasNext = " + (end - start));

}

}
Time for get = 102
Time for hasNext = 1
Why does it take longer for get than hasNext?
get starts at the beginning each time it is called
Node p = front;
for(int i = 0; i< index; i++)
p = p.next;
return p.data;
So going to do 1 + 2 + 3 + 4 + ... + 10000 times.
hasNext() executes only once per call.

Java has a LinkedList class

15