Description

133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Answer & Explainaing

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 101

struct Node* createNode(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = val; //
    newNode->numNeighbors = 0; //初始化鄰居數量為0
    newNode->neighbors = NULL; //初始化指向neighbot node的pointer陣列為NULL
    return newNode;
}


// DFS 遍歷並clone graph

struct Node* dfs(struct Node* node, struct Node* visited[]) {
    if (node == NULL) return NULL;

    // 如果該node已經被clone過，直接返回clone node
    if (visited[node->val] != NULL) {
        return visited[node->val];
    }

    // 創建新節點
    struct Node* cloneNode = createNode(node->val);
    visited[node->val] = cloneNode;

    // 分配neighbor pointer的空間
    cloneNode->numNeighbors = node->numNeighbors;
    cloneNode->neighbors = (struct Node**)malloc(cloneNode->numNeighbors * sizeof(struct Node*));

    // 遍歷當前node的所有鄰居，進行clone
    for (int i = 0; i < node->numNeighbors; i++) {
        cloneNode->neighbors[i] = dfs(node->neighbors[i], visited);
    }

    return cloneNode;
}

//clone all graph

struct Node* cloneGraph(struct Node* s) {
    struct Node* visited[MAX_NODES] = {NULL}; // 初始化 visited 陣列

    return dfs(s, visited);
}

Testing

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 101

//定義Node
struct Node {
    int val;
    int numNeighbors; //鄰居數量
    struct Node** neighbors; //指向neighbot node的pointer陣列
};

struct Node* createNode(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = val; //
    newNode->numNeighbors = 0; //初始化鄰居數量為0
    newNode->neighbors = NULL; //初始化指向neighbot node的pointer陣列為NULL
    return newNode;
}


// DFS 遍歷並clone graph

struct Node* dfs(struct Node* node, struct Node* visited[]) {
    if (node == NULL) return NULL;

    // 如果該node已經被clone過，直接返回clone node
    if (visited[node->val] != NULL) {
        return visited[node->val];
    }

    // 創建新節點
    struct Node* cloneNode = createNode(node->val);
    visited[node->val] = cloneNode;

    // 分配neighbor pointer的空間
    cloneNode->numNeighbors = node->numNeighbors;
    cloneNode->neighbors = (struct Node**)malloc(cloneNode->numNeighbors * sizeof(struct Node*));

    // 遍歷當前node的所有鄰居，進行clone
    for (int i = 0; i < node->numNeighbors; i++) {
        cloneNode->neighbors[i] = dfs(node->neighbors[i], visited);
    }

    return cloneNode;
}

//clone all graph

struct Node* cloneGraph(struct Node* s) {
    struct Node* visited[MAX_NODES] = {NULL}; // 初始化 visited 陣列

    return dfs(s, visited);
}

// 測試函數
void testCloneGraph() {
    // 創建一個圖: 1-2-3-4
    struct Node* node1 = createNode(1);
    struct Node* node2 = createNode(2);
    struct Node* node3 = createNode(3);
    struct Node* node4 = createNode(4);

    // 配置鄰居
    node1->numNeighbors = 2;
    node1->neighbors = (struct Node**)malloc(2 * sizeof(struct Node*));
    node1->neighbors[0] = node2;
    node1->neighbors[1] = node4;

    node2->numNeighbors = 2;
    node2->neighbors = (struct Node**)malloc(2 * sizeof(struct Node*));
    node2->neighbors[0] = node1;
    node2->neighbors[1] = node3;

    node3->numNeighbors = 2;
    node3->neighbors = (struct Node**)malloc(2 * sizeof(struct Node*));
    node3->neighbors[0] = node2;
    node3->neighbors[1] = node4;

    node4->numNeighbors = 2;
    node4->neighbors = (struct Node**)malloc(2 * sizeof(struct Node*));
    node4->neighbors[0] = node1;
    node4->neighbors[1] = node3;

    // clone graph
    struct Node* clonedGraph = cloneGraph(node1);

    // 測試clone結果
    printf("Original node value: %d, Cloned node value: %d\n", node1->val, clonedGraph->val);
    printf("Original node's neighbor 1 value: %d, Cloned node's neighbor 1 value: %d\n", node1->neighbors[0]->val, clonedGraph->neighbors[0]->val);
}

// 主要測試函數
int main() {
    testCloneGraph();
    return 0;
}