본문 바로가기
학교생활!

[231111] 고급 자료구조 과제3: 그래프

by Daybreak21 2023. 11. 15.

 

클래스 AdjMatGraph를 완성하라. 다음과 같은 함수를 구현하라.
⦁ void deleteVertex(int val): 인수인 val과 같은이름(혹은 숫자)를 가진 정점을 그래프에서 삭제한다.
⦁ void deleteEdge(int u, int v): 정점 u와 v를 잇는 간선을 삭제한다.
⦁ void display(): 그래프를 출력한다. 그래프에 더이상 존재하지 않는 정점은 출력하지 말아야 한다. (출력의 예는 아래 그림에서 확인)

클래스 AdjListGraph를 완성하라. 다음과 같은 함수를 구현하라.
⦁ void deleteVertex(int val): 인수인 val과 같은이름(혹은 숫자)를 가진 정점을 그래프에서 삭제한다.
⦁ void deleteEdge(int u, int v): 정점 u와 v를 잇는 간선을 삭제한다. (hint: 연결리스트를 잘 활용하라)
⦁ void display(): 그래프를 출력한다. 그래프에 더이상 존재하지 않는 정점은 출력하지 말아야 한다. (출력의 예는 아래 그림에서 확인)

 

※구현할 함수  

-클래스 AdjMatGraph

  • void deleteVertex(int val) : 인수인 val과 같은이름(혹은 숫자)를 가진 정점을 그래프에서 삭제한다.
  • void deleteEdge(int u, int v) : 정점 u와 v를 잇는 간선을 삭제한다.
  • void display() : 그래프를 출력한다. 그래프에 더이상 존재하지 않는 정점은 출력하지 말아야 한다.

- 클래스 AdjListGraph

  • void deleteVertex(int val) : 인수인 val과 같은이름(혹은 숫자)를 가진 정점을 그래프에서 삭제한다.
  • void deleteEdge(int u, int v) : 정점 u와 v를 잇는 간선을 삭제한다.
  • void display() : 그래프를 출력한다. 그래프에 더이상 존재하지 않는 정점은 출력하지 말아야 한다.

 

※출력 화면

<인접 행렬 그래프>

AdjMatGraph g;
//AdjListGraph g;

g.load((char*)"graph.txt");

g.display();


g.deleteEdge(4, 1);
g.deleteEdge(7, 4);
g.deleteEdge(4, 6);
g.deleteEdge(5, 3);
g.deleteEdge(7, 2);
g.deleteEdge(6, 7);
g.deleteEdge(10, 7);
g.deleteEdge(1, 6);
g.deleteEdge(6, 8);

g.display();


g.deleteVertex(4);
g.deleteVertex(6);
g.deleteVertex(7);
g.deleteVertex(1);

g.display();


g.deleteEdge(5, 8);
g.deleteEdge(10, 2);

g.display();

 

main함수 코드 실행 후

 

 

 

<인접리스트 그래프>

AdjListGraph g;

g.load((char*)"graph.txt");

g.display();


g.deleteEdge(4, 1);
g.deleteEdge(7, 4);
g.deleteEdge(4, 6);
g.deleteEdge(5, 3);
g.deleteEdge(7, 2);
g.deleteEdge(6, 7);
g.deleteEdge(10, 7);
g.deleteEdge(1, 6);
g.deleteEdge(6, 8);

g.display();


g.deleteVertex(4);
g.deleteVertex(6);
g.deleteVertex(7);
g.deleteVertex(1);

g.display();


g.deleteEdge(5, 8);
g.deleteEdge(10, 2);

g.display();

main함수 코드 실행 후

 

 

 

 

코드전체

더보기 
#include <iostream>
#include <string>
using namespace std;

#define SWAP(a, b) {a^=b^=a^=b;};
#pragma warning(disable : 4996)
#define _CRT_SECURE_NO_WARNINGS
#define MAX_VTXS	16

class Node
{
protected:
	int		id;		// index of Vertex in vertices 
	Node* link;	// pointer to next node in the adjacency list
public:
	Node(int i = 0, Node* l = NULL) : id(i), link(l) { }
	~Node(void) {
		if (link != NULL)
			delete link;
	}
	int	  getId() { return id; }
	Node* getLink() { return link; }
	void setLink(Node* l) { link = l; }
	void display() { printf("%2d	", id + 1); }
	bool hasID(int val) { return id == val; }

	void insertNext(Node* n) {
		if (n != NULL) {
			n->link = link;
			link = n;
		}
	}

	Node* removeNext() {
		Node* removed = link;
		if (removed != NULL) {
			link = removed->link;
		}
		return removed;
	}
};

class LinkedList {
	Node org;
public:
	LinkedList() : org(0) {}
	~LinkedList() { clear(); }
	void clear() { while (!isEmpty()) delete remove(0); }
	Node* getHead() { return org.getLink(); }
	void setHead(Node* node) { org.setLink(node); } //
	bool isEmpty() { return getHead() == NULL; }

	Node* getEntry(int pos) {
		Node* n = &org;

		for (int i = -1; i < pos; i++, n = n->getLink()) {
			if (n == NULL)
				break;
		}
		return n;
	}

	void insert(int pos, Node* n) {
		Node* prev = getEntry(pos - 1);
		if (prev != NULL)
			prev->insertNext(n);
	}

	Node* remove(int pos) {
		Node* prev = getEntry(pos - 1);
		return prev->removeNext();
	}


	Node* find(int val) {
		for (Node* p = getHead(); p != NULL; p = p->getLink())
			if (p->hasID(val)) return p;
		return NULL;
	}

	void replace(int pos, Node* n) {
		Node* prev = getEntry(pos - 1);
		if (prev != NULL) {
			delete prev->removeNext();
			prev->insertNext(n);
		}
	}

	int size() {
		int count = 0;
		for (Node* p = getHead(); p != NULL; p = p->getLink())
			count++;
		return count;
	}

	void display() {
		//printf( "[�ܼ����Ḯ��Ʈ �׸� �� = %2d] : ", );
		for (Node* p = getHead(); p != NULL; p = p->getLink())
			p->display();
		printf("\n");
	}

};

class AdjMatGraph
{
protected:
	int		size;						// size of graph (# of vertices in the graph)
	int	vertices[MAX_VTXS];				// arrays of vertex names (1, 2, 3 ... N)
	int		adj[MAX_VTXS][MAX_VTXS];	// adjacency matrix

public:
	AdjMatGraph() { reset(); }
	~AdjMatGraph() {  }

	int 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() { return 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(int val) {
		if (!isFull()) vertices[size++] = val;
		else printf("Error: Graph is full\n");
	}

	void insertEdge(int u, int v) {
		setEdge(u, v, 1);
		setEdge(v, u, 1);
	}

	void deleteVertex(int val) {
		// val과 같은 숫자를 가진 정점 찾기
		for (int i = 0; i < size; i++) {
			if (vertices[i] == val) val = i;
		}

		// 관련된 간선들 삭제
		int idx_r = 0;
		for (int i = 0; i < size; i++) {
			int idx_c = 0;
			if (i == val) continue;

			for (int j = 0; j < size; j++) {
				if (j == val) continue;

				setEdge(idx_r, idx_c, getEdge(i, j));
				idx_c++;
			}
			idx_r++;
		}

		// 인접 행렬 재조정
		for (int i = val; i < size - 1; i++) {
			vertices[i] = vertices[i + 1];
		}
		vertices[size - 1] = 0;

		// 전체그래프의 정점 수 변경
		size--;
	}

	void deleteEdge(int u, int v) {
		int idx_u = -1, idx_v = -1;
		for (int i = 0; i < size; i++) {
			if (vertices[i] == u) idx_u = i;
			if (vertices[i] == v) idx_v = i;
		}
		if (idx_u || idx_v) {
			setEdge(idx_u, idx_v, 0);
			setEdge(idx_v, idx_u, 0);
		}
	}

	void display() {
		for (int i = 0; i < size; i++) {
			cout << "N: " << getVertex(i) << "	  ";
			for (int j = 0; j < size; j++) {
				cout << getEdge(i, j) << "	";
			}
			cout << endl;
		}
		cout << endl;
	}

	void load(const char* filename) {
		FILE* fp = fopen(filename, "r");
		if (fp != NULL) {
			int n;
			fscanf(fp, "%d", &n);
			for (int i = 0; i < n; i++) {
				char	str[80];
				int		node;

				fscanf(fp, "%d", &node);
				insertVertex(node);

				for (int j = 0; j < n; j++) {
					fscanf(fp, "%s", str);

					if (strcmp(str, "O") == 0)
						insertEdge(i, j);
				}
			}
			fclose(fp);
		}
	}

};


class AdjListGraph
{
	int		size;					// size of graph (# of vertices in the graph)
	int	vertices[MAX_VTXS];			// arrays of vertex names (1, 2, 3 ... N)
	LinkedList* adj[MAX_VTXS];		// adjacency list

public:
	AdjListGraph(void) : size(0) { }
	~AdjListGraph(void) { reset(); }

	void reset(void) {
		for (int i = 0; i < size; i++)
			if (adj != NULL) delete adj[i];
		size = 0;
	}

	bool isEmpty() { return (size == 0); }
	bool isFull() { return (size >= MAX_VTXS); }
	int getVertex(int i) { return vertices[i]; }

	void insertVertex(int val) {
		if (!isFull()) {
			vertices[size] = val;
			adj[size++] = new LinkedList();
		}
		else printf("Error: Graph is full\n");
	}

	void insertEdge(int u, int v) {
		adj[u]->insert(adj[u]->size(), new Node(v, NULL));
	}

	LinkedList* getHead(int i) { return adj[i]; }

	void deleteVertex(int val) {

		// 관련된 간선들 삭제 (
		for (int i = 0; i < size; i++) {
			deleteEdge(vertices[i], val);
		}

		//val과 같은 숫자를 가진 정점 찾기
		for (int i = 0; i < size; i++) {
			if (vertices[i] == val) val = i;
		}

		// 인접 행렬 재조정
		for (int i = val; i < size - 1; i++) {
			vertices[i] = vertices[i + 1];
			adj[i] = adj[i + 1];
		}

		// 전체그래프의 정점 수 변경
		size--;

	}

	void deleteEdge(int u, int v) {

		int idx_u = -1;
		for (int i = 0; i < size; i++) {
			if (vertices[i] == u) idx_u = i;
		}
		if (idx_u != -1) {
			Node* prev = NULL;
			for (Node* curr = getHead(idx_u)->getHead(); curr != NULL; curr = curr->getLink()) {
				if (curr->getId() == v - 1) {
					if (prev == NULL) getHead(idx_u)->remove(0);
					else prev->removeNext();
					break;
				}
				prev = curr;
			}
		}

		int idx_v = -1;
		for (int i = 0; i < size; i++) {
			if (vertices[i] == v) idx_v = i;
		}
		if (idx_v != -1) {
			Node* prev = NULL;
			for (Node* curr = getHead(idx_v)->getHead(); curr != NULL; curr = curr->getLink()) {
				if (curr->getId() == u - 1) {
					if (prev == NULL) getHead(idx_v)->remove(0);
					else prev->removeNext();
					break;
				}
				prev = curr;
			}
		}
	}

	void display() {
		for (int i = 0; i < size; i++) {
			if (getHead(i)->getHead() == NULL) continue;
			printf("N: %2d     ", getVertex(i));
			getHead(i)->display();
		}
		printf("\n");
	}

	void load(char* filename) {
		FILE* fp = fopen(filename, "r");
		if (fp != NULL) {
			int n;
			fscanf(fp, "%d", &n);
			for (int i = 0; i < n; i++) {
				char	str[80];
				int 	node;

				fscanf(fp, "%d", &node);
				insertVertex(node);

				for (int j = 0; j < n; j++) {
					fscanf(fp, "%s", str);

					if (strcmp(str, "O") == 0)
						insertEdge(i, j);
				}
				//printf("\n");
			}
			fclose(fp);
		}
	}
};


int main()
{
	//AdjMatGraph g;
	AdjListGraph g;

	g.load((char*)"graph.txt");

	g.display();


	g.deleteEdge(4, 1);
	g.deleteEdge(7, 4);
	g.deleteEdge(4, 6);
	g.deleteEdge(5, 3);
	g.deleteEdge(7, 2);
	g.deleteEdge(6, 7);
	g.deleteEdge(10, 7);
	g.deleteEdge(1, 6);
	g.deleteEdge(6, 8);

	g.display();


	g.deleteVertex(4);
	g.deleteVertex(6);
	g.deleteVertex(7);
	g.deleteVertex(1);

	g.display();


	g.deleteEdge(5, 8);
	g.deleteEdge(10, 2);

	g.display();


	return 0;
}

 

 

<class AdjMatGraph>

 

void deleteEdge(int u, int v)

void deleteEdge(int u, int v) {
    int idx_u = -1, idx_v = -1;
    for (int i = 0; i < size; i++) {
        if (vertices[i] == u) idx_u = i;
        if (vertices[i] == v) idx_v = i;
    }
    if (idx_u || idx_v) {
        setEdge(idx_u, idx_v, 0);
        setEdge(idx_v, idx_u, 0);
    }
}


매개변수로 들어온 값과 같은 숫자를 가진 정점을 찾고 삭제를 진행한다. 

 

 

void deleteVertex(int u, int v)

void deleteVertex(int val) {
    // val과 같은 숫자를 가진 정점 찾기
    for (int i = 0; i < size; i++) {
        if (vertices[i] == val) val = i;
    }

    // 관련된 간선들 삭제
    int idx_r = 0;
    for (int i = 0; i < size; i++) {
        int idx_c = 0;
        if (i == val) continue;

        for (int j = 0; j < size; j++) {
            if (j == val) continue;

            setEdge(idx_r, idx_c, getEdge(i, j));
            idx_c++;
        }
        idx_r++;
    }

    // 인접 행렬 재조정
    for (int i = val; i < size - 1; i++) {
        vertices[i] = vertices[i + 1];
    }
    vertices[size - 1] = 0;

    // 전체그래프의 정점 수 변경
    size--;
}


매개변수로 들어온 값과 같은 숫자를 가진 정점을 찾고 삭제를 진행한다. 

index_row,와, index_col을 새로 만들어지는 배열의 인덱스로 사용하고, i와 j는 삭제하는 정점의 인덱스와 같으면 그 반복문은 뛰어넘어 배열을 새로 저장한다. 

 

 

 

void display()

void display() {
    for (int i = 0; i < size; i++) {
        cout << "N: " << getVertex(i) << "	  ";
        for (int j = 0; j < size; j++) {
            cout << getEdge(i, j) << "	";
        }
        cout << endl;
    }
    cout << endl;
}


반복문을 사용해서 배열을 순회

 

 

 

<class AdjListGraph>

 

void deleteEdge(int u, int v)

void deleteEdge(int u, int v) {

	int idx_u = -1;
	for (int i = 0; i < size; i++) {
		if (vertices[i] == u) idx_u = i;
	}
	if (idx_u != -1) {
		Node* prev = NULL;
		for (Node* curr = getHead(idx_u)->getHead(); curr != NULL; curr = curr->getLink()) {
			if (curr->getId() == v - 1) {
				if (prev == NULL) getHead(idx_u)->remove(0);
				else prev->removeNext();
				break;
			}
			prev = curr;
		}
	}

	int idx_v = -1;
	for (int i = 0; i < size; i++) {
		if (vertices[i] == v) idx_v = i;
	}
	if (idx_v != -1) {
		Node* prev = NULL;
		for (Node* curr = getHead(idx_v)->getHead(); curr != NULL; curr = curr->getLink()) {
			if (curr->getId() == u - 1) {
				if (prev == NULL) getHead(idx_v)->remove(0);
				else prev->removeNext();
				break;
			}
			prev = curr;
		}
	}
}


간선을 삭제하는 과정 전에 vertieces에서 입력받은 값과 같은 인덱스 번호를 찾고 idx_u, r에 저장하여 사용한다. 

prev, curr 두개의 노드 포인터를 사용한다. 
현재 노드의 값과 삭제하는 값을 비교하여 삭제해야하는 노드를 찾고 그 이전노드의 removeNext()함수를 사용하여 삭제한다.  

 

void deleteVertex(int u, int v)

void deleteVertex(int val) {

	// 관련된 간선들 삭제 (
	for (int i = 0; i < size; i++) {
		deleteEdge(vertices[i], val);
	}

	//val과 같은 숫자를 가진 정점 찾기
	for (int i = 0; i < size; i++) {
		if (vertices[i] == val) val = i;
	}

	// 인접 행렬 재조정
	for (int i = val; i < size - 1; i++) {
		vertices[i] = vertices[i + 1];
		adj[i] = adj[i + 1];
	}

	// 전체그래프의 정점 수 변경
	size--;

}


리스트의 헤드포인터가 저장된 배열을 돌면서 value값과 같은 노드를 삭제한다.  
인접 행렬을 재조정하고, 정점 수를 변경하면서 정점헤드포인트가 삭제된다. 

 

void display()

void display() {
    for (int i = 0; i < size; i++) {
        if (getHead(i)->getHead() == NULL) continue;
        printf("N: %2d     ", getVertex(i));
        getHead(i)->display();
    }
    printf("\n");
}


헤드포인터 배열을 돌면서 display()함수 실행

 

'학교생활!' 카테고리의 다른 글

[231222] 고급 자바프로그래밍 프로젝트: 캘린더  (0) 2024.01.01
[231104] 고급 자바프로그래밍 과제: Puzzle  (1) 2023.11.13
[230602] 자료구조 과제6: 연결 리스트와 힙  (0) 2023.07.11
[230520] 고급C++프로그래밍: 과제3  (0) 2023.05.31
[230503] 자료구조 과제5: 순환(recursion)  (0) 2023.05.07

관련글

티스토리툴바