用邻接表表示的有向图的广度和深度遍历

#include<iostream>#include<stack>using namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20#define INFI 10000typedef enum {DG, DN, UDG, UDN} GraphKind;typedef enum { BLACK, WHITE, GRAY} COLOR;//邻接表typedef struct ArcNode{     int adjvex; struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int key;int d ;           //距离ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum,arcnum;GraphKind kind;} ALGraph;void CreateDG(ALGraph &G)      //用邻接表创建有向图{   int i;   cout<<"Input vexnum:"<<endl;   cin>>G.vexnum;   cout<<"Input arcnum:"<<endl;   cin>>G.arcnum;   for( i=0; i<G.vexnum; i++)   {   G.vertices[i].key=i;   G.vertices[i].firstarc=NULL;   }   int v1,v2;   for( int k=0; k<G.arcnum; ++k)   {      cout<<"Input two index:"<<endl;  cin>>v1>>v2;  if( v1==v2 )  {  --k;  cout<<"two index are same, renew input:"<<endl;  continue;  }  ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));  node->adjvex=v2;  node->nextarc=NULL;      if(G.vertices[v1].firstarc==NULL)  {         G.vertices[v1].firstarc=node;  }  else  {     ArcNode *next=G.vertices[v1].firstarc;  while(next->nextarc)  {  next=next->nextarc;  }  next->nextarc=node;  }     }   for( int j=0; j<G.vexnum; j++)   {       cout<<G.vertices[j].key<<" :";   ArcNode *next=G.vertices[j].firstarc;   while( next!=NULL)   {   cout<<next->adjvex<<" ";   next=next->nextarc;   }   cout<<endl;   }}int  getFirstNeighbor(ALGraph G, int v)    //获得第一个结点{       ArcNode *next = G.vertices[v].firstarc;   if( next!=NULL )   {           return next->adjvex;   }       else    {       return -1;   }}int getNextNeighbor(ALGraph G, int v, int w)   //获得w结点的下一个结点{       ArcNode *next = G.vertices[v].firstarc;   while( next->nextarc!=NULL&&next->adjvex!=w )   {     next = next->nextarc;   }   if(next->nextarc==NULL)   {   return -1;   }   else   {    return next->nextarc->adjvex;   }}bool visited[MAX_VERTEX_NUM];deque<int> Q;void BFS(ALGraph G, int v){cout<<"visit:"<<v<<endl;visited[v]=true;Q.push_back(v);while(!Q.empty()){int node = Q.front();Q.pop_front();for( int w=getFirstNeighbor(G, node); w>=0; w=getNextNeighbor(G, node, w)){   if( !visited[w] ){               cout<<"visit:"<<w<<endl;   visited[w]=true;   Q.push_back(w);}}}}void BFSTraverse(ALGraph G)     //广度优先遍历{    for( int i=0; i<G.vexnum; ++i){visited[i]=false;}    for( int j=0; j<G.vexnum; ++j)    {if(!visited[j]){     BFS(G, j);}    }}void DFS(ALGraph G, int v){    cout<<"visit:"<<v<<endl;visited[v] = true;for( int w = getFirstNeighbor(G,v); w>=0; w=getNextNeighbor(G, v, w)){if(!visited[w]){DFS(G, w);}}}void DFSTraverse(ALGraph G)     //深度优先遍历{    for( int i=0; i<G.vexnum; ++i){visited[i]=false;}    for( int j=0; j<G.vexnum; ++j)    {if(!visited[j]){     DFS(G, j);}    }}int main(){   ALGraph G;CreateDG(G);    DFSTraverse(G);return 0;}

2楼wang19890326昨天 19:37

[code=cpp]nvoid BFS_MIN_DISTANCE(ALGraph G, int v)n{n for( int i=0; i<G.vexnum; ++i)n {nt d[i] = INFINITY;n }n visited[v] = true;n d[v] = 0;n Q.push_back(v);n while( !Q.empty())n {nt tint node = Q.front();nttQ.pop_front();nttfor( int w=getFirstNeighbor(G, node); w>=0; w=getNextNeighbor(G, node, w))ntt{ ntttif( !visited[w] )nttt{nttt visited[w]=true;nttt d[w] = d[node]+1;nttt Q.push_back(w);nttt}ntt} n }n}n[/code]n最短路径

1楼wang19890326昨天 19:08

[code=cpp]nnvoid DFS_Non_Rc(ALGraph G, int v)n{n stack<int> S;ntfor( int i=0; i<G.vexnum; ++i)nt{nttvisited[i] = false;nt}ntS.push(v);ntvisited[v] = true;ntwhile(!S.empty())nt{n int node = S.top();nt S.pop();nt for( int w=getFirstNeighbor(G, node); w>=0; w=getNextNeighbor(G, node, w))ntt{ ntttif( !visited[w] )nttt{nttt S.push(w);nttt visited[w] = true;nttt}ntt} nt nt}nn}[/code]n无需递归的深度优先遍历