Graph (DFS, BFS) 자료구조 (C++)

" class vertex "

- Graph의 정점을 저장하는 단위로 쓰이는 객체이다.

 

1. 변수

- int data  :  정점의 data를 저장한다.

- int degree  :  정점의 인접한 vertex 수를 저장한다.

- bool visited  :  탐색시에 정점이 탐색되었는지 여부를 저장한다.

- vector<vertex*> adj_list  :  정점에 인접한 vertex를 vector로 저장한다.

 

2. 함수

- vertex(int data)  :  셍성자 함수이며, data를 받아와 생성한다.

 

3. class vertex ADT

class vertex {
public:
    int data;
    int degree;
    bool visited;
    vector<vertex*> adj_list;

    vertex(int data) {
        this->data = data;
        this->degree = 0;
        this->visited = false;
    }
};

 

 

" class edge "

- Graph의 간선을 저장하는 단위로 쓰이는 객체이다.

 

1. 변수

- vertex* src  :  간선의 시작 vertex를 저장한다.

- vertex* dst  :  간선의 종료 vertex를 저장한다.

 

2. 함수

- edge(vertex* in_src, vertex* in_dst)  :  생성자 함수이며, 시작, 종료 vertex를 받아와 생성한다.

 

3. class edge ADT

class edge{
public:
    vertex* src;
    vertex* dst;

    edge(vertex* in_src, vertex* in_dst) {
        this->src = in_src;
        this->dst = in_dst;
    }
};

 

 

" class Graph "

- vertex와 edge를 사용하여 Graph를 생성한다.

 

1. 변수

- int size  :  정점의 수를 저장한다.

- edge*** edgeMatrix  :  Matrix 형태로 vertex간의 간선이 존재하는 경우 해당 edge 객체를 저장한다.

- vector<vertex*> vertexList  :  vertex를 vector에 넣어 저장한다.

- vector<vertex*> edgeList  :  edge를 vector에 넣어 저장한다.

 

2. 함수

- vertex* findVertex(int data)  :  data값에 해당되는 vertex를 vertexList에서 찾아 반환한다.

- edge* findEdge(int src, int dst)  :  시작, 종료에 해당되는 vertex의 data를 각각 받아와 해당 vertex의 인덱스를 찾아 edgeMatrix에서 해당 edge를 반환한다.

- void insertVertex(int data)  :  data에 해당되는 vertex가 없는경우 새로 생성하여 vertexList에 추가한다.

- void insertEdge(int src, int dst)  :  src, dst 값에 해당되는 각 vertex 간의 edge가 없는경우 새로 생성하여 edgeMatrix, edgeList에 추가한다. 그리고 각 vertex의 adj_list에 vertex를 추가하며 degree를 증가시킨다.

- void isAdjacent(int src, int dst)  :  각 src, dst 값에 해당되는 vertex가 있는지 확인 후 있다면 findEdge를 통해 edge 유무 여부를 반환한다.

 

3. class Graph ADT

class Graph {
private:
    int size;
    edge*** edgeMatrix;
    vector<vertex*> vertexList;
    vector<edge*> edgeList;
public:
    Graph(int size) { }
    vertex* findVertex(int data) { }
    edge* findEdge(int in_src, int in_dst) { }
    void insertVertex(int data) { }
    void insertEdge(int in_src, int in_dst) { }
    void isAdjacent(int in_src, int in_dst) { }
};

 

4. 예시 코드

- 참고 코드 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/9.%20Graph%2C%20DFS%2C%20BFS/Code_cpp/W13_P2_Graph_Matrix.cpp

- 참고 문제 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/9.%20Graph%2C%20DFS%2C%20BFS/Exercize_pdf/prob-W13_P2.pdf

//
//  W13_2_graph.cpp
//  INHA CLASS
//
//  Created by Kang Minsang on 2020/12/16.
//  Copyright © 2020 Kang Minsang. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;

class vertex {
public:
    int data;
    int degree;
    bool visited;
    vector<vertex*> adj_list;

    vertex(int data) {
        this->data = data;
        this->degree = 0;
        this->visited = false;
    }
};

class edge{
public:
    vertex* src;
    vertex* dst;

    edge(vertex* in_src, vertex* in_dst) {
        this->src = in_src;
        this->dst = in_dst;
    }
};

class Graph {
private:
    int size;
    edge*** edgeMatrix;
    vector<vertex*> vertexList;
    vector<edge*> edgeList;
public:
    Graph(int size) {
        this->size = size;
        edgeMatrix = new edge**[size];
        for(int i=0; i<size; i++) {
            edgeMatrix[i] = new edge*[size];
            for(int j=0; j<size; j++) {
                edgeMatrix[i][j] = NULL;
            }
        }
    }

    vertex* findVertex(int data) {
        vertex* result = NULL;
        for(vertex* w : vertexList) {
            if(w->data == data) {
                result = w;
                break;
            }
        }
        return result;
    }

    edge* findEdge(int in_src, int in_dst) {
        int src = -1;
        int dst = -1;
        for(int i=0; i<vertexList.size(); i++) {
            if(vertexList[i]->data == in_src) {
                src = i;
            }
            if(vertexList[i]->data == in_dst) {
                dst = i;
            }
            if(src != -1 && dst != -1) {
                break;
            }
        }
        edge* result = edgeMatrix[src][dst];
        return result;
    }

    void insertVertex(int data) {
        if(findVertex(data) != NULL) {
            return;
        }
        vertex* newVertex = new vertex(data);
        vertexList.push_back(newVertex);
    }

    void insertEdge(int in_src, int in_dst) {
        vertex* srcV = findVertex(in_src);
        vertex* dstV = findVertex(in_dst);
        if(srcV == NULL || dstV == NULL) {
            cout<<-1<<"\n";
            return;
        }
        if(findEdge(in_src, in_dst) != NULL) {
            cout<<-1<<"\n";
            return;
        }

        int src = -1;
        int dst = -1;
        for(int i=0; i<vertexList.size(); i++) {
            if(vertexList[i]->data == in_src) {
                src = i;
            }
            if(vertexList[i]->data == in_dst) {
                dst = i;
            }
            if(src != -1 && dst != -1) {
                break;
            }
        }
        edge* newEdge = new edge(srcV, dstV);
        edgeMatrix[src][dst] = newEdge;
        edgeMatrix[dst][src] = newEdge;
        edgeList.push_back(newEdge);
        srcV->adj_list.push_back(dstV);
        dstV->adj_list.push_back(srcV);
        srcV->degree++;
        dstV->degree++;
    }

    void print() {
        cout<<vertexList.size()<<" "<<edgeList.size()<<"\n";
    }

    void isAdjacent(int in_src, int in_dst) {
        vertex* srcV = findVertex(in_src);
        vertex* dstV = findVertex(in_dst);
        if(srcV == NULL || dstV == NULL) {
            cout<<-1<<"\n";
            return;
        }
        edge* result = findEdge(in_src, in_dst);
        if(result == NULL) {
            cout<<0<<"\n";
        }
        else {
            cout<<1<<"\n";
        }
        return;
    }
};

int main()
{
    int N, M, K;
    cin>>N>>M>>K;
    Graph graph = Graph(N);
    int I;
    while(N--) {
        cin>>I;
        graph.insertVertex(I);
    }
    int src, dst;
    while(M--) {
        cin>>src>>dst;
        graph.insertEdge(src, dst);
    }
    graph.print();
    while(K--) {
        cin>>src>>dst;
        graph.isAdjacent(src, dst);
    }
}

 

5. 기타

- DFS  :  한 vertex를 시작점으로 시작하여 adj_list의 각 vector 들을 visited가 false인 경우 재귀로 계속 방문한다.

void DFS(vertex* curV) {
    curV->visited = true;
    cout<<curV->data<<" ";
    for(vertex* w : curV->adj_list) {
        if(w->visited == false) {
            DFS(w);
        }
    }
}

- BFS  :  한 vertex를 시작점으로 시작하여 queue에 넣은 뒤 queue가 empty가 될때까지 dequeue를 하며 해당 vertex의 adj_list 의 vertex 들을 visited가 false인 경우 queue 하며 계속 방문한다.

void BFS(vertex* curV) {
    queue<vertex*> q;
    curV->visited = true;
    q.push(curV);
    while(!q.empty()) {
        vertex* temp = q.front();
        q.pop();
        cout<<temp->data<<" ";
        for(vertex* w : temp->adj_list) {
            if(w->visited == false) {
                w->visited = true;
                q.push(w);
            }
        }
    }
}

- DFS 또는 BFS의 정점 우선순위 방문  :  vertexList의 각 vertex의 adj_list내의 각 vertex값을 비교하며 sort 한 후 DFS 또는 BFS를 시작한다.

void sort_vertex() {
    for(int i=0; i<vertexList.size(); i++) {
        sort_adj_list(vertexList[i]);
    }
}

void sort_adj_list(vertex* v) {
    for(int i=0; i<v->adj_list.size()-1; i++) {
        for(int j=i+1; j<v->adj_list.size(); j++) {
            if(v->adj_list[i]->data > v->adj_list[j]->data) {
                vertex* temp = v->adj_list[i];
                v->adj_list[i] = v->adj_list[j];
                v->adj_list[j] = temp;
            }
        }
    }
}

- erase vertex

    void erase_vertex(int n) {
        //존재하지 않거나 개수가 0개인 경우 종료
        if(!isfindVertex(n) || vertexSize == 0) {
            cout<<-1<<"\n";
            return;
        }
        else {
            //N-1 * N-1 크기의 tempMatrix 생성
            edge*** tempMatrix = new edge**[vertexSize-1];
            for(int i=0; i<vertexSize-1; i++) {
                tempMatrix[i] = new edge*[vertexSize-1];
                for(int j=0; j<vertexSize-1; j++) {
                    tempMatrix[i][j] = NULL;
                }
            }
            //삭제될 vertex의 index 찾기
            int middleIdx = 0;
            for(int i=0; i<vertexSize; i++) {
                if(mappingTable[i] == n) {
                    middleIdx = i;
                }
            }
            //mappingTable 한칸씩 앞당기기
            for(int i=middleIdx; i<vertexSize; i++) {
                mappingTable[i] = mappingTable[i+1];
            }
            //EdgeList 에서 삭제 vertex와 연결된 Edge를 삭제한다
            //edgeMatrix 에서 삭제 행 중에서 열값중에 연결된 Edge가 있는경우 해당 Edge를 list에서 제거한다
            for(int i=0; i<vertexSize; i++) {
                if(this->edgeMatrix[middleIdx][i] != NULL) {
                    EdgeList->remove(this->edgeMatrix[middleIdx][i]);
                }
            }
            //tempMatrix로 옮기기
            for(int i=0; i<vertexSize; i++) {
                for(int j=0; j<vertexSize; j++) {
                    //안전지대 : 그대로 붙여넣기
                    if(i<middleIdx && j<middleIdx) {
                        tempMatrix[i][j] = edgeMatrix[i][j];
                    }
                    //대각선으로 이동, 붙여넣기
                    else if(i>middleIdx && j>middleIdx) {
                        tempMatrix[i-1][j-1] = edgeMatrix[i][j];
                    }
                    //열 땡겨서 붙여넣기
                    else if(j>middleIdx) {
                        tempMatrix[i][j-1] = edgeMatrix[i][j];
                    }
                    //행 땡겨서 붙여넣기
                    else if(i>middleIdx) {
                        tempMatrix[i-1][j] = edgeMatrix[i][j];
                    }
                }
            }
            //수정된 Matrix로 저장
            this->edgeMatrix = tempMatrix;
            //마지막으로 삭제 vertex를 VertexList에서 삭제
            VertexList->remove(findVertex(n));
            //크기줄이기
            vertexSize--;

            printEdge();
        }
    }

- erase edge

    void erase_edge(int inputSource, int inputDestination) {
        int source = -1;
        int destination = -1;
        //source, destination 값에 맞는 vertex의 각 index 구하여 저장
        for(int i=0; i<=vertexSize; i++) {
            if(mappingTable[i] == inputSource) {
                source = i;
            }
            if(mappingTable[i] == inputDestination) {
                destination = i;
            }
            if(source != -1 && destination != -1) {
                break;
            }
        }
        //이미 삭제되어 없는경우 : 종료
        if(edgeMatrix[source][destination] == NULL || edgeMatrix[destination][source] == NULL) {
            return;
        }
        //여기서부터 삭제 시작
        //해당 vertex들의 degree 감소
        findVertex(inputSource)->decress_degree();
        findVertex(inputDestination)->decress_degree();
        //해당 Edge를 EdgeList에서 제거
        edge* delEdge = edgeMatrix[source][destination];
        EdgeList->remove(delEdge);
        edgeMatrix[source][destination] = NULL;
        edgeMatrix[destination][source] = NULL;
    }