博文
Stein算法--转bpttc的发言(2007-04-20 12:23:00)
摘要：转自http://www.programfan.com/club/showbbs.asp?id=227318&page=1
bpttc的发言
int GCD_Stein( int x, int y ){ int factor = 0; int temp; if ( x < y ) { temp = x; x = y; y = temp; } while ( x != y ) { &......
四种寻路算法并比较 (2007-04-18 15:16:00)
摘要：四种寻路算法并比较
好久没搞这些东西了...想了十分钟才勉强回忆起来...写了三个钟头...好累啊...四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*)用了两张障碍表，一张是典型的迷宫：
char Block[SY][SX]={{1,1,1,1,1,1,1,1,1,1,1 },{1,0,1,0,1,0,0,0,0,0,1 },{1,0,1,0,0,0,1,0,1,1,1 },{1,0,0,0,1,0,1,0,0,0,1 },{1,0,1,1,0,0,1,0,0,1,1 },{1,0,1,0,1,1,0,1,0,0,1 },{1,0,0,0,0,0,0,0,1,0,1 },{1,0,1,0,1,0,1,0,1,0,1 },{1,0,0,1,0,0,1,0,1,0,1 },{1,1,1,1,1,1,1,1,1,1,1 }};
第二张是删掉一些障碍后的:
char Block[SY][SX]={{1,1,1,1,1,1,1,1,1,1,1 },{1,0,1,0,1,0,0,0,0,0,1 },{1,0,1,0,0,0,1,0,1,1,1 },{1,0,0,0,0,0,1,0,0,0,1 },{1,0,0,1,0,0,1,0,0,1,1 },{1,0,1,0,0,1,0,1,0,0,1 },{1,0,0,0,0,0,0,0,1,0,1 },{1,0,1,0,0,0,1,0,1,0,1 },{1,0,0,1,0,0,1,0,0,0,1 },{1,1,1,1,1,1,1,1,1,1,1 }};
结果：尝试节点数 合法节点数 步数深度优先 416/133 110/43 19/25广度优先 190/188 48/49 19/15深度+启发 283/39 82/22 19/19广度+启发 189/185 48/49 19/15
所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。
附：dfs+heu的源程序，bc++ 3.1通过
#include <iostream.h>#include <memory.h>#include <stdlib.h>
#define SX 11 //宽#define SY 10 //长
int ......
一个图和其中两点.求出该两点间的所有路径 (2007-04-18 15:15:00)
摘要：一个图和其中两点.求出该两点间的所有路径
void lookingforway(graph g){ bool visitedp[max] for (v=0;v<g.vertex_number; v ) visited[v]=false; input your start point: special_vertex; visited[special_vertex]=true; for (v=first_adjacent_vertex(g,special_vertex);v; v=next_adjacent_vertex(g,v){ if (!visited[v]){ visited[v]=true; search(g,v); } }}void search(graph g, int v){ visited[v]=true; if v=end_point { 打印路径 return; } for (w=first_adjacent_vertex(g,v);w;w=next_adjacent_vertex(g,v)){ if (!visited[w]) search(g,w); }} ......
图的相关算法(2007-04-18 15:15:00)
摘要：在广度优先搜索的基础上求图中两结点的最短路径需1,将链队列的结点改为“双链”结点，即结点中包含next和priou两个指针；2，修改入队列的操作，插入新的队尾结点时，令其priou域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；3，修改出队列的操作，出队列时，仅移动队头指针，而不将队头结点从链表中删除。由于普里姆算法的时间复杂度为O( N的平方)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为o(eloge)，则适于稀疏图。
7.5重（双）连通图和关节点若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。没有关节点的连通图为双连通图。
关节点的特征： 假设从某个顶点V出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。 若生成树的根结点，有两个或两个以上的分支，则此顶点（生成树的根）必为关节点； 对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。
如何求关键点：1)对根结点来说深度优先遍历看count是否小于结点数，如果小于则该根结点为关节点。2)对生成树上的顶点定义一个函数：low(v)=Min{visited[v],low[w],visited[k]}（k为和v有回边相通的顶点）对顶点v，若（在生成树上）存在一个子树根w,且low[w]>=visited[v]则顶点v为关节点对深度优先遍历算法作如下修改：1，visited[v]的值改为遍历过程中顶点的访问次序count值2,遍历过程中求得low(v)=Min{visited[v],low[w],visited[k]}3,从子树遍历返回时判别low[v]是否>=visited[v]
7.6两点之间的最短路径问题从源点到其余各点的最短路径算法的基本思想：依路径长度递增的次序求得各条路径
7.7拓扑排序如何进行拓扑排序一，从有向图中选取一个没有前驱的顶点(入度为零的顶点)，并输出之；二，从有向图中删去此顶点......
深度优先搜索算法（ＤＦＳ）源代码(2007-04-18 15:12:00)
摘要：深度优先搜索算法（ＤＦＳ）源代码，Ｃ＋＋的，
/*深度搜索，用邻接矩阵存储*/void DFSTraverse(Graph *G){int v;for(v=1;v<=G->vexnum;v++)visited[v]=false;for(v=1;v<=G->vexnum;v++)if(visited[v]==false)DFS(G,v);}void DFS(Graph *G,int v){int w;visited[v]=true;visitfunc(G,v);for(w=FirstAdjex(G,v);w>=0;w=NextAdjex(G,v,w))if(visited[w]==false)DFS(G,w);}int FirstAdjex(Graph *G,int v){int i;for(i=1;i<=G->vexnum;i++)if(G->Garr[v][i])return i;return -1;}int NextAdjex(Graph *G,int v,int w){int i;for(i=w+1;i<=G->vexnum;i++)if(G->Garr[v][i])return i;return -1;}......
[算法] 算法总汇(2007-04-18 15:10:00)
摘要：路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra） 可以用Dijkstra解决问题的特征 负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化 差分约束系统 Floyd 广义路径问题 传递闭包 极小极大距离 / 极大极小距离 Euler Path / Tour 圈套圈算法 混合图的 Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path ......