# DFS \*

## Undirected Graph

{% embed url="<https://www.geeksforgeeks.org/detect-cycle-undirected-graph/>" %}
Explanation
{% endembed %}

{% embed url="<https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1>" %}
Problem
{% endembed %}

> from: use this when graph is undirected, can omit when graph is directed

> Time: O(V + E): iter V and then iter E, connected to the V
>
> Space: O(V), V is the number of vertices

<figure><img src="/files/8zU0txPlTtdys4xysaWI" alt="" width="188"><figcaption></figcaption></figure>

```javascript

// if vertex 0 and 1 are connected then, graph = [ [1], [0] ]

const graph = [
    [1, 4],
    [0, 4, 2, 3],
    [1, 3],
    [1, 4, 2],
    [3, 0, 1]
]; // cycle

const graph = [
    [1, 2],
    [0],
    [0],
]; // no cycle

const State = {
  'WHITE': 0, // not visisted
  'GRAY': 1, // current checking
  'BLACK': 2 // visited
}

function dfsAll(adjs) {
    // console.log(adjs);
    const vertexNum = adjs.length;
    const visited = new Array(vertexNum).fill(State.WHITE);
    
    let componentCnt = 0;
    for (let vertex = 0; vertex < adjs.length; vertex++) {
        if (visited[vertex] !== State.WHITE) continue;

        componentCnt += 1; // check component count
        console.log(`:: vertex ${vertex} is traversing, :: components = ${componentCnt}`);
         
        const flag = dfs(adjs, visited, vertex, vertex);
        
        console.log(`vertex ${vertex} form a cycle? ${flag}`)
        
        if (flag === true) {
            console.log('cycle detected!');
            return true;
        }
    }
    
    return false;
}

function dfs(adjs, visited, here, parent) {
    visited[here] = State.BLACK; // 방문 순간 양방향 소통이 일어나 black
    
    const adj = adjs[here];
    for (const str of adj) {
        const there = Number(str);
        
        // if (visited[there] === State.WHITE) {
        //   const flag = dfs(adjs, visited, there, here);
        //     if (flag === true) 
        //         return true;
        // } else if (parent !== there) {
        //     return true;
        // }
        
        if (parent === there) continue;
        if (visited[there] === State.GRAY) return true; // different        
        if (visited[there] === State.BLACK) return true;
        
        const flag = dfs(adjs, visited, there, here);
        if (flag === true)
            return true;
    }
    visited[here] = BLACK;
    return false;
}

dfsAll(graph);
```

<mark style="color:blue;">Undirected graph는 정점간 연결되면 -> <- 양 방향이기 때문에 black 방문 시 gray 방문과 같으 효과르르 갖는다.</mark>

## Directed Graph

{% embed url="<https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/>" %}

```javascript
function cycleInGraph(edges) {
  
  return detectCycle(edges);
}

const State = {
  'WHITE': 0, // not visisted
  'GRAY': 1, // current checking
  'BLACK': 2 // visited
}

function dfs(adjs, visited, here) {
  visited[here] = State.GRAY;

  const adj = adjs[here];
  for (const str of adj) {
    const there = Number(str);
    
    if (visited[there] === State.Black) 
      continue; // black continue; 일방향이기 때문에 => 양 방향이면 black이면 현재로 넘어온 기억이 있다.
    if (visited[there] === State.GRAY) 
      return true; // gray 현재 싸이클에서 돌고 있을 때만

    const flag = dfs(adjs, visited, there);
    if (flag === true) return true;
  }

  visited[here] = State.BLACK;
  return false;
}

function detectCycle(adjs) {
  const visited = new Array(adjs.length).fill(State.WHITE);

  for (let vertex = 0; vertex < adjs.length; vertex++) {
    const canVisit = visited[vertex] === State.WHITE;
    if (!canVisit) continue;
    
    const flag = dfs(adjs, visited, vertex);
    if (flag === true) 
      return true;
  }

  return false;
}

```

directed graph는 한 방향 이기 때문에 <mark style="color:blue;">balck을 방문해도 괜찮다</mark>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://algorithm.prettylog.com/overview/2.-data-structures/graph/detect-a-cycle-in-a-graph/dfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.