graphs.ts

type GraphProp={[key:string]:string[]}

const buildGraph = (edges:string[][]):GraphProp=>{
    const result :GraphProp= {}
    for(const edge of edges){
        const [a,b]= edge
        if(!(a in result)) result[a]=[]
        if(!(b in result)) result[b]=[]
        result[a].push(b)
        result[b].push(a)
    }

    return result

}

const hasPath = (graph:GraphProp,source:string,destination:string,visited:Set<string>): boolean => {
    if(source === destination) return true;
    if(visited.has(source)) return false;
    
    
    visited.add(source)
    for(let child of graph[source]){
        if(hasPath(graph,child,destination,visited)){
            return true;
        }
    }
    return false;
}
const hasPathDfs = (edges:string[][],src:string,dest:string)=>{
    const graph =buildGraph(edges)
  
  

    return hasPath(graph,src,dest,new Set());

}
  

const graph=[
    ['i','j'],
    ['k','i'],
    ['m','k'],
    ['k','l'],
    ['o','n']
]
console.log(hasPathDfs(graph,'j','m'))

const countConnectedComponents=(graph:GraphProp)=>{
    let count = 0;

    const visited:Set<string> =new Set()
    for(const key in graph){
        if(visited.has(key)) continue
        count++
        markVisistedDfs(graph,key,visited) 
    }

    return count;
}

const markVisistedDfs=(graph:GraphProp,source:string,visited: Set<string>)=>{
        if(visited.has(source)) return
        const stack:string[] = [source] //bfs
        visited.add(source)
        while(stack.length>0){
            const current = stack.pop() as string;
            for(let neighbour of graph[current]){
                markVisistedDfs(graph,neighbour,visited)
            }
        }
}

const adj:GraphProp={
    '1': ['2'],
    '2':['1'],
    '3':[],
    '4':['6'],
    '6':['4','5','7','8'],
    '8':['6'],
    '7':['6'],
    '5':['6']
}
console.log(countConnectedComponents(adj))



const largestComponent=(graph:GraphProp)=>{
    let max = 0;

    const visited:Set<string> = new Set()
    for( let edge in graph ){
        if(visited.has(edge)) continue
        const count = countConnectedComponentsBfs(graph,edge,visited)
        if(count>max){
            max=count
        }
    }

    return max
}

const countConnectedComponentsBfs= (graph:GraphProp,start:string,visited:Set<string>)=>{
    if(visited.has(start)) return 0
    let count = 1;
    visited.add(start)
   
        for(let neigbour of graph[start]){
            count+=countConnectedComponentsBfs(graph,neigbour,visited)
        }
    

    return count
}
const components:GraphProp= {
    '0':['1','5','8'],
    '1':['0'],
    '5':['0','8'],
    '8':['0','5'],
    '2':['3','4'],
    '3':['2','4'],
    '4':['3','2']
}

console.log(largestComponent(components))




const shortestPathBfs=(graph:GraphProp,start:string,end:string)=>{
    const visited= new Set()
    const stack =[[start,0]]

    while(stack.length>0){
        const [current,distance] = stack.shift() as any;
        if(current==end) return distance
        if(visited.has(current)) continue
        visited.add(current)
        for(const neigbours of graph[current]){
            stack.push([neigbours,distance+1])
        }
    }
    return -1
}
const shortestPath = (edges:string[][],start:string,destination:string)=>{
    const graph =buildGraph(edges)
    return shortestPathBfs(graph,start,destination);

}



const graph=[
    ['w','x'],
    ['x','y'],
    ['z','y'],
    ['z','v'],
    ['w','v']
]
console.log(shortestPath(graph,'w','z'))



const explore=(graph:string[][],row:number,col:number,visited:Set<string>)=>{
    if(row<0 || col<0|| row>graph.length-1|| col>graph[row].length-1) return
     if( visited.has(`${row},${col}`))return
    visited.add(`${row},${col}`)
 
    if(graph[row][col]=='L'){
       explore(graph,row-1,col,visited)
       explore(graph,row+1,col,visited)
       explore(graph,row,col-1,visited)
       explore(graph,row,col+1,visited)
    }
}
const islandCount=(edges:string[][])=>{
    const visited :Set<string>= new Set()
    let count =0;
    for(let row =0;row<edges.length;row++){
        for(let column=0;column< edges[0].length;column++){
            if(!visited.has(`${row},${column}`) && edges[row][column]=='L' ){
                count++
                explore(edges,row,column,visited)
            }
        }
    }
    return count;
}

  
const grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
];

console.log(islandCount(grid)); // -> 3