cycle find (undirected graph에서)

점을 V(Vertex)
edge를 E라고 하면..

 

처음에 V를 쭉 더해놓고

다음부터는 BFS (혹은 DFS도 가능)

 

따라서 complexity는 O (V + E) 

 

https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

cycle find 코드예제:

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    boolean isCyclicUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;
        for (Integer i : adj[v]) {
            if (!visited[i]) {
                if (isCyclicUtil(i, visited, v))
                    return true;
            } else if (i != parent) {
                return true;
            }
        }
        return false;
    }

    boolean isCyclic() {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; ++i)
            if (!visited[i])
                if (isCyclicUtil(i, visited, -1))
                    return true;

        return false;
    }
}

public class CycleDetectionExample {
    public static void main(String[] args) {
        Graph g1 = new Graph(5);
        g1.addEdge(1, 0);
        g1.addEdge(0, 2);
        g1.addEdge(2, 1);
        g1.addEdge(0, 3);
        g1.addEdge(3, 4);
        
        if (g1.isCyclic())
            System.out.println("Graph contains cycle");
        else
            System.out.println("Graph doesn't contain cycle");
    }
}

코드예제임.

 

Digikstra 알고리듬.  근접한 distance 부터 하나씩 추가하는 알고리듬.

import java.util.*;

class Node implements Comparable<Node> {
    int id;
    int distance;
    
    public Node(int id, int distance) {
        this.id = id;
        this.distance = distance;
    }
    
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class DijkstraAlgorithmWithClass {
    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int node = curr.id;
            int dist = curr.distance;
            
            if (dist > distance[node]) continue;
            
            for (int neighbor = 0; neighbor < n; neighbor++) {
                int weight = graph[node][neighbor];
                if (weight > 0 && distance[node] + weight < distance[neighbor]) {
                    distance[neighbor] = distance[node] + weight;
                    pq.offer(new Node(neighbor, distance[neighbor]));
                }
            }
        }
        
        // 출력: 각 노드까지의 최단 경로 길이
        System.out.println("Node\tDistance");
        for (int i = 0; i < n; i++) {
            System.out.println(i + "\t" + distance[i]);
        }
    }
    
    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            // 나머지 그래프 데이터도 입력
        };
        
        dijkstra(graph, 0);
    }
}