과제12_그래프

1.(1) 교재에 있는 그래프에 대하여 정점 3에서 출발하여 너비 우선 탐색을 한경우의 방문 순서를 쓰세요. (3) 정점 3에서 출발하여 깊이 우선 탐색을 한 경우의 방문순서를 쓰세요

풀이: (1)-3,1,4,5,0,2,7,8,9,6    (3)-3,1,0,2,4,5,6,7,8,9

 

2번 문제 그래프

2. 위와 같이 그래프가 주어졌을 때, V(정점 집합), E(간선 집합)을 쓰세요. Adjacent list(인접 리스트)를 쓰세요. Topological sort(위상 정렬)하여 정점을 나열하세요. 위상 정렬 알고리즘 pseudo code로 작성하세요.

풀이: (1)-V={A,B,C,D},E={<A,B>,<B,D>,<C,D>} 

(2)-adjacent list=A->B|null   

                           B->D|null

                           C->D|null

                           D|null

(3)-topological sort: A,B,C,D

(4)-각 노드의 진입차수 파악하기->진입차수가 0인 노드에서 출발->선택한 노드와 연결된 모든 간선을 제거하고 연결된 선택 노드의 진입차수 -1하기->다음 과정을 반복하며 차례대로 sort한다.

3.교재 프로그램 11.11, 11.12 프로그램을 본인 코드로 옮겨 봅니다. • 주어진 ‘graph.txt’ 파일을 일고, 이를 너비 우선 탐색하여 교재와 같은 결과를 확인합니다. 

#include <iostream>
#include <fstream>
#define MAX_VTXS 256
#define MAX_QUEUE_SIZE 100
using namespace std;
class Circularqueue {
protected:
    int front;
    int rear;
    int data[MAX_QUEUE_SIZE];
public:
    Circularqueue() { front = rear = 0; }
    bool isempty() { return front == rear; }
    bool isfull() { return (rear + 1) % MAX_QUEUE_SIZE == front; }
    void enqueue(int val) {
        if (!isfull()) {
            rear = (rear + 1) % MAX_QUEUE_SIZE;
            data[rear] = val;
        }
    }
    int dequeue() {
        if (!isempty()) {
            front = (front + 1) % MAX_QUEUE_SIZE;
            return data[front];
        }
    }
    void display() {
        cout << "큐의 내용: ";
        int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for (int i = front + 1; i <= maxi; i++)
            cout << data[i % MAX_QUEUE_SIZE];
    }
};

class AdjMatGraph {
protected:
    int size;
    char vertices[MAX_VTXS];
    int adj[MAX_VTXS][MAX_VTXS];
public:
    AdjMatGraph() { reset(); }
    void reset() {
        size = 0;
        for (int i = 0; i < MAX_VTXS; i++) {
            for (int j = 0; j < MAX_VTXS; j++)
                setEdge(i, j, 0);
        }
    }
    bool isempty() { return size == 0; }
    bool isfull() { return size >= MAX_VTXS; }
    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; }
    void insertVertex(char name) {
        if (!isfull())
            vertices[size++] = name;
        else
            cout << "Error: 그래프 정점 개수 초과했음..." << endl;
    }
    void insertEdge(int u, int v) {
        setEdge(u, v, 1);
        setEdge(v, u, 1);
    }
    void display() {
        cout << size << endl;
        for (int i = 0; i < size; i++) {
            cout << getVertex(i);

            for (int j = 0; j < size; j++)
                cout << "   " << getEdge(i, j);
            cout << endl;
        }
    }
};
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; }
    void BFS(int v) {
        visited[v] = true;
        cout << 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;
                    cout << " " << getVertex(w);
                    que.enqueue(w);
                }
            }
        }
    }
};
int main() {
    int num, val;
    char str;
    SrchAMGraph g;
    ifstream inputFile("graph.txt");
    inputFile >> num;

    for (int i = 0; i < num; i++) {
        inputFile >> str;
        g.insertVertex(str);
        for (int j = 0; j < num; j++) {
            inputFile >> val;
            if (val != 0)
                g.insertEdge(i, j);
        }
    }
    inputFile.close();
    g.display();
    cout << "BFS==>";
    g.resetVisited();
    g.BFS(0);
    cout << endl;
}

실행결과