Undirected Graph

Appendix

• Graph Glossary

• Graph API

• Search and Path
• Depth-First-Search
• Breath-first search
• Connected Component

• Bipartite graph

Graph Glossary

Term Definition
Graph A graph is a set of vertices and a collection of edges that each connect a pair of vertices.
simple Graph A graph with no self-loop and no parallel edges
Path Path in a graph is a sequence of vertices connected by edges, the length of Path is number of edges
Cycle A cycle is a path with at least one edge whose first and last vertices are the same
Connected Graph A graph is connected if there is a path from every vertex to every other vertex in the graph.
Acyclic Graph An acyclic graph is a graph with no cycles
bipartite Graph a bipartite Graph is a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.

Graph API

There are three way to represent Graph

• Adjacency list: best solution: seems like separating chaining in hashing.

• Adjacency matrix: sparse graph cause inefficient memory usage

• edge list: adj() will traversal through all edges, cost too much time.

Basic Graph API

``````public class graph{
private final int V;
private int E;
//constructor

public graph(int V){
this.V = V;
this.E = 0;

for(int i = 0; i < V; i++){
}
}

//return number of vertices
public int V() {
return V;
}

// return number of edges
public int E() {
return E;
}

//add edges between v and w
public void addedge(int v, int w){
E++;
}

//return a Iterable object contain vertices that linked to v
}

//print graph
public String toString() {
String s = V + "vertices" + E + "edges\n";
for(int v = 0; v<V; s++){
s += v + ":";
s += w + "";
}
return s;
}
}
}

``````

Extended graph API

``````
/* The following function eliminates the main function, only show support function*/

public int degree(Graph G, int v){
int degree;
degree ++;
}
return degree;
}

public int maxDegree(Graph G, int v){
int max = 0;
for(int v = 0; v < G.V(); v++){
if(degree(G,v) > max){
max = degree(G,v);
}
}
return max;
}

public int hasLoops(Graph G){
for(int v = 0; v < G.V(); v++){
if(v == w) return true;
}
}
return false;
}
``````

Find a path from v to w in a graph, record each vertices in the path.

DFS

process the vertices until it has no vertex connected to

``````public class DFS {
private boolean[] marked;
private int[] edgeTo;
private final int s;

public DFS(Graph G, int s){
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G,s);
}

private void dfs(Graph G, int s){
marked[s] = true;
if(!marked[w]){
edgeTo[v] = w;
dfs(G,w);
}
}
}

public Iterable<Integer> pathTo(int v){
Stack<Integer> path = new Stack<Integer>();
for(int x = v; x!= s; x = edgeTo[x]){
path.push(x);
}
path.push(s);
}
}

``````

BFS

Process all the branch first then go deep, this method always return the shortest path from source

``````public class BFS{
private boolean[] marked;
private int[] edgeTo;
private final int s;

marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G, s);
}

public void bfs(Graph G, int s){
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
queue.enqueue(s);
while(!queue.isempty()){
int v = queue.dequeue();
if (!marked[w])
{
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}
}

public Iterable<Integer> pathTo(int v){
Stack<Integer> path = new Stack<Integer>();
for(int x = v; x!= s; x = edgeTo[x]){
path.push(x);
}
path.push(s);
}

}
``````

Connected Component.

This class is used for detect how many components in a graph

``````public class CC{
private boolean[] marked;
private int[] id;
private int count; //return how many component does the graph have

public CC(Graph G){
marked = new boolean[G.V()];
id = new int [G. V()];
//in order to record which components does each vertex belong to

for(int s = 0; s < G.V(); s++){
// if the graph is connected, if statement should be only execute once
if(!marked[s]){
dfs(G, s);
count ++;
}
}
}

private void dfs(Graph G, int v){
marked[v] = true;
id[v] = count;
if (!marked[w]) {
dfs(G, w);
}
}
}

public boolean connected(int v, int w)
{  return id[v] == id[w];  }

public int id(int v)
{  return id[v];  }

public int count()
{  return count;  }
}
``````

Bipartite Graph

vertices who have same color canâ€™t be connected together

``````public class Bipartite{
private boolean[] marked;
private boolean[] color;
private boolean isbipartite = true;

public Bipartite(Graph G){
marked = new boolean[G.V()];
color = new boolean[G.V()];

for(int s = 0; s < G.V(); s++){
// in order to cover all components
if(!marked[s]){
dfs(G, s);
}
}
}

private void dfs(Graph G, int v){
marked[v] = true;