熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

圖 - 圖的遍歷 - 深度優先遍歷(二)

2013-11-15 15:42:44  來源: 數據結構 

  深度優先遍歷的遞歸算法

  ()深度優先遍歷算法

  typedef enum{FALSETRUE}Boolean;//FALSE為TRUE為

  Boolean visited[MaxVertexNum]; //訪問標志向量是全局量

  void DFSTraverse(ALGraph *G)

  { //深度優先遍歷以鄰接表表示的圖G而以鄰接矩陣表示G時算法完全與此相同

  int i;

  for(i=;in;i++)

  visited[i]=FALSE; //標志向量初始化

  for(i=;in;i++)

  if(!visited[i]) //v i 未訪問過

  DFS(Gi); //以v i 為源點開始DFS搜索

  }//DFSTraverse

  ()鄰接表表示的深度優先搜索算法

  void DFS(ALGraph *Gint i){

  //以v i 為出發點對鄰接表表示的圖G進行深度優先搜索

  EdgeNode *p;

  printf(visit vertex%cG>adjlist[i]vertex);//訪問頂點v i

  visited[i]=TRUE; //標記v i 已訪問

  p=G>adjlist[i]firstedge; //取v i 邊表的頭指針

  while(p){//依次搜索v i 的鄰接點v j 這裡j=p>adjvex

  if (!visited[p>adjvex])//若v i 尚未被訪問

  DFS(Gp>adjvex);//則以V j 為出發點向縱深搜索

  p=p>next; //找v i 的下一鄰接點

  }

  }//DFS

  ()鄰接矩陣表示的深度優先搜索算法

  void DFSM(MGraph *Gint i)

  { //以vi為出發點對鄰接矩陣表示的圖G進行DFS搜索設鄰接矩陣是l矩陣

  int j;

  printf(visit vertex%cG>vexs[i]);//訪問頂點v i

  visited[i]=TRUE;

  for(j=;jn;j++) //依次搜索v i 的鄰接點

  if(G>edges[i][j]==&&!visited[j])

  DFSM(Gj)//(v i v j )∈E且v j 未訪問過故v j 為新出發點

  }//DFSM

  注意

  遍歷操作不會修改圖G的內容故上述算法中可將G定義為ALGraph或MGraph類型的參數而不一定要定義為ALGraph和MGraph的

  指針類型但基於效率上的考慮選擇指針類型的參數為宜


From:http://tw.wingwit.com/Article/program/sjjg/201311/23838.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.