자료구조 - 그래프

그래프란? 연결되어 있는 객체간의 관계를 표현하는 자료구조

그래프는 G, (V,E)로 표시한다.

• V(정점)(vertices) or 노드(node)는 여러가지 특성을 가질 수 있는 객체를 의미
• E(간선)(edge) or 링크(link)는 정점들 간의 관계 의미
• 간선의 종류에 따라 무방향그래프 // 방향 그래프로 나뉠수 있다.
• 혹은 가중치를 부여한 가중치 그래프, 부분 그래프도 존재

---

그래프의 용어

1. 인접 정점(adjacent vertex) - 하나의 정점에서 간선에 의해 직접 연결된 정점
2. 차수(degree) - 하나의 정점에 연결된 다른 정점의 수(방향성을 따진다)
3. 경로(path) - 방향성을 따진다. 간선이 반드시 존재해야함
4. 길이(length) - 경로를 구성하는데 사용된 간선의 수
5. 단순경로(simple path) - 경로중 반복되는 간선이 없는 경로
6. 사이클(cycle) - 시작 정점과 종료 정점이 같은 경로
7. 연결그래프(connected graph) - 모든 정점쌍에 대한 경로가 존재하는 그래프
8. 트리(tree) - 사이클을 가지지 않는 연결 그래프
9. 완전그래프(complete graph) - 모든 정점이 연결되어 있는 그래프

---

※인접 행렬을 이용한 그래프 구현

// AdjMatGraph.h

#include <cstdio>
#define MAX_VTXS 100;

class AdjMatGraph {
protected:
	int size;
    char vertices[MAX_VTXS];
    int adj[MAX_VTXS][MAX_VTXS];
public:
	AdjMatGraph() { reset(); }
    char getVertex(int i) { return vertices[i]; }
    int getEdge(int i, int j) { return adj[i][j]; }
    void setEdge(int i, int j int val) { adj[i][j] = val; }
    bool isEmpty() { return size == 0; }
    bool isFull() { retrun size >= MAX_VTXS; }
    // 공백상태의 그래프 초기화
    void reset() {
    	size = 0;
        for(int i = 0; i < MAX_VTXS; i++){
        	for(int j = 0; j < MAX_VTXS; j++){
            	setEdge(i,j,0)}}
    }
    // 정점삽입
    void insertVertex(char name) {
    	if(!isFull()) { vertices[size++] = name; }
        else{ printf("Error : 그래프 정점 개수 초과\n"); }
    }
    // 간선삽입
    void insertEdge(int u, int v) {
    	setEdge(u,v,1);
        setEdge(v,u,1); // 무방향 그래프라 둘다 존재
    }
    //그래프 정보출력
    void display( FILE *fp = stdout) {
    	fprintf(fp, "%d\n", size);
        for( int i = 0; i<size; i++) {
        	fprintf(fp, "%c ", getVertex(i));
            for(int j=0; j<size; j++) {
            	fprintf(fp, " %3d", getEdge(i,j));}
            fprintf(fp, "\n");
        }
    }
};

---

※인접리스트 을 이용한 그래프 구현

// Node.h

class Node
{
protected:
	int id;
    Node* link;
public:
	Node(int i, Node* l=NULL) : id(i), link(l) { }
    ~Node() {
    	if( link != NULL ) { delete link; } }
    int getId() { return id; }
    Node* getLink() { return link; }
    void setLink(Node* l) { link = l; }
};

// AdjListGraph.h

#include "Node.h"
#include <cstdio>
#define MAX_VTXS 100;

class AdjListGraph
{
protected:
	int size;
    char vertices[MAX_VTXS];
    Node* adj[MAX_VTXS];
public:
	AdjListGraph() : size(0) { }
    ~AdjListGraph() { reset(); }
    void reset(void) {
    	for(int i = 0; i<size; i++){
        	if(adj[i] != NULL) { delete adj[i] }}
    }
    // 정점 삽입
    void insertVertex( char val ) {
    	 if( !isFull() ) {
         	vertices[size] = val;
            adj[size++] = NULL;
         }
         else { printf("Error : 그래프 정점 개수 초과\n"); }
    }
    // 간선 삽입
    void insertEdge(int u, int v) {
    	adj[u] = new Node(v, adj[u]);
        adj[v] = new Node(u, adj[v]);
    }
    void display(){
    	printf("%d\n", size);
        for( int i =0; i<size; i++){
        	printf("%c ", getVertex(i));
            for(Node* v=adj[i]; v != NULL; v=v->getLink()){
            	printf(" %c", getVertex(v->getId())); }
            printf("\n");
        }
    }
    Node* adjacent(int v) { return adj[v]; }
};

---

※그래프를 이용한 두 알고리즘

DFS(depth-first search) - 깊이 우선 탐색 -> 한방향으로 다 진행후 더이상 못가면 되돌아와 가장 가까운 갈림길로 진행

BFS(breadth-first search) - 너비 우선 탐색 ->시작 정점으로부터 가까운 정점 먼저 방문 후 멀리떨어진 곳 방문

 

DFS 는 스택을 BFS는 큐를 사용한다.

---

// DFS
#include <cstdio>

class SrchAMGraph : public AdjMatGraph
{
	bool visited[MAX_VTXS];
public:
	void resetVisited() {
    	for(int i =0; i<size; i++){
        	visited[i] = false;}
    }
    bool isLinked(int u, int v) { return getEdge(u,v) != 0; }
    // DFS
    void DFS(int v) {
    	visited[v] = true; // 현재 정점 방문
        printf("%c ",getVertex(v)); // 정점의 이름 출력
        
        for( int w=0; w<size; w++){
        	if(isLinked(v,w) && visited[w] == false) { // 연결되어 있고, 방문하지 않았다면 순환호출
            	DFS(w); }
        }
    }
 };

// BFS

#include "AdjListGraph.h"
#include "CircularQueue.h"
#include <cstdio>

class SrchAMGraph : public AdjMatGraph
{
	bool visited[MAX_VTXS];
public:
	void resetVisited() {
    	for(int i=0; i<size; i++){
        	visited[i] = false;}
    }
    bool isLinked(int u, int v) { return getEdge(u,v) != 0; }
    
    // BFS
    void BFS(int v) {
    	visited[v] = true;  // 현재정점 방문처리
        printf("%c ", getVertex(v)); // 현재 정점 이름 출력
        
        CircularQueue que;
        que.enqueue(v);  // 큐에 현재 정점삽입
        while(!que.isEmpty()){
        	int v = que.dequeue();  // 제일 최근 방문 정점빼내기
            for(int w=0; w<size; w++){
            	if(isLinked(v,w) && visited[w] == false) { //연결되어있고 방문하지 않았다면
                	visited[w] = true;  //방문처리
                    printf("%c ", getVertex(w)); //정점출력
                    que.enqueue(w); // 큐에 정점삽입
                    }
            }
       }
    }
};