Graphs

Question 1

How to represent a Graph?

Answer 1

Pointer/object notation
Adjacency list
Adjacency Matrix

Question 2

Pros/Cons of Adjacency List

Answer 2

Pros:
Only covers active Nodes and edges. 
Space efficient: O(|V| +|E|)
Cons: 
Slower time complexity than matrix
If it is a sparse graph, use adjacency list.

Question 3

Pros/Cons Adjacency Matrix

Answer 3

Pros:
Faster access time. O(1)
Cons:
Space complexity: )(|V|^2)
Represent non present edges.
If it is a strongly connected graph, Adjacency matrix is beneficial for access.

Question 4

What is DFS?

Answer 4

Depth first search recursively goes through graph. It goes to the first child and iterates until reaches the end of a path, then returns to original parent node and goes to the other children.

Question 5

What is BFS?

Answer 5

Breadth first search, looks at all adjacent nodes first. Uses a queue to iteratively perform search.

Question 6

Pros/Cons BFS?

Answer 6

Pros:
1. Solution will definitely found out by BFS If there are some solution.
2. BFS will never get trapped in blind alley , means unwanted nodes.
3. If there are more than one solution then it will find solution with minimal steps.
Cons:
1. Memory Constraints As it stores all the nodes of present level to go for next level.
2. If solution is far away then it consumes time.
Application:
1.Finding Shortest Path.
2.Checking graph with bipertiteness.
3.Copying cheiney’s Algorithm.

Question 7

Pros/Cons DFS

Answer 7

Pros:
1. Memory requirement is Linear WRT Nodes.
2. Less time and space complexity rather than BFS.
3. Solution can be found out by without much more search.
Cons:
1. Not Guaranteed that it will give you solution.
2. Cut-off depth is smaller so time complexity is more.
3. Determination of depth until the search has proceeds.
Application:
1. Finding Connected components.
2. Topological sorting.
3. Finding Bridges of graph.

Question 8

What is a Graph Node?

Answer 8

import java.util.ArrayList;

class GraphNode 
{
	public String name;
	public boolean visited=false;
	public int value;
	public ArrayList children;
	GraphNode(String name)
	{
	this.name = name;
	value = 0;
	this.children = new ArrayList();
	}
	GraphNode (String name, int value )
	{
		this.name = name;
		this.value = value;
		this.children = new ArrayList();
	}
	GraphNode(String name, ArrayList children)
	{
	this.name = name;
	this.children = new ArrayList();
	this.children.addAll(children);
	}

	void addChild(GraphNode node) 
	{
		if (children == null)
		{
			children = new ArrayList();
		}
		children.add(node);
	}

	void listEdges() 
	{
		if (children == null)
		{
			System.out.println("No Children");
			return;
		}
		for (GraphNode g : children)
			System.out.println(g.name);
	}

}

Question 9

How to search a graph DFS iteratively?

Answer 9

boolean DFSearchIter(String name)
	{

		if (Nodes.size() == 0) return false;
		Stack s = new Stack();
		s.add(Nodes.get(0));
		if (Nodes.get(0).name == name) return true;
		while (!s.isEmpty())
		{
			GraphNode tmp = s.pop();
			tmp.visited = true;

		for(int i = 0; i < tmp.children.size();i++) 
		{
			if ( tmp.children.get(i).name == name) return true;
			if (tmp.children.get(i).visited != true)
			{
				s.add(tmp.children.get(i));
			}
		}

	}
	return false;
}

Question 10

DFSearch recursively

Answer 10

boolean DFSearchCall(String name)
	{
		if (Nodes.size() == 0 ) return false;
		boolean isThere = DFSearchRec(Nodes.get(0), name );
		return isThere;
	}
	// Recursive DFS on adj list
	private boolean DFSearchRec(GraphNode node, String name)
	{
		boolean isThere = false;
		if (node.name == name ) return true;
		node.visited = true;

		for(GraphNode g : node.children)
		{
			if (!g.visited)
			{
				isThere = DFSearchRec(g,name);
			}
		}
		return isThere;

}

Question 11

BFSearch

Answer 11

boolean BFSearch(String name)
	{
		Queue q = new LinkedList();
		q.add(Nodes.get(0));
		if (Nodes.get(0).name == name) return true;
		while(!q.isEmpty())
		{
			GraphNode tmp = q.remove();
			tmp.visited = true;
			for (int i = 0; i

Question 12

What are the members of Graph class?

Answer 12

public ArrayList Nodes;

public int[][] matrix = null;