Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
I think it is not possible to put visit situation in a graph node. A graph node is pure graph node.Step 3 maybe need modification.
It's random psuedo/english based code.
I don't know what your talking about either :P
Please explain.
Trees do not have parent nodes.
You are speaking of any possible "root" node (special node designated as root).
Well the question says the edges are undirected, so a "child" can reach its parent node, so any node can reach the root node (it is sort of like having parent pointers in the rooted binary tree you are imagining).
G is the overall graph object instatiated from a class/struct "Graph" .. wrapping everything up.
It represents whole graph.
//for e.g. (some parts of setup, minimalistic- no member functions)
#define MAX_VERTICES 100000
struct Graph {
int numVertices; // number of actual vertices
struct Vertex {
bool visited;
//other stuff (maybe adj list , edges, etc.)
//some data
} vertices[MAX_VERTICES]; //or make it dynamic array
//some more stuff
};
bool isTree(Graph *G)
{
if(G->numVertices == 0) return true; /* empty tree ? :) */
/* Step 1: pick a random vertex and reset visit flags somehow */
int v = //PICK RANDOM INDEX NUMBER from 0 to G->numVertices-1
// for(int i=0; i < G->numVertices i++) G->vertices[i].visited = false;
Stack <int> S;
/* DFS to check for cycles - f you meet a visited node ==> cycle found */
S.push(v); //v is random start node we picked earlier
while( !S.empty ) {
v = S.pop();
if( G->vertices[v].visited )
return false; //cycle found (not a tree)
G->vertices[v].visited = true;
for( all edges (v, u) from vertex v)
S.push(u);
}
/* Step 3: If any vertices are unvisited, graph is disconnected == not a true */
for(int i=0; i < G->numVertices i++)
if( ! G->vertices[i].visited )
return false;
return true; //passed both tests, so it is a tree
}
your approach is fine but your code is wrong as it will only work for directed graphs but not for general graphs, as you can encounter already visited node.
Ex:
1 -- 2 -- 3 -- 5
Now, after visiting 1 when you switch to node 2, it will check its adjacent nodes which are 1 and 3. As 1 is already marked as visited your function would return false but there is no cycle in example. you need to add one more condition as
while( !S.empty ) {
v = S.pop();
if( G->vertices[v].visited && v != parent)
return false; //cycle found (not a tree)
G->vertices[v].visited = true;
parent = v;
for( all edges (v, u) from vertex v)
S.push(u);
}
Followed the same approach and tested the code, it works
public class Graph {
public static void main(String[] args){
int[] vertices={1,2,3,4,5,6};
boolean[] visited={false,false,false,false,false,false,false};
Map<Integer,Integer[]> adjacent=new HashMap<Integer, Integer[]>();
adjacent.put(1,new Integer[]{2,3});
adjacent.put(2,new Integer[]{4,5});
adjacent.put(3,new Integer[]{});
adjacent.put(4,new Integer[]{});
adjacent.put(5,new Integer[]{});
adjacent.put(6,new Integer[]{1});
Stack<Integer> stack=new Stack<Integer>();
boolean flag=false;
stack.push(1);
visited[1]=true;
while(!stack.empty()){
Integer v=stack.pop();
if(adjacent.get(v).length!=0){
for(Integer i:adjacent.get(v)){
if(visited[i]==true){
System.out.print("cycle detected");
flag=true;
break;
}
visited[i]=true;
stack.push(i);
}
}
}
for(int i=1;i<visited.length;i++){
if(!visited[i])
{
System.out.print("break detected");
flag=true;
}
}
if(!flag)
System.out.print("graph is a tree");
}
}
This is for a directed graph:
public static void main(String[] args) {
int[] vertices = {1,2,3,4,5};
HashMap<Integer, int[]> adjList = new HashMap<>();
adjList.put(1, new int[]{2});
adjList.put(2, new int[]{3,4});
adjList.put(4, new int[]{5});
System.out.println("Is tree: " + (isTree(vertices, adjList)?"yes":"no"));
}
private static boolean isTree(int[] vertices, HashMap<Integer, int[]> adjList) {
HashMap<Integer, Boolean> visited = new HashMap<>();
Stack<Integer> stack = new Stack<>();
stack.push(vertices[0]);
while (!stack.isEmpty()) {
int node = stack.pop();
visited.put(node, true);
int[] adjNodes = adjList.get(node);
if (adjNodes != null) {
for (int n : adjNodes) {
if (visited.containsKey(n)) {
return false;
}
stack.push(n);
}
}
}
for (int n : vertices) {
if (!visited.containsKey(n))
return false;
}
return true;
}
If Graph is connected then use following:
Directed Graph: Count the number of edges if it is equal to (Number of nodes - 1) then it's a tree.
Undirected Graph: Count the number of edges if it is equal to (Number of nodes - 1)/2 then it's a tree.
Otherwise use BFS or DFS to make sure the graph is connected and has no loops.
thoughts... or counter example?
It is a tree IFF if both
1) it is connected
2) has no cycles
So use DFS from any node s:
[Assuming below that vertices are integer labelled from 0 to ... N-1. ]
- S O U N D W A V E February 27, 2014bool isTree(Graph *G) { if(G->numVertices == 0) return true; /* empty tree ? :) */ /* Step 1: pick a random vertex and reset visit flags somehow */ // int v = PICK RANDOM INDEX NUMBER from 0 to G->numVertices-1 // for(int i=0; i < G->numVertices i++) G-vertices[i].visited = false; Stack <int> S; /* DFS to check for cycles - that is, if you meet a visited node ==> cycle found */ S.push(start); while( !S.empty ) { v = S.pop(); if( G->vertices[v].visited ) return false; //cycle found (not a tree) G->vertices[v].visited = true; for( all edges (v, u) from vertex v) S.push(u); } /* Step 3: If any vertices are unvisited, graph is disconnected == not a true */ for(int i=0; i < G->numVertices i++) if( ! G-vertices[i].visited ) return false; return true; //passed both tests, so it is a tree }