133. 克隆图

红太狼 2022-11-27 00:55 162阅读 0赞

## 题目 ##

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。  
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list\[Node\]）。  
class Node \{  
public int val;  
public List neighbors;  
\}  
测试用例格式：  
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。  
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。  
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70_pic_center]

## 思路 ##

\*\*题意：\*\*题目意思就是给定一个图的邻接矩阵，然后让你重新遍历一遍这个图，返回一个新的邻接矩阵。也就是图的遍历，可以采用BFS或者DFS。因为是无向图， 遍历对的过程为避免死循环，所以要使用记忆化搜索  
\*\*知识点：\*\*记忆化+搜索

## 代码 ##

/** * Definition for a Node. * struct Node { * int val; * int numNeighbors; * struct Node** neighbors; * }; */
    struct Node** flag;
    struct Node* DFS(struct Node* s)
    { 
        if(s==NULL)return NULL;
        //检查节点是否被访问过,不存在值就是NULL
        if(flag[s->val])return flag[s->val];
    
        struct Node* nod =(struct Node*)malloc(sizeof(struct Node));
        nod->val=s->val;
        nod->numNeighbors=s->numNeighbors;
    
        flag[nod->val]=nod;
        nod->neighbors=(struct Node**)malloc(sizeof(struct Node*) * nod->numNeighbors);
        for(int i=0;i<nod->numNeighbors;i++)
        nod->neighbors[i]=DFS(s->neighbors[i]);
        return nod;
    }
    struct Node *cloneGraph(struct Node *s) { 
        flag=(struct Node**)malloc(sizeof(struct Node*) * 101);
        memset(flag, NULL, sizeof(struct Node*) * 101);
        return DFS(s);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/e1a03f9a09ed448db6591fab2920ca0a.png