[자료구조]그래프

원문: https://blog.naver.com/qoxmfaktmxj/223757124124

그래프(Graph)

노드와 노드(Node)를 연결하는 간선(Edge)의 집합으로 구성된 비선형 자료구조 (노드 = 정점-Vertex)

정점과 간선의 집합으로 구성 그래프 G 는 G=(V,E)로 표현

V는 정점의 집합, E는 간선의 집합

간선은 정점들을 연결하는 선으로 방향그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분

방향 그래프의 간선은 방향성을 가지며, 무방향 그래프의 간선은 양쪽 방향으로 이동할 수 있음

import java.util.*;

// 노드 클래스 (인접 리스트의 요소) class Node { int vertex; Node next;

public Node(int vertex) { this.vertex = vertex; this.next = null; } }

// 인접 리스트 클래스 class AdjList { Node head; // 리스트의 첫 번째 노드

public void addNode(int vertex) { Node newNode = new Node(vertex); newNode.next = head; head = newNode; }

public void printList(int vertex) { System.out.print(“정점 “ + vertex + “ -> “); Node current = head; while (current != null) { System.out.print(current.vertex + “ “); current = current.next; } System.out.println(); } }

// 그래프 클래스 class Graph { private int vertices; private AdjList[] adjLists;

public Graph(int vertices) { this.vertices = vertices; adjLists = new AdjList[vertices]; for (int i = 0; i < vertices; i++) { adjLists[i] = new AdjList(); } }

// 무방향 간선 추가 public void addEdge(int src, int dest) { adjLists[src].addNode(dest); adjLists[dest].addNode(src); }

// 그래프 출력 public void printGraph() { for (int i = 0; i < vertices; i++) { adjLists[i].printList(i); } } }

// 실행 클래스 public class test11 { public static void main(String[] args) { Graph graph = new Graph(5);

graph.addEdge(0, 1); graph.addEdge(0, 4); graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 3); graph.addEdge(3, 4);

graph.printGraph(); } }

🔹 설명

1. Node 클래스: 단일 연결 리스트 노드 (정점을 저장)
2. AdjList 클래스: 인접 리스트를 관리하며, 간선 정보를 저장
3. Graph 클래스:
   • 정점 개수(vertices)를 저장
   • 인접 리스트 배열(adjLists)을 관리
   • addEdge(int src, int dest) → 무방향 간선 추가
   • printGraph() → 그래프 출력

4. UndirectedGraphExample 클래스: 그래프 생성 및 출력 실행