[数据结构]无向图的深度优先非递归遍历

采用邻接表存储实现无向图的深度优先非递归遍历。

输入格式:

先输入两个整数（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);
}