Module 4 (Graph Traversal) - Algoritma-dan-Pemrograman-ITS/StrukturData GitHub Wiki

Traversal Graph

Depth First Search (DFS)

As the name implies, DFS will traversal to the deepest vertex. Every time you arrive at a vertex $u$, DFS will select one of the vertex associated(neighbouring) with vertex $u$ that had never been visited before, then continue searching from that vertex. This step continues as long as we still find vertex that can still be visited. If it doesn't exist, it will do backtracking then return to look for vertex that can be visited.

An example of implementing in a weighted graph can be done iteratively like the following code:

void dfs(vector<long> &result, long start){
    vector<bool> visited(vertexCount, false);
    stack<long> st;

    st.push(start);
    visited[start] = true;
    result.push_back(start);

    while(!st.empty()){
        long temp = st.top();
        st.pop();

        if(!visited[temp]){
            result.push_back(temp);
            visited[temp] = true;
        }

        for(auto vertex:adjList[temp]){
            if (!visited[vertex])
                st.push(vertex);
        }
    }
}

DFS Pseudocode

DFS Pseudocode

DFS Ilustration

DFS Ilustration

Source: https://skilled.dev/course/depth-first-search

Breadth First Search (BFS)

Traversal using BFS starts from a vertex, then will visit the vertex which is directly connected (neighbouring) to the vertex (layer 1). Then, in the next step we will visit vertex which is directly connected to vertex - vertex on layer 1 (layer 2) and so on until there is no more vertex that can be visited.

This is an iterative BFS implementation:

void bfs(vector<long> &result, long start){
    vector<bool> visited(vertexCount, false);
    queue<long> q;

    q.push(start);
    visited[start] = true;
    result.push_back(start);

    while(!q.empty()){
        long temp = q.front();
        q.pop();

        for(auto vertex:adjList[temp]){
            if (!visited[vertex]){
                q.push(vertex);
                visited[vertex] = true;
                result.push_back(vertex);
            }
        }
    }
}

BFS Pseudocode

BFS Pseudocode

BFS Ilustration

BFS Ilustration

Source: https://skilled.dev/course/breadth-first-search

Trivia question: in DFS, we tag the nodes before iterating over the contents of the adjacency list, whereas in BFS, we tag them in iterations. Does the timing of the placement of these marks affect the algorithms? If so, what effect would it have?

Graph

If we do BFS on the graph from vertex 1, the vertices for each layer are:

  • Layer 0: 1
  • Layer 1: 2 5
  • Layer 2: 3 4
  • Layer 3: 6

Note that the number of layers is the number of minimal edges that must be passed to get to the vertex from vertex 1 or so-called shortest path.

⚠️ **GitHub.com Fallback** ⚠️