图论的基本算法及性质.doc

图论的基本算法及性质.doc

ID:27869917

大小:212.50 KB

页数:44页

时间:2018-12-06

图论的基本算法及性质.doc_第1页
图论的基本算法及性质.doc_第2页
图论的基本算法及性质.doc_第3页
图论的基本算法及性质.doc_第4页
图论的基本算法及性质.doc_第5页
资源描述:

《图论的基本算法及性质.doc》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、图论的基本算法及性质  二分图(Is-Bipartite)  一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。  这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。  同样,一维数组colors表示节点已着的颜色。  伪代码:  IS-BIPARTITE(g,colors)  letqueuebenewQueue  colors[0]=1  queue.push(0)  whilequeue.empty()==false  letv=queue.top()

2、  queue.pop()  foriequaltoeveryvertexing  ifcolors[i]==0  colors[i]=3-图论的基本算法及性质  二分图(Is-Bipartite)  一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。  这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。  同样,一维数组colors表示节点已着的颜色。  伪代码:  IS-BIPARTITE(g,colors)  letqueuebenewQueue  c

3、olors[0]=1  queue.push(0)  whilequeue.empty()==false  letv=queue.top()  queue.pop()  foriequaltoeveryvertexing  ifcolors[i]==0  colors[i]=3-图论的基本算法及性质  二分图(Is-Bipartite)  一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。  这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。  同样,一维数

4、组colors表示节点已着的颜色。  伪代码:  IS-BIPARTITE(g,colors)  letqueuebenewQueue  colors[0]=1  queue.push(0)  whilequeue.empty()==false  letv=queue.top()  queue.pop()  foriequaltoeveryvertexing  ifcolors[i]==0  colors[i]=3-图论的基本算法及性质  二分图(Is-Bipartite)  一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。  这个问题可以转

5、换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。  同样,一维数组colors表示节点已着的颜色。  伪代码:  IS-BIPARTITE(g,colors)  letqueuebenewQueue  colors[0]=1  queue.push(0)  whilequeue.empty()==false  letv=queue.top()  queue.pop()  foriequaltoeveryvertexing  ifcolors[i]==0  colors[i]=3-图论的基本算法及性质 

6、 二分图(Is-Bipartite)  一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。  这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。  同样,一维数组colors表示节点已着的颜色。  伪代码:  IS-BIPARTITE(g,colors)  letqueuebenewQueue  colors[0]=1  queue.push(0)  whilequeue.empty()==false  letv=queue.top()  queue.pop

7、()  foriequaltoeveryvertexing  ifcolors[i]==0  colors[i]=3-colors[v]  queue.push(i)  elseifcolors[i]==colors[v]  returnfalse  end  end  returntrue  时间复杂度:Θ(V+E),V表示顶点的个数,E表示边的个数  DFS改良(DFS-Improve)  上篇文章提到过,搜索解空间是树形的,也就是在说BFS和DFS。那么在对图进行BFS和DFS有什么区别呢,这个问

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。