1. 详细介绍
文中详细介绍了较为初中级的图优化算法，包含深度优先解析xml，深度广度优先选择解析xml和双重深度广度优先选择解析xml。
2. 深度优先解析xmlDFS
2.1 优化算法观念
从图上某一端点v逐渐，浏览此连接点，随后先后从v中未被浏览的临接点考虑深度优先解析xml图，直至图上上全部和v有途径互通的端点都被浏览；若这时图上还有端点未被浏览，则代选图上一个未被浏览端点做起始点，反复之上全过程，直至图上全部端点都被浏览截止。
深度优先检索解析xml类似树的先序遍历。假设给出图G的初态是全部端点均未被浏览过，在G中随意选择一个端点i做为解析xml的原始点，则深度优先检索解析xml可定义以下：
(1) 最先浏览端点i，并将其浏览标识置为浏览过，即visited[i]=1；
(2) 随后检索与端点i有边相接的下一个端点j，若j未被浏览过，则浏览它，并将j的浏览标识置为浏览过，visited[j]=1，随后从j逐渐反复此全过程，若j已浏览，再看与i有边相接的其他端点；
(3) 若与i有边相接的端点都被浏览过，则退还到前一个浏览端点并反复刚刚全过程，直至图上全部端点都被浏览完止。
2.2 优化算法完成
邻接矩阵的优化算法叙述为下边方式：
void dfs1(graph &g,int i,int n)//深度优先
{//从端点i考虑解析xml 临界值引流矩阵
cout<<g.v[i];//輸出浏览端点
visited[i]=1;
for(j=1;j<=n;j )
if((g.arcs[i][j]==1)&&(!visited[j]))
dfs1(g,j,n);
}
邻接表优化算法叙述为下边方式：
void dfs2(adjlist GL,int i,int n)
{//深度优先 ----从端点i考虑解析xml，算法设计选用邻接表
cout<<i<<" ";
visited[i]=1;
edgenode* p=GL[i];
while(p!=NULL)
{
if(!visited[p->adjvex])
dfs2(G,p.adjvex,n);
p=p->next;
}
}
2.3 应用领域
必须有次序解析xml图，且寻找一个解后輸出就可以。如：trie树排列
多用以只需求得，而且解释树中的反复连接点较多而且反复较难分辨时应用，但通常可以用A*或回溯算法替代。
2.4 举例说明
数独求解。得出一个不详细的数独，让添充在其中空缺的数据。
大量题型：
POJ 1321 旗盘难题：http://www.cublog.cn/u3/105033/showart_2212140.html
类迷宫问题：http://www.jguoer.com/post/2010/02/17/DFS-Code.aspx
数独难题：http://acm.hdu.edu.cn/showproblem.php?pid=1426
3. 深度广度优先选择解析xmlBFS
3.1 优化算法观念
深度广度优先选择检索解析xml类似树的按层级解析xml。设图G的初态是全部端点均未浏览，在G 随意选择一端点i做为原始点，则深度广度优先选择检索的基础观念是：
(1)最先浏览端点i，并将其浏览标示置为已被浏览，即visited[i]=1；
(2)然后先后浏览与端点i有边相接的全部端点W1，W2，…，Wt；
(3)随后再按序浏览与W1，W2，…，Wt有边相接又不曾浏览过的端点；
以此类推，直至图上全部端点都被浏览完截止。
3.2 优化算法完成
用邻接矩阵的优化算法叙述以下：
void bfs1(graph g,int i)
{//从端点i考虑深度广度优先选择解析xml.算法设计为邻接矩阵
Queue q;
cout<<g.v[i];
visited[i]=1;
q.insert(i);
while(!q.empty())
{
int k=q.delete();
for(j=0;j<n;j )
{
if((g.a[k][j])&&!visited[j])
{
cout<<g.v[j];
visited[j]=1;
q.insert(j);
}
}
}
}
用邻接表的优化算法叙述以下 ：
void bfs2(adjlist GL,int i,int n)
{//深度广度优先选择解析xml 从i考虑，应用邻接表做为算法设计
queue q;
cout<<i<<" ";
visited[i]=1;
q.insert(i);
while(!q.empty())
{
int k=q.pop();
edgenode* p=GL[k];
while(p!=NULL)
{
if(!visited[p->adjvex])
{
cout<<p->adjvex;
visited[p->adjvex]=1;
q.insert(p->adjvex);
}
p=p->next;
}
}
}
3.3 应用领域
求难题的最优解
3.4 举例说明
给出一个8*8的方格地形图，再给出最初的状态和停止情况，輸出从原始点抵达停止点的至少计步。
大量题型：
http://www.cppblog.com/firstnode/archive/2009/03/07/75839.html
http://blog.sina.com.cn/s/blog_6635898a0100hwe3.html
http://blog.csdn.net/super_chris/archive/2009/12/26/5082666.aspx
http://www.chenyajun.com/2010/05/08/4540
4. 双重深度广度优先选择解析xml
4.1 优化算法观念
有一些难题依照深度广度优先选择检索规律拓展节点的标准，既合适次序，也合适反序，因此大家考虑到在找寻总体目标节点或途径的检索全过程中，原始节点向总体目标节点和总体目标节点向原始节点另外开展拓展，直到在2个拓展方位上出現同一个子节点，检索完毕，这就是双重检索全过程。
出現的这一同一子节点，大家称之为交叉点，假如的确存有一条从原始节点到总体目标节点的最好途径，那麼按双重检索开展检索必定会在某层出現“交叉”，既有交叉点，原始节点一交叉点一总体目标节点所产生的一条途径就是所愿途径。
4.2 优化算法完成
转自：http://blog.sina.com.cn/s/blog_8627bf080100ticx.html
如今再讨论一下双重广搜免费模板：
void TBFS()
{
bool found=false;
memset(visited,0,sizeof(visited)); // 判重二维数组
while(!Q1.empty()) Q1.pop(); // 顺向序列
while(!Q2.empty()) Q2.pop(); // 反方向序列
//======顺向拓展的情况标识为1，反方向拓展标识为2
visited[s1.state]=1; // 最初的状态标识为1
visited[s2.state]=2; // 完毕情况标识为2
Q1.push(s1); // 最初的状态入顺向序列
Q2.push(s2); // 完毕情况入反方向序列
while(!Q1.empty() || !Q2.empty())
{
if(!Q1.empty())
BFS_expand(Q1,true); // 在顺向序列中检索
if(found) // 检索完毕
return ;
if(!Q2.empty())
BFS_expand(Q2,false); // 在反方向序列中检索
if(found) // 检索完毕
return ;
}
}
void BFS_expand(queue<Status> &Q,bool flag)
{
s=Q.front(); // 从序列中获得头节点s
Q.pop()
for( 每一个s 的子连接点 t )
{
t.state=Gethash(t.temp) // 获得子连接点的情况
if(flag) // 在顺向序列中分辨
{
if (visited[t.state]!=1）// 没在顺向序列出現过
｛
if(visited[t.state]==2) // 该情况在反方向序列中出現过
{
//各种各样实际操作；
found=true；
return;
}
visited[t.state]=1; // 标识为在在顺向序列中
Q.push(t); // 入队
｝
｝else // 在顺向序列中分辨
{
if (visited[t.state]!=2） // 没在反方向序列出現过
｛
if(visited[t.state]==1) // 该情况在顺向向序列中出現过
{
各种各样实际操作；
found=true；
return;
}
visited[t.state]=2; // 标识为在反方向序列中
Q.push(t); // 入队
｝
｝
}
4.3 应用领域
最优控制难题中，了解难题的起止情况和最后情况，且2个情况可互相抵达。
4.4 举例说明
旗盘上面有四个棋盘，让你2个情况，问能否8步内将一个情况迁移到另一个情况？
5. DFS与BFS较为
算法设计：DFS选用栈，而BFS选用序列
优化算法观念：深度搜索与深度广度检索的系统结构和造成系统软件很类似，唯一的差别取决于对拓展连接点选择上。因为其保存了全部的前继连接点，因此在造成后续连接点时能够除掉一部分反复的连接点，进而提升 了检索高效率。这二种优化算法每一次都拓展一个连接点的全部子连接点，而不一样的是，深度搜索下一次拓展的是此次拓展出去的子连接点中的一个，而深度广度检索拓展的则是此次拓展的连接点的弟兄连接点
应用范畴：DFS能够快速的寻找一个解，随后运用这一解开展修枝，而BFS可寻找最优解。
