采用邻接表存储实现无向图的深度优先非递归遍历。
输入格式:
先输入两个整数（m,n）（分别表示待创建的图顶点数和边数），之后是m个顶点的信息，再之后是n 条边。
输出格式:
对每一组输入，在一行中输出该无向图的深度遍历结果，各个数据之间用一个空格分隔，最后一个数据后也有空格。
输入样例:
在这里给出一组输入。例如：
6 6
a b c d e f
a b
a c
a d
b e
b f
d e
输出样例:
在这里给出相应的输出。例如：
a d e b f c
#include <bits/stdc++.h>
#define MVNum 100
using namespace std;
bool visited[MVNum];
typedef struct ArcNode
{int adjvex;struct ArcNode *nextarc;}ArcNode;
typedef struct VNode
{char data;ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct
{AdjList vertices;int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph &G,char v)
{int flag=0;for(int i=0;i<G.vexnum;i++){if(G.vertices[i].data==v){flag=1;return i;}}
}
int CreateDG(ALGraph &G)
{char v1,v2;cin>>G.vexnum>>G.arcnum;for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}for(int i=0;i<G.arcnum;i++){cin>>v1>>v2;int t1=LocateVex(G,v1);int t2=LocateVex(G,v2);ArcNode *p1,*p2;p1=new ArcNode;p1->adjvex=t2;p1->nextarc=G.vertices[t1].firstarc;G.vertices[t1].firstarc=p1;p2=new ArcNode;p2->adjvex=t1;p2->nextarc=G.vertices[t2].firstarc;G.vertices[t2].firstarc=p2;}return 1;
}void DFS(ALGraph G,int vi)
{ArcNode* st[100];int top=-1;int v;ArcNode*p;cout<<G.vertices[vi].data<<" ";visited[vi]=true;top++;st[top]=G.vertices[vi].firstarc;while(top>-1){p=st[top];while(p!=NULL){v=p->adjvex;if(visited[v]==false){cout<<G.vertices[v].data<<" ";visited[v]=true;top++;st[top]=G.vertices[v].firstarc;break;}p=p->nextarc;}if(p==NULL)top--;}
}
void DFSbianli(ALGraph G)
{for(int i=0;i<G.vexnum;i++){visited[i]=false;}for(int i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);
}
void PrintG(ALGraph &G)
{ArcNode *p;for(int i=0;i<G.vexnum;i++){cout<<G.vertices[i].data<<":";p=G.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex+1<<" ";p=p->nextarc;}cout<<endl;}
}
int main()
{ALGraph G;CreateDG(G);//PrintG(G);DFSbianli(G);
})
