# Graph

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A graph is a set of objects called points, nodes, or vertices connected by links called lines or edges. In a proper graph, which is by default undirected, a line from point A to point B is considered to be the same thing as a line from point B to point A. In a digraph, short for directed graph, the two directions are counted as being distinct arcs or directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges)

## Code Packet

Modeling problems as graphs is essential for contest problems. The implementation of a graph, and some graph algorithms appear below:

NOTE: This class requires a List implementation, which also appears in the code packet.

```import java.util.*;

class Graph{
/** Core Stuff **/
public Vertex[] verts;

public Graph(int order){
verts=new Vertex[order];

for(int i=0;i<order;i++){
verts[i]=new Vertex();
verts[i].ID=i;
}
}

}

}

public void removeEdge(Vertex i,Vertex j){
}

/** Optional Stuff **/

public Vertex getFirst(){
return verts[0];
}

public boolean isConnected(){
return verts.length==countNodes(getFirst());
}

private int countNodes(Vertex v){
if(v.visited)
return 0;

v.visited=true;

int num=1;

for(Vertex x:v){
num+=countNodes(x);
}

return num;
}
}

class Vertex implements Iterable<Vertex>{
public boolean visited=false;
public int ID;

public Vertex(){
}

public int degree(){
}

public Iterator<Vertex> iterator(){
}

}

class List implements Iterable<Vertex>{

class Node{
Vertex el;
Node next;
}

class Iter implements Iterator<Vertex>{
Node ptr;

public boolean hasNext(){
return ptr.next!=null;
}
public Vertex next(){
ptr=ptr.next;return ptr.el;
}
public void remove(){}
}

int size;

public List(){
size=0;
}

for(Vertex x:this)
if(v.equals(x))
return false;
Node n=new Node();
n.el=v;
++size;
return true;
}

public boolean remove(Vertex v){
if(n.next.el.equals(v)){
n.next=n.next.next;
--size;
return true;
}
return false;
}

public Iter iterator(){
Iter i=new Iter();