[그래프] 인접리스트, 인접행렬 (무방향)

 

코드:

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

typedef struct Vertex {
	int vN;
	struct Vertex* next;
}Vertex;

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

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

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

void createVertex(Graph* G, int vN) {
	Vertex* v = (Vertex*)malloc(sizeof(Vertex));
	v->vN = vN;
	v->next = NULL;

	Vertex* q = G->vHead;
	if (q == NULL)
		G->vHead = v;
	else {
		while (q->next != NULL) {
			q = q->next;
		}
		q->next = v;
	}
}

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

void insertEdge(Graph* G, int w, int v1, int v2) {
	Edge* e = (Edge*)malloc(sizeof(Edge));
	e->weight = w;
	e->v1 = findVertex(G, v1);
	e->v2 = findVertex(G, 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;
	}
}

void newInsertEdge(Graph* G, int w, int v1, int v2) {// 이부분 다시보기
	if (w == 0) {
		return;
	}
	Edge* e = (Edge*)malloc(sizeof(Edge));
	e->weight = w;
	e->v1 = findVertex(G, v1);
	e->v2 = findVertex(G, v2);
	e->next = NULL;

	Edge* q = G->eHead;
	if (v1 <= q->v1->vN && v2 < q->v2->vN) {
		e->next = G->eHead;
		G->eHead = e;
	}

	else {
		while (1) {
			if (q->next->v1->vN >= v1) {
				break;
			}
			q = q->next;

			if (q->next == NULL) {
				q->next = e;
				return;
			}
		}
		while (1) {
			if (q->next->v1->vN > v1 || q->next->v2->vN > v2) {
				break;
			}
			q = q->next;

			if (q->next == NULL) {
				q->next = e;
				return;
			}
		}

		e->next = q->next;
		q->next = e;
	}

}

void delete(Graph* G, Edge* q, int v1, int v2) {
	if (q->v1->vN == v1 && q->v2->vN == v2) {
		G->eHead = q->next;
	}
	else {
		for (; q != NULL; q = q->next) {
			if (q->next->v1->vN == v1) {
				if (q->next->v2->vN == v2) {
					break;
				}
			}
		}
		Edge* e = q->next->next;
		q->next = e;
	}
}


int newWeight(Graph* G, int w, int v1, int v2) {
	Edge* q = G->eHead;
	for (; q != NULL; q = q->next) {
		if (q->v1->vN == v1) {
			if (q->v2->vN == v2) {
				q->weight = w;
				return 0;
			}
		}
	}
	return 1;
}

void printG (Graph* G, int n) {
	Edge* q = G->eHead;

	for (; q != NULL; q = q->next) {
		if (q->weight == 0) {
			continue;
		}
		if (q->v2->vN == n) {
			printf(" %d %d", q->v1->vN, q->weight);
		}
		else if (q->v1->vN == n) {
			printf(" %d %d", q->v2->vN, q->weight);
		}
	}
	printf("\n");
}

void main() {
	Graph G;
	init(&G);

	createVertex(&G, 1); createVertex(&G, 2); createVertex(&G, 3);
	createVertex(&G, 4); createVertex(&G, 5); createVertex(&G, 6);

	insertEdge(&G, 1, 1, 2); insertEdge(&G, 1, 1, 3);
	insertEdge(&G, 1, 1, 4); insertEdge(&G, 2, 1, 6);
	insertEdge(&G, 1, 2, 3); insertEdge(&G, 4, 3, 5);
	insertEdge(&G, 4, 5, 5); insertEdge(&G, 3, 5, 6);

	Edge* q = G.eHead;

	char type;
	int n = 0;
	int a = 0, b = 0, w = 0, flag = 0, tmp = 0;

	while (1)
	{
		scanf("%c", &type);

		if (type == 'a') {
			scanf("%d", &n);
			getchar();

			if (n < 1) {
				printf("-1\n");
				continue;
			}
			if (n > 6) {
				printf("-1\n");
				continue;
			}

			printG(&G, n);
		}

		else if (type == 'm') {
			scanf("%d %d %d", &a, &b, &w);
			getchar();

			if (a < 1 || b < 1) {
				printf("-1\n");
				continue;
			}
			if (a > 6 || b > 6) {
				printf("-1\n");
				continue;
			}

			if (a > b) {
				tmp = a;
				a = b;
				b = tmp;
			}

			if (w == 0) {
				delete(&G, q, a, b);
			}
			else {
				flag = newWeight(&G, w, a, b);
				if (flag == 1) {
					newInsertEdge(&G, w, a, b);
				}
			}
		}

		else if (type == 'q') {
			break;
		}
		q = G.eHead;
	}

}