用邻接表表示的有向图的广度和深度遍历
#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;}