博文
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通过
......
一个图和其中两点.求出该两点间的所有路径 (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两点之间的最短路径问题
从源点到其余各点的最短......
深度优先搜索算法（ＤＦＳ）源代码(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
&n......