> For the complete documentation index, see [llms.txt](https://algorithm.prettylog.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://algorithm.prettylog.com/overview/2.-data-structures/graph/detect-a-cycle-in-a-graph/dfs.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.