算法学习 之遍历

/********************广度优先遍历算法*******************/

void BFSTraverse(Graph G, Status (*Visit)(int v))
 {  // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
for (v=0; v<G.vexnum; ++v)   visited[v] = FALSE;
InitQueue(Q);     // 置空的辅助队列Q
for ( v=0; v<G.vexnum; ++v )
if (!visited[v])
{  EnQueue(Q, v);                   //入队
visited[u] = TRUE;   Visit(u);    //访问
while (!QueueEmpty(Q))
{  DeQueue(Q, u);              //出队
for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )
if ( ! visited[w]) 
{  visited[u] = TRUE;   Visit(u);   //访问
EnQueue(Q, w);               //入队
}
}  //while
}  //if
} // BFSTraverse　
// FirstAdjVex(G, u)寻找u的第一个邻接点，并返回其下标位置
// NextAdjVex(G, u, w) w是u的一个邻接点，寻找u的所有邻接点中位于w后面的那一个，并返回其下标位置

 

评论

4 楼 sblig 2012-05-22  

用Dijkstra算法求最短路径

#define MAX_VERTEX_NUM  20
void ShortestPath_DIJ(MGraph G,int v1)   //V1是源点
{  //用Dijkstra算法求有向网G的v10顶点到其余顶点的最短路径
 int P[ MAX_VERTEX_NUM] , D[ MAX_VERTEX_NUM];
   int final[ MAX_VERTEX_NUM]; 
   int i,v,w,min,pre;
   for(v=1; v<=G.vexnum; ++v)
   {    //D[ ],final[ ],P[ ]初始化
final[v]=FALSE;  D[v]=G.arcs[v1][v].adj;
      if(D[v]<INFINITY)   P[v]=1;
      else P[v]=0;
    }
    D[v1]=0;  final[v1]=TRUE;  //源点v0相关数组初始化
   for( i=2; i<=G.vexnum; ++i)
    { 
min=INFINITY;   //寻找final[]=0的D[ ]中最小值
       for(w=1; w<=G.vexnum; ++w)  //最小值->min，最小值的下标->v
         if(!final[w] &&D [w]<min)  { v=w; min=D[w];}
       final[v]=TRUE;   //入选
       for(w=1; w<=G.vexnum; ++w) //根据入选的v顶点修改D[ ]及p[ ]
          if(!final[w] && (min+G.arcs[v][w].adj<D[w]))
	       {  D[w]=min+G.arcs[v][w].adj;  P[w]=v;  }
     } //逐渐更新D[ ] 及p[ ]
     for (w=1; w<=G.vexnum; ++w)  //依次输出
     {    printf("%d",w);   pre=P[w];
          if ( pre==0)
             if(w==v1)  printf("    source point \n");
             else       printf("    No Path \n");
          else 
{   while( pre!=v1 ) { printf("<--%d",pre); pre=P[pre];}
	          printf("<--%d **** distance is:%d\n",v0,D[w]);
	       }  //else
     } //for 输出结束
} ShortestPath_DIJ

void ShortestPath_FLOYD(MGraph G,PathMatrix &p[],DistancMatrix D[])
{
for(v=0;v<G.vexnum;v++)
  for(w=0;w<G.vexnum;w++)
{  D[v][w] = G.arcs[v][w]; 
     for(u=0;u<G.vexnum;u++)  P[v][w][u]=FALSE;
     if(D[v][w] < INFINITY) 
{    P[v][w][v] = TRUE;  P[v][w][w] = TRUE;  }
}
for(v=0;v<G.vexnum;v++)
  for(w=0;w<G.vexnum;w++)
    for(u=0;u<G.vexnum;u++)
       if(D[v][u] + D[u][w] < D[v][w])
{   D[v][w] = D[v][u]+D[u][w];
    for(i=0; i<G.vexnum; i++)
      P[v][w][i]= P[v][u][i] || P[u][w][i];
}    
}

 

3 楼 sblig 2012-05-22  

   0  1  2  3  4  5
0   *  6  1  5  *  *
1   6  *  5  *  3  *
2   1  5  *  5  6  4
3   5  *  5  *  *  2
4   *  3  6  *  *  6
5   *  *  4  2  6  *

U 1
到达顶点 V1 V2 V3 V4 V5 V6
经由U中          V1 V1 V1 V1 V1 V1
耗费          0 6 1 5 * *
入选顶点                V3

U 13
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V1 V3 V3
耗费         0 5 0 5 6 4
入选顶点                                          V6

U 136
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V3 V3
耗费         0 5 0 2 6 0
入选顶点                         V4

U 1364
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V3 V3
耗费         0 5 0 0 6 0
入选顶点         V2

U 13642
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V2 V3
耗费         0 0 0 0 3 0
入选顶点                                        V5

U 136425
到达顶点 V1 V2 V3 V4 V5 V6
完成 经由U中 V1 V3 V1 V6 V2 V3
耗费         0 0 0 0 0 0
入选顶点

2 楼 sblig 2012-05-22  

/****************最小生成树Prim算法******************/

typedef struct
{   VertexType adjvex;
VRType lowcost;
} closedge[MAX_VERTEX_NUM];
void MiniSpanTree_PRIM (MGraph G, VerTexType u)
{
k = LocateVex ( G, u );     // 顶点u为构造生成树的起始点
for ( j=0; j<G.vexnum; ++j )  // 辅助数组初始化
if (j!=k)  closedge[j] = { u, G.arcs[k][j].adj }; 
closedge[k].lowcost = 0;                   // 初始，U＝{u}
for (i=1; i<G.vexnum; ++i) 
{  //在其余顶点中选择
k = minimum(closedge);        // 求出T的下一个结点(k)
printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边
closedge[k].lowcost = 0;             // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj < closedge[j].lowcost)
{   closedge[j].adjvex=G.vexs[k];
         closedge[j].lowcost=G.arcs[k][j].adj;
};
}
} // MiniSpanTree_PRIM

1 楼 sblig 2012-05-22  

/********************深度优先遍历算法*******************/


//--- 下列算法使用两个的全局变量 ---
Boolean visited[MAX]; // 访问标志数组
Status (* VisitFunc)(int v);      // 函数变量
void DFSTraverse(Graph G, Status (*Visit)(int v)) 
{      // 对图G作深度优先遍历。
VisitFunc = Visit; 
for (v=0; v<G.vexnum; ++v) 
visited[v] = FALSE;                  // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v) 
if (!visited[v]) DFS(G, v);      // 对尚未访问的顶点调用DFS
}
void DFS (Graph G, int v) 
{   // 从顶点v出发递归地深度优先遍历图G。
visited[v] = TRUE;  VisitFunc(v);   //访问第v个顶点
for (w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) )
if (!visited[w]) DFS(G, w); 
// 对v的尚未访问的邻接顶点w递归调用DFS
}
// FirstAdjVex(G, u)寻找u的第一个邻接点，并返回其下标位置
// NextAdjVex(G, u, w) w是u的一个邻接点，寻找u的所有邻接点中位于w后面的那一个，并返回其下标位置