for Robot Artificial Inteligence

34. Graphs

24 Jun 2020 | Algorithm

Introduction(Representation of Graph)

  • Graph
    • Vertex와 edge를 이용하여서 최소의 경로의 값을 구하거나 특정 데이터를 찾는데 쓰인다.

Breadth First Search(BFS)

  • using queue data structure and hash table.

#include <iostream>
#include <queue>

using namespace std;

void BFS(int vtx, int A[][8], int n){
    queue<int> Q;
    int visited[8] {0};

    // Initial
    cout << vtx << ", " << flush;  // Visit vertex
    visited[vtx] = 1;
    Q.emplace(vtx);

    // Explore
    while (!Q.empty()){
        int u = Q.front();  // Vertex u for exploring
        Q.pop();
        for (int v=1; v<=n; v++){  // Adjacent vertices of vertex u
            if (A[u][v] == 1 && visited[v] == 0){  // Adjacent vertex and not visited
                cout << v << ", " << flush;  // Visit vertex
                visited[v] = 1;
                Q.emplace(v);
            }
        }
    }
    cout << endl;
}

int main (){

    int A[8][8] = {0, 0, 0, 0, 0, 0, 0, 0},
                   {0, 0, 1, 1, 1, 0, 0, 0},
                   {0, 1, 0, 1, 0, 0, 0, 0},
                   {0, 1, 1, 0, 1, 1, 0, 0},
                   {0, 1, 0, 1, 0, 1, 0, 0},
                   {0, 0, 0, 1, 1, 0, 1, 1},
                   {0, 0, 0, 0, 0, 1, 0, 0},
                   {0, 0, 0, 0, 0, 1, 0, 0}; // {} 이거 더있어야 한다

    cout << "Vertex: 1 -> " << flush;
    BFS(1, A, 8);

    cout << "Vertex: 4 -> " << flush;
    BFS(4, A, 8);


    return 0;
}

  • Vertex 1 & 4로 시작해서 경로 다 Visited하기

Depth First Search(DFS)

  • using Stack Data structure and hash table

#include <iostream>
#include <queue>

using namespace std;

void DFS(int u, int A[][8], int n){
    static int visited[8] = {0};
    if(visited[u] == 0)
    {
        cout<< u << ", "<<flush;
        visited[u] = 1;
        for(int v=1; v<n; v++)
        {
            if(A[u][v] == 1 && visited[v]==0)
            {
                DFS(v,A,n);
            }
        }
    }

}

int main (){

    int A[8][8] = {0, 0, 0, 0, 0, 0, 0, 0},
                   {0, 0, 1, 1, 1, 0, 0, 0},
                   {0, 1, 0, 1, 0, 0, 0, 0},
                   {0, 1, 1, 0, 1, 1, 0, 0},
                   {0, 1, 0, 1, 0, 1, 0, 0},
                   {0, 0, 0, 1, 1, 0, 1, 1},
                   {0, 0, 0, 0, 0, 1, 0, 0},
                   {0, 0, 0, 0, 0, 1, 0, 0};// {} 이거 더 있어야 한다.

    cout << "Vertex: 4 -> " << flush;
    DFS(4,A,8);
    cout<<endl;


    return 0;
}

DFS using STL(Stack)

#include <iostream>
#include <stack>

using namespace std;

// Based on Lecture
void DFS(int u, int A[][8], int n){
    // initialize visit tracking array and stack
    int visited[8] = {0};
    stack<int> stk;
    stk.emplace(u);

    // Visit start vertex u
    cout << u << ", " <<flush;
    visited[u] = 1; // visited vertex u

    // initial adjacent vertex
    int v =0;

    while(!stk.empty())
    {
        while(v<n)
        {
            if(A[u][v]==1 && visited[v] == 0)
            {
                stk.push(u); // suspend exploring current vertex u
                u = v;

                //Visit Current vertex u
                cout << u << ", "<<flush;
                visited[u] = 1;
                v = -1; // increment will make this 0
            }
            v++;
        }
        v = u; // can set v= 0; but seeing v=u is better;
        u = stk.top(); //return previous suspsended vertex
        stk.pop();
    }

}

// Simpler and adds elements to stack from end
void dfs(int u, int A[][8], int n)
{
    int visited[8] = {0};
    stack<int> stk;
    stk.emplace(u);

    while(!stk.empty())
    {
        u = stk.top();
        stk.pop();
        if(visited[u]!=1)
        {
            cout<< u << ", "<<flush;
            visited[u] = 1;
            for(int v = n -1; v>=0; v--)
            {
                if(A[u][v]==1 && visited[v]== 0)
                {
                    stk.emplace(v);
                }
            }
        }
    }

}

int main (){

    int A[8][8] = {0, 0, 0, 0, 0, 0, 0, 0},
                   {0, 0, 1, 1, 1, 0, 0, 0},
                   {0, 1, 0, 1, 0, 0, 0, 0},
                   {0, 1, 1, 0, 1, 1, 0, 0},
                   {0, 1, 0, 1, 0, 1, 0, 0},
                   {0, 0, 0, 1, 1, 0, 1, 1},
                   {0, 0, 0, 0, 0, 1, 0, 0},
                   {0, 0, 0, 0, 0, 1, 0, 0}; // {} 이거 더 있어야 한다.
    int u = 5;
    cout << "DFS Vertex: " << u << "-> "<< flush;
    DFS(u,A,8);
    cout<<endl;

    cout << "dfs Vertex: " << u << " -> " << flush;
    dfs(u, A, 8);
    cout<<endl;



    return 0;
}

Comments