• G = (V, E), V represents vertices and E represents edges
• Adjacency list, sparse graph, for which |E| is much less than |V|²
• Adjacency matrix, dense graphs, for which |E| is close to |V|²

• O(V+E)
• Generate one BFS tree

/** Node in CLRS Ch22.2
 * @author Lin Chen
 * @since 11.09.2017
 */
public class Node
{
	private String id;//vertex id
	private int dist;//distance from source to current vertex
	private String color;//vertex color, WHITE, not visited; GRAY, pushed into queue; BLACK, popped up from queue
	private Node prev;//predecessor

	public Node(String i)
	{
		id = i;
		dist = -1;
		color = "WHITE";
		prev = null;
	}

	public String getID() {return id;}
	public int getDist() {return dist;}
	public String getColor() {return color;}
	public Node getPrev() {return prev;}

	public void setID(String i) {id = i;}
	public void setDist(int d) {dist = d;}
	public void setColor(String c) {color = c;}
	public void setPrev(Node n) {prev = n;}
}
			

/**
 * Graph descript in CLRS Chapter 22.2
 * @author Lin Chen
 * @since 11.09.2017
 */
import java.util.*;

public class Graph
{
	private int V;//number of vertices
	private LinkedList<LinkedList<Node>> adjList;
	private Node [] vertices;
	private HashMap<String, Integer> id2index;

	/** Initialize a graph with n node
	 * @param n number of vertices
	 */
	public Graph(String ... args)
	{
		V = args.length;

		//create adjacency list
		adjList = new LinkedList<LinkedList<Node>>();
		for(int i = 0; i < V; i++)
			adjList.add(new LinkedList<Node>());

		//create vertices
		vertices = new Node[V];
		id2index = new HashMap<String, Integer>();
		for(int i = 0; i < V; i++)
		{
			vertices[i] = new Node(args[i]);
			id2index.put(args[i], i);
		}
	}

	/** Breadth First Search
	 * @param s search from vertex s
	 */
	public void BFS(String s)
	{
		vertices[id2index.get(s)].setColor("GRAY");
		vertices[id2index.get(s)].setDist(0);
		vertices[id2index.get(s)].setPrev(null);
		Queue<Node> q = new LinkedList<Node>();
		q.add(vertices[id2index.get(s)]);

		while(!q.isEmpty())
		{
			Node u = q.poll();
			int uIndex = id2index.get(u.getID());
			System.out.println("Pop "+u.getID()+" and set color to be BLACK");
			for(Node e : adjList.get(uIndex))
			{
				int index = id2index.get(e.getID());
				if(vertices[index].getColor().equals("WHITE"))
				{
					System.out.println("Push "+e.getID()+" into queue and set color to be GRAY");
					vertices[index].setColor("GRAY");
					vertices[index].setDist(vertices[uIndex].getDist()+1);
					vertices[index].setPrev(vertices[uIndex]);
					q.add(e);
				}
			}
			vertices[uIndex].setColor("BLACK");
		}
	}

	/** Add edge (u, v) to the graph
	 * @param u start node
	 * @param v end node
	 */
	public void addEdge(String u, String v)
	{
		adjList.get(id2index.get(u)).add(vertices[id2index.get(v)]);
	}

	/** List adjacency list
	 * @return {@code String}, whole adjacency list
	 */
	public String adjList()
	{
		String s = "";
		for(int i = 0; i < vertices.length; i++)
		{
			s += vertices[i].getID()+" --> ";
			for(Node e : adjList.get(i))
				s += e.getID()+" --> ";
			s += "\n";
		}

		return s;
	}

	/** Display Graph
	 */
	public void display()
	{
		System.out.println("---------BFS Graph------------");
		for(int i = 0; i < vertices.length; i++)
		{
			System.out.printf("ID: %5s Dist: %5d Color: %10s", vertices[i].getID(), vertices[i].getDist(), vertices[i].getColor());
			if(vertices[i].getPrev() != null)
				System.out.printf("%5s\n", vertices[i].getPrev().getID());
			else
				System.out.println();
		}
	}
}
			

public class BFS
{
	public static void main(String args[])
	{
		Graph g = new Graph("1", "2", "3", "4", "5");
		g.addEdge("1", "2");
		g.addEdge("1", "5");
		g.addEdge("2", "3");
		g.addEdge("2", "4");
		g.addEdge("4", "3");
		g.addEdge("5", "2");
		g.addEdge("5", "4");

		System.out.println(g.adjList());

		g.BFS("1");

		g.display();
	}
}
			

• O(V+E)
• Generate multiple DFS trees

/** Node in CLRS Ch22.3
 * @author Lin Chen
 * @since 11.09.2017
 */
public class Node
{
	private String id;//vertex id
	private int d;//first timestamp
	private int f;//second teimstamp
	private String color;//vertex color, WHITE, not visited; GRAY, pushed into queue; BLACK, popped up from queue
	private Node prev;//predecessor

	public Node(String i)
	{
		id = i;
		d = -1;
		f = -1;
		color = "WHITE";
		prev = null;
	}

	public String getID() {return id;}
	public int getD() {return d;}
	public int getF() {return f;}
	public String getColor() {return color;}
	public Node getPrev() {return prev;}

	public void setID(String i) {id = i;}
	public void setD(int d) {this.d = d;}
	public void setF(int f) {this.f = f;}
	public void setColor(String c) {color = c;}
	public void setPrev(Node n) {prev = n;}

	public String toString()
	{
		return id+"("+d+","+f+")";
	}
}
			

public class TimeStamp
{
	private int t;

	public TimeStamp()
	{
		t = 0;
	}

	public int getTimeStamp() {return t;}

	public void setTimeStamp(int t) {this.t = t;}
}
			

/**
 * Graph descript in CLRS Chapter 22.3
 * @author Lin Chen
 * @since 11.09.2017
 */
import java.util.*;

public class Graph
{
	private int V;//number of vertices
	private LinkedList<LinkedList<Node>> adjList;
	private Node [] vertices;
	private HashMap<String, Integer> id2index;

	/** Initialize a graph with n node
	 * @param n number of vertices
	 */
	public Graph(String ... args)
	{
		V = args.length;

		//create adjacency list
		adjList = new LinkedList<LinkedList<Node>>();
		for(int i = 0; i < V; i++)
			adjList.add(new LinkedList<Node>());

		//create vertices
		vertices = new Node[V];
		id2index = new HashMap<String, Integer>();
		for(int i = 0; i < V; i++)
		{
			vertices[i] = new Node(args[i]);
			id2index.put(args[i], i);
		}
	}

	/** Depth First Search
	 * @param s search from vertex s
	 */
	public void DFS()
	{
		TimeStamp t = new TimeStamp();

		for(int i = 0; i < V; i++)
			if(vertices[i].getColor().equals("WHITE"))
			{
				DFSVisit(vertices[i], t);
			}
	}

	/** DFS visit node
	 * @param u start node
	 * @param t time stamp
	 */
	public void DFSVisit(Node u, TimeStamp t)
	{
		t.setTimeStamp(t.getTimeStamp()+1);
		u.setD(t.getTimeStamp());
		u.setColor("GRAY");
		for(Node v : adjList.get(id2index.get(u.getID())))
			if(v.getColor().equals("WHITE"))
			{
				v.setPrev(u);
				DFSVisit(v, t);
			}
		u.setColor("BLACK");
		t.setTimeStamp(t.getTimeStamp()+1);
		u.setF(t.getTimeStamp());
	}

	/** Add edge (u, v) to the graph
	 * @param u start node
	 * @param v end node
	 */
	public void addEdge(String u, String v)
	{
		adjList.get(id2index.get(u)).add(vertices[id2index.get(v)]);
	}

	/** List adjacency list
	 * @return {@code String}, whole adjacency list
	 */
	public String adjList()
	{
		String s = "";
		for(int i = 0; i < vertices.length; i++)
		{
			s += vertices[i].getID()+" --> ";
			for(Node e : adjList.get(i))
				s += e.getID()+" --> ";
			s += "\n";
		}

		return s;
	}

	/** Display Graph
	 */
	public void display()
	{
		System.out.println("---------DFS Graph------------");
		for(int i = 0; i < vertices.length; i++)
		{
			System.out.printf("ID: %5s D: %5d F: %5d, Color: %10s", vertices[i].getID(), vertices[i].getD(), vertices[i].getF(), vertices[i].getColor());
			if(vertices[i].getPrev() != null)
				System.out.printf("%5s\n", vertices[i].getPrev().getID());
			else
				System.out.println();
		}
	}
}
			

public class DFS
{
	public static void main(String args[])
	{
		Graph g = new Graph("1", "2", "3", "4", "5");
		g.addEdge("1", "2");
		g.addEdge("1", "5");
		g.addEdge("2", "3");
		g.addEdge("2", "4");
		g.addEdge("4", "3");
		g.addEdge("5", "2");
		g.addEdge("5", "4");

		System.out.println(g.adjList());

		g.DFS();

		g.display();
	}
}
			

• Tree edges, edges in the DFS forest
• Back edges, edges (u, v), in which u connect to an ancester v in a DFS tree
• Forward edges, nontree edges (u, v) connecting a vertex u to a descendant v in a DFS tree
• Cross edges, other edges, (u, v) can be in the same DFS tree or in different DFS tree

• First time explore an edge (u, v), the color of v tells the edges
  • WHITE, tree edge
  • GRAY, back edge
  • BLACK, forward or cross edges
    • forward edge, u.d < v.d
    • cross edge, u.d > v.d

• A directed graph has a cycle if and only if its DFS reveals a back edge
• Topological sort, convert a directed acyclic graph to a linear dag
• Call DFS
• As each vertex is finished, insert it onto the front of a linked list

• Two nodes u and v of a directed graph are connected if there is a path from u to v and a path from v to u
• A strongly connected component of a directed graph is a maximal set of vertices such that every pair of u and v are connected