[C언어][알고리즘] 연결리스트 인접리스트 그래프 표현

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

typedef struct graphNode {
  int vertex;
  int weight;
  struct graphNode* link;
}graphNode;

typedef struct Graph {
  struct graphNode* adjList[21]; // 인접리스트
}Graph;

void insertEdge(Graph* G, int a, int b, int weight);
void printAdjList(Graph* G);
void printNode(Graph* G, int num);
void modifyWeight(Graph* G, int a, int b, int weight);

int main() {
  // 그래프 초기화
  Graph* G = (Graph*)malloc(sizeof(Graph));
  for (int i = 1; i <= 6; i++) {
    G->adjList[i] = NULL;
  }
    
  insertEdge(G, 1, 2, 1);
  insertEdge(G, 2, 1, 1);
  insertEdge(G, 1, 3, 1);
  insertEdge(G, 3, 1, 1);
  insertEdge(G, 1, 4, 1);
  insertEdge(G, 4, 1, 1);
  insertEdge(G, 1, 6, 2);
  insertEdge(G, 6, 1, 2);
  insertEdge(G, 2, 3, 1);
  insertEdge(G, 3, 2, 1);
  insertEdge(G, 3, 5, 4);
  insertEdge(G, 5, 3, 4);
  insertEdge(G, 5, 5, 4);
  insertEdge(G, 5, 6, 3);
  insertEdge(G, 6, 5, 3);
	// printAdjList(G);

  char oper;
  int num, a, b, w;
  while (1) {
    scanf("%c", &oper);
    if (oper == 'a') { // 노드 출력
        scanf("%d", &num);
		getchar();
		if (1 <= num && num <= 6) { // 문제 조건
			printNode(G, num);
		}
		else {
			printf("-1\n");
		}
	}
	if (oper == 'm') { // 가중치 수정
		scanf("%d %d %d", &a, &b, &w);
		getchar();
		if (1 <= a && a <= 6 && 1 <= b && b <= 6) {
			modifyWeight(G, a, b, w);
		}
		else {
			printf("-1\n");
		}
	}
	if (oper == 'q') {
		break;
	}
  }
}

void insertEdge(Graph* G, int a, int b, int weight) {
  graphNode* Node = (graphNode*)malloc(sizeof(graphNode));
  Node->vertex = a;
  Node->weight = weight;

  // 인접리스트 연결
  Node->link = G->adjList[b];
  G->adjList[b] = Node;
}

void printAdjList(Graph* G) { // 인접리스트 출력
  for (int i = 1; i <= 6; i++) {
    graphNode* p = G->adjList[i];

    while (p != NULL) {
      printf(" %d", p->vertex);
      p = p->link;
    }
    printf("\n");
  }
}

void printNode(Graph* G, int num) { 
  graphNode* p = G->adjList[num];
  while (p != NULL) {
    if (p->link == NULL) {
      break;
    }

    graphNode* p1 = p->link;

    // 정렬
    while (p1 != NULL) {
      if (p->vertex > p1->vertex) {
        int tmp1, tmp2;
        tmp1 = p->vertex;
        tmp2 = p->weight;
        p->vertex = p1->vertex;
        p->weight = p1->weight;
        p1->vertex = tmp1;
        p1->weight = tmp2;
      }
      p1 = p1->link;
    }
    p = p->link;
  }

  p = G->adjList[num];

  while (p != NULL) {
    printf(" %d %d", p->vertex, p->weight);
    p = p->link;
  }
  printf("\n");
}

void modifyWeight(Graph* G, int a, int b, int weight) {
  graphNode* p = G->adjList[a];

  if (weight == 0) { // 간선 삭제
    graphNode* tmp = NULL;
    graphNode* save = p;
    
    while (p != NULL) {
      if (p->vertex == b) {
        if (tmp == NULL) {
            p = p->link;
            save = p;
        }
        else {
          tmp->link = p->link;
        }
        break;
      }
      tmp = p;
      p = p->link;
    }

    G->adjList[a] = save;

    p = G->adjList[b];
    tmp = NULL;
    save = p;

    while (p != NULL) {
      if (p->vertex == a) {
        if (tmp == NULL) {
            p = p->link;
            save = p;
        }
        else {
          tmp->link = p->link;
        }
        break;
      }
      tmp = p;
      p = p->link;
    }

    G->adjList[b] = save;
  }
  else { // 가중치 수정
    while (p != NULL) {
      if (p->vertex == b) {
        p->weight = weight;
        break;
      }
        p = p->link;
    }

    p = G->adjList[b];

    while (p != NULL) {
      if (p->vertex == a) {
        p->weight = weight;
        break;
      }
      p = p->link;
    }

    if (p == NULL) { // 간선이 없는 경우
      insertEdge(G, a, b, weight);
      if (a != b) { // 싸이클이 아닌 경우
        insertEdge(G, b, a, weight);
      }
    }
  }
}