Week10_그래프_실습

1. 간선 구조체 만들기

typedef struct Edge {
	int weight;
	char v1, v2;
	struct Edge* next;
}Edge;

2. 인접정점 구조체 만들기

typedef struct IncidentEdge {
	char adjVertex;
	Edge* e;
	struct IncidentEdge* next;
}IncidentEdge;
//정점이 관리, 인접리스트는 간선 만들고 생성

3. 정점 구조체 만들기

typedef struct Vertex {
	char vName;
	IncidentEdge* iHead;
	struct Vertex* next;
}Vertex;

 

4. 그래프 구조체 만들기

typedef struct {
	Vertex* vHead;
	Edge* eHead;
}Graph;

5. 그래프 초기화

-정점 Head, 간선 Head 초기화

void init(Graph* G) {
	G->vHead = NULL;
	G->eHead = NULL;
}

6. 정점 생성

void makeVertex(Graph* G, char vName) {
	Vertex* v = (Vertex*)malloc(sizeof(Vertex));
	v->vName = vName;
	v->iHead = NULL;
	v->next = NULL;

	Vertex* q = G->vHead;

	if (q == NULL)
		G->vHead = v;
	else {
		while (q->next != NULL) { //마지막 노드에서 멈춤
			q = q->next;
		}
		q->next = v;
	}
}

7. 인접정점 생성

오름차순으로 인접정점 삽입

void insertIncidentEdge(Vertex* v, char av, Edge* e) {
	IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
	p->adjVertex = av;
	p->e = e;
	p->next = NULL;

	IncidentEdge* q = v->iHead;
	if (q == NULL) {
		v->iHead = p;
	}
	else {
		while (q->next != NULL) {
			if (q->next->adjVertex < av)
				q = q->next;
			else {
				p->next = q->next;
				q->next = p;
				return;
			}
		}
		q->next = p;
	}

}

8. 정점 찾기

Vertex* findVertex(Graph* G, char vName) {
	Vertex* p = G->vHead;
	int cnt = 0;
	while (p->vName != vName) {
		p = p->next;
	}
	return p;
}

9. 간선 삽입

void insertEdge(Graph* G, int w, char v1, char v2) {
	Edge* e = (Edge*)malloc(sizeof(Edge));
	e->weight = w;
	e->v1 = v1; //이름으로 주소 값 찾는 함수로
	e->v2 = v2;
	e->next = NULL;

	Edge* q = G->eHead;

	if (q == NULL)
		G->eHead = e;
	else {
		while (q->next != NULL) { //마지막 노드에서 멈춤
			q = q->next;
		}
		q->next = e;
	}
	if (v1 != v2) {
		Vertex* v = findVertex(G, v1);
		insertIncidentEdge(v, v2, e);
		v = findVertex(G, v2);
		insertIncidentEdge(v, v1, e);
	}
	else {
		Vertex* v = findVertex(G, v1);
		insertIncidentEdge(v, v2, e);
	}
}

10. 인접정점 출력

void printAdj(Graph* G, char ch) {
	Vertex* p = G->vHead;
	IncidentEdge* q;
	int flag = 0;
	//printf("%c\n", ch);
	for (; p != NULL; p = p->next) {
		if (ch == p->vName) {
			//printf("%c : ", p->vName);
			flag = 1;	

			for (q = p->iHead; q != NULL; q = q->next) {
				if (q->e->weight == 0) continue;
				printf(" %c %d", q->adjVertex, q->e->weight);
			}
		}
	}
	if (flag == 0) printf("-1"); //정점 없음
	printf("\n");

}

11. 가중치 변경

void modifyWeight(Graph* G, char v1, char v2, int w) {
	if (v1 > '6' || v1 < '0') {
		printf("-1\n");
		return;
	}
	if (v2 > '6' || v2 < '0') {
		printf("-1\n");
		return;
	}
	Vertex* p = findVertex(G, v1);
	IncidentEdge* q = p->iHead;
	IncidentEdge* r = p->iHead;
	int flag = 0;


	while (q) {
		if (q->adjVertex == v2) { //한쪽만 변경해도됨
			q->e->weight = w;
			flag = 1;
			break;
		}
		else {
			q = q->next;
		}
	}
	if (flag == 0) {
		insertEdge(G, w, v1, v2);
	}
}//부착리스트는 정점 중심