Expand|Select|Wrap|Line Numbers
- dfs(v)
- { create a stack s to store visited notes
- s.push(v)
- while(!s.isEmpty())
- {
- if(no unvisited vertices are adjacent to the vertex on stack top)
- {
- //need a method to peep at the top element
- s.pop() //backtrack
- }
- else
- {
- select an unvisited vertex u adjacent to the vertex on stack top
- s.push(u);
- mark u as visited
- }
- }
- }
Expand|Select|Wrap|Line Numbers
- public class Graph {
- int arraySize, graphSize;
- ListNode node[];
- boolean[] visited= new boolean[arraySize];
- public Graph() { // constructor
- arraySize = 10;
- graphSize = 0;
- node = new ListNode[arraySize];
- for (int j=0; j<arraySize; j++) node[j] = null;
- }
- public Graph(int size) { // constructor
- arraySize = size;
- graphSize = 0;
- node = new ListNode[arraySize];
- for (int j=0; j<arraySize; j++) node[j] = null;
- }
- public boolean isEmpty() {
- return graphSize == 0;
- }
- public boolean isFull() {
- return graphSize == arraySize;
- }
- public int getArraySize() {
- return arraySize;
- }
- public int getGraphSize() {
- return graphSize;
- }
- public boolean insertNode(NodeRecord r) {
- int j;
- if (isFull()) return false;
- for (j=0; j<arraySize; j++)
- if (node[j]==null)
- break;
- node[j] = new ListNode(r);
- graphSize++;
- return true;
- }
- //dfs method
- public boolean insertEdge(int nodeID, EdgeRecord e) {
- int j;
- for (j=0; j<arraySize; j++)
- if (nodeID==((NodeRecord) node[j].getItem()).getID())
- break;
- if (j>=arraySize) return false;
- node[j].setNext(new ListNode(e, node[j].getNext()));
- return true;
- }
- public void print() {
- int j;
- ListNode link;
- System.out.println(graphSize + " nodes read");
- for (j=0; j<graphSize; j++) {
- System.out.print(node[j].getItem()+"-> ");
- link = node[j].getNext();
- while (link!=null) {
- System.out.print(link.getItem());
- link = link.getNext();
- }
- System.out.println();
- }
- }
- }
Expand|Select|Wrap|Line Numbers
- public class Record implements Comparable {
- protected int ID;
- protected String name;
- public Record(int newID) {
- ID = newID;
- name = "";
- }
- public Record(int newID, String newName) {
- ID = newID;
- name = newName;
- }
- //set and get methods
- public int compareTo(Object o) {
- if (!(o instanceof Record) throw new IllegalArgumentException("Error: non-Record type object!");
- Record c = (Record) o;
- if (ID > c.ID) return 1;
- if (ID < c.ID) return -1;
- return 0;
- }
- public String toString() { // add to class Circle
- return getID()+" ";
- }
- }
Expand|Select|Wrap|Line Numbers
- public class NodeRecord extends Record {
- public NodeRecord(int newID) {
- super(newID);
- }
- public NodeRecord(int newID, String otherInfo) {
- super(newID, otherInfo);
- }
- public int compareTo(Object o) {
- if (!(o instanceof NodeRecord)) throw new IllegalArgumentException("Error: non-NodeRecord type object!");
- NodeRecord c = (NodeRecord) o;
- if (ID > c.ID) return 1;
- if (ID < c.ID) return -1;
- return 0;
- }
- }
Expand|Select|Wrap|Line Numbers
- public class EdgeRecord extends Record {
- public EdgeRecord(int newconnectedTo) {
- super(newconnectedTo);
- }
- public EdgeRecord(int newConnectedTo, String newOtherInfo) {
- super(newConnectedTo, newOtherInfo);
- }
- public int getConnectedTo() {
- return ID;
- }
- public String getOtherInfo() {
- return name;
- }
- public EdgeRecord setConnectedTo(int newconnectedTo) {
- ID = newconnectedTo;
- return this;
- }
- public EdgeRecord setotherInfo(String newOtherInfo) {
- name = newOtherInfo;
- return this;
- }
- public int compareTo(Object o) {
- if (!(o instanceof EdgeRecord)) throw new IllegalArgumentException("Error: non-EdgeRecord type object!");
- EdgeRecord c = (EdgeRecord) o;
- if (ID > c.ID) return 1;
- if (ID < c.ID) return -1;
- return 0;
- }
- }
Expand|Select|Wrap|Line Numbers
- public class Stack extends List {
- public Stack() {
- super();
- }
- public boolean push(Object newItem) {
- return insert(1, newItem);
- }
- public Object pop() {
- return remove(1);
- }
- public Object peek(){
- return super.getItem(super.size());
- }
- }