Design an algorithm which can automatically indicate whether

Design an algorithm which can automatically indicate whether or not a graph G contain a cycle (write your pseudo-code). Using the following two graphs as two examples to indicate what data structure to represent (i) and (ii), respectively. Explain how to determine whether or not an undirected graph is connected? And whether or not it is a tree? Using the following graph as an example to justify your answer.

Solution

(a)
   define visit(node n):
      if n.colour == grey: //if we\'re still visiting this node or its descendants
        throw exception(\"Cycle found\")

      n.colour = grey //to indicate this node is being visited
      for node child in n.children():
        if child.colour == white: //if the child is unexplored
          visit(child)

      n.colour = black //to show we\'re done visiting this node
      return

      Both (i) and (ii) can be done using Doubly linked list data structure
           keeping each connected node to each of each node as head.
           like in case of (i)
               x1 -> y1,y2
               x2 -> y1,y2
               x3 -> y1,y3

(b)
   DFS is an algorithm to traverse a graph, meaning it goes to all the nodes in the same connected component as the starting node. If we traverse the graph from a starting node and we find out that other nodes, after the traversal ends, have not been visited, this means that the graph is not connected.
   pseudocode :
   void dfs(int v){ //You can run DFS on any arbitrary node
                        if vis[v] is true: //don\'t visit the same node twice
                            return
                        set vis[v] as true
                        for all neighbors u of v: //DFS to all the neighbors
                            if vis[u] is false: //check if you visited it before
                                dfs(u)
   }


   bool connected(){ //Run DFS first
        for all nodes u:
            if vis[u] is false: //DFS did not reach this node
                return false
        return true
   }

   An undirected graph is tree if it has following properties.
   1) There is no cycle.
   2) The graph is connected.

   So, in the example we can see that the graph is not connected. since after traveral nodes are left unvisited.
       here for example if the traversal starts from A, B, C, E, F or I then D, H and G are not visited.
       Similarly if the traversal starts from D, H or G then A, B, C, E, F and I are not visited.

   and since it is graph is not connected, the graph is not a tree. (as given in the second condition of the graph to be tree)