# Graph

### From Progteam

This page discusses the subject of graphs. For a list of problems related to graphs, see Category:Graph.

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 addEdge(Vertex i,Vertex j){ i.adj.add(j); j.adj.add(i); } public void addEdge(int i,int j){ addEdge(verts[i],verts[j]); } public void removeEdge(Vertex i,Vertex j){ i.adj.remove(j); j.adj.remove(i); } /** 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 List adj; public int ID; public Vertex(){ adj=new List(); } public int degree(){ return adj.size; } public Iterator<Vertex> iterator(){ return adj.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(){} } Node header; int size; public List(){ header=new Node(); header.next=null; size=0; } public boolean add(Vertex v){ for(Vertex x:this) if(v.equals(x)) return false; Node n=new Node(); n.el=v; n.next=header.next; header.next=n; ++size; return true; } public boolean remove(Vertex v){ for(Node n=header;n.next!=null;n=n.next) if(n.next.el.equals(v)){ n.next=n.next.next; --size; return true; } return false; } public Iter iterator(){ Iter i=new Iter(); i.ptr=header; return i; } }