Algorithms Cheat Sheet : Graph Search
Note : Below mentioned source code is taken from the book “Algorithm 4th Edition” by Robert Sedgewick. These code snippets are for personal reference. For more details on these topics you can either buy the book or refer the following site : http://algs4.cs.princeton.edu/home/
Topics Covered
- Graph data type
- Depth First Search
- Breadth First Search
- Symbol Graph
- Cycle Detection
- Two Colourable
public interface IGraph
{
int NumberOfVertices{get;set;}
int NumberOfEdges {get;set;}
void AddEdge(int s, int v);
IEnumerable<int> AdjacentVertices(int v);
}
public class Graph : IGraph
{
List<int>[] adjList; // adjacenecy list
// other methods & constructor
}
public class DepthFirstSearch
{
private bool[] marked; // node visited or not
private int[] edgeTo; // last vertex on known path to this vertex
public void DFS(Graph g, int s)
{
marked[s] = true;
foreach(int v in g.AdjacentVertices(s)){
if(!marked[v]){
edgeTo[v] = s;
DFS(g, v);
}
}
}
}
public class BreadthFirstSearch
{
private bool[] marked; // node visited or not
private int[] edgeTo; // last vertex on known path to this vertex
public void BFS(Graph g, int s)
{
Queue<int> q = new Queue<int>();
marked[s] = true;
q.Enqueue(q);
while(q.Count != 0)
{
int v = q.Dequeue();
foreach(var v in g.AdjacentVertices(s))
{
if(!marked[v]){
edgeTo[v] = s;
marked[v] = true;
q.Enqueue(v);
}
}
}
}
}
public class SymbolGraph
{
private Dictionary<string, int> dictionary; // <london,0>
private string[] invertedIndex; // 0 -> london
public SymbolGraph(string filePath){
dictionary = new Dictionary<string,int>();
foreach(var line in File.ReadLines(filePath))
{
string[] words = line.Split(' '); //delimiter
foreach(var word in words)
{
if(!dictionary.ContainsKey(word))
{
dictionary.Add(word, dictionary.Count);//<london,0>
}
}
}
invertedIndex = new string[dictionary.Count];
foreach(var item in dictionary)
{
invertedIndex[item.Value] = item.Key;//0 -> london
}
Graph g = new Graph();
foreach(var line in File.ReadLines(filePath))
{
string[] words = line.Split(' '); //delimiter
int source = dictionary[words[0]];
for(int i = 1; i < words.Length; i++)
{
g.AddEdge(source, dictionary[words[i]]);
}
}
}
}
public class Cycle
{
private bool[] marked; // node visited or not
private bool hasCycle;
///g -> graph
///s -> source vertex
///u -> source vertex(for cycle detection)
public void DFS(Graph g, int s, int u)
{
marked[s] = true;
foreach(int v in g.AdjacentVertices(s)){
if(!marked[v]){
DFS(g, v, u);
}
else if(v == u) hasCycle = true;
}
}
public bool HasCycle
{
get{return hasCycle;}
set{hasCycle = value;}
}
}
public class TwoColor
{
private bool[] marked;
private bool[] color;
private bool twoColorable = true;
public void DFS(Graph g, int s)
{
marked[s] = true;
foreach(int v in g.AdjacentVertices(s)){
if(!marked[v]){
color[v] = !color[s];
DFS(g, v, u);
}
else if(color[v] == color[s]) twoColorable = false;
}
}
public bool HasCycle
{
get{return twoColorable;}
set{twoColorable = value;}
}
}