本文共 1795 字，大约阅读时间需要 5 分钟。

Depth-first search 深度优先算法，举个例子：二叉树中的前序遍历，一般用递归实现；

Breadth-first search 广度优先算法，举个例子：二叉树的层序遍历，需要用队列实现。

method1:DFS

UndirectedGraphNode *DFS(UndirectedGraphNode *node, unordered_map
   
     *existed){		if (node == NULL)			return NULL;		UndirectedGraphNode *ret;		if ((*existed).find(node->label) == (*existed).end())		{						ret = new UndirectedGraphNode(node->label);			(*existed)[node->label] = ret;		}		else		{			ret = (*existed)[node->label];			return ret;		}				int n = node->neighbors.size();		int i = 0;		while (i
    
     neighbors.push_back( DFS(node->neighbors[i],existed));			i++;					}		return ret;	}	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {		if (node == NULL)			return NULL;		unordered_map
     
       *existed = new  unordered_map
      
       ;		return DFS(node, existed);	}
      
     
    
   

UndirectedGraphNode *cloneGraphII(UndirectedGraphNode *node) {		if (node == NULL)			return NULL;		unordered_map
   
     visited;		queue
    
      Q;		UndirectedGraphNode *head = new UndirectedGraphNode(node->label);		visited.insert({ node->label, head });		Q.push(node);		while (Q.size() > 0)		{			UndirectedGraphNode *tmp = Q.front();			Q.pop();			int n = tmp->neighbors.size();			head = visited[tmp->label];			for (int i = 0; i < n; ++i)			{				if (visited.find(tmp->neighbors[i]->label) == visited.end())				{					head->neighbors.push_back(new UndirectedGraphNode(tmp->neighbors[i]->label));					Q.push(tmp->neighbors[i]);					visited[tmp->neighbors[i]->label] = head->neighbors[i];				}					else				{					head->neighbors.push_back(visited[tmp->neighbors[i]->label]);				}			}		}		return visited[node->label];	}
    
   

用map记录已经出现过的节点。

C++要注意：vector不能通过下标增加原来没有的原素，map可以； new 和malloc一样返回指针

转载地址：http://thovi.baihongyu.com/