## 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;}`
`    }`
`}`
Published Saturday, February 02, 2013 2:10 PM by Pawan_Mishra
Filed under: , , , ,

### Comments

#### # re: Algorithms Cheat Sheet : Graph Search

Wednesday, February 20, 2013 9:45 AM by louis vuitton handbags

I'm typically to blogging and i actually admire your content. The article has actually peaks my interest. I am going to bookmark your website and maintain checking for new information. louis vuitton handbags www.louisvuitt0noutlets.com

(required)
(required)
(optional)
(required)