深度优先搜索DFS——图邻接表表示
作为图的一个基本算法，DFS应用很广，可以推广出很多实用的算法。下面贴出一个比较常用的用邻接表表示的图DFS。
/*图邻接表表示DFSinput:17A 1 5B 2 4 3C 2 4 2D 3 6 5 2E 3 7 4 1F 1 4G 1 5output:A E D B C F G*/#include<iostream>#include<cstring>using namespace std;struct LinkNode{ //相邻结点 int vex; LinkNode *next;};struct Graph{ //图邻接表表示 char data; LinkNode *head;};void Create(Graph G[],int n){ //创建图的邻接表 int i,j,m; LinkNode *p; for(i=1; i<=n; i++){ cin>>G[i].data; G[i].head = NULL; cin>>m; for(j=1; j<=m;j++){ p = new LinkNode; cin>>p->vex; p->next = G[i].head; G[i].head = p; } }}void DFS(Graph G[],int v,bool visited[]){ //图邻接表表示DFS LinkNode *p; visited[v] = true; cout<<G[v].data<<' '; p = G[v].head; while(p != NULL){ if(!visited[p->vex])DFS(G,p->vex,visited); p = p->next; }}int main(){ Graph *G = NULL; bool *visited = NULL; int t,n; cin>>t; while(t--){ cin>>n; G = new Graph[n+1]; visited = new bool[n+1]; memset(visited,0,sizeof(visited)); Create(G,n); DFS(G,1,visited);cout<<endl; } return 0;}