Description

实现图的邻接表存储结构及一些基本操作函数。在此基础上实现图的深度遍历算法并加以测试。本题只给出部分代码,请补全内容。

oj源代码过于冗长，此处不贴出来。解题用栈结构替换头插法链表。

输入格式

第一行：输入0到3之间整数(有向图:0,有向网:1,无向图:2,无向网:3)；
第二行：输入顶点数和边数；
第三行：输入各个顶点的值（字符型，长度〈3）；(遍历从输入的第一个顶点开始)
第四行：输入每条弧(边)弧尾和弧头(以空格作为间隔),如果是网还要输入权值；

输出格式

输出对图深度遍历的结果。

输入样例

0
3 3
a b c
a b
b c
c b

输出样例

a b c

提示

注意题目的邻接表采用的是头插法，也就是后出现的边节点先被访问。

源码：

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

int n,m;  //结点数，边数

struct vex  //存放结点数据的结构体（用字符串数组应该也能解决这个问题）
{
    char name[5];  //结点的值
};

void dfs(int x,stack<int> e[],int visit[],vex v[])  //深搜算法
{
    if(visit[x]==1)  //如果访问过了，就不再继续访问了
        return;
    cout<<v[x].name<<' ';  //没访问就把他输出
    visit[x]=1;  //标记为已访问
    int size=e[x].size();  //求这个结点的边数（就是栈里存了多少个数据）
    for(int i=0;i<size;i++)  //对每条边的另一头的结点进行深搜遍历
    {
        int t=e[x].top();  //取栈顶元素
        e[x].pop();  //弹出栈顶元素
        if(visit[t]==0)  //如果这个元素没被访问（这个判断语句不写应该也没问题，因为递归的时候也会判断）
        {
            dfs(t,e,visit,v);  //没访问就深搜它
        }
    }
}

int main()
{
    int type;  //有向图:0,有向网:1,无向图:2,无向网:3
    cin>>type;
    cin>>n>>m;
    stack<int> e[n+1];  //二维动态栈结构
    vex v[n+1];  //数据结点值数组（字符串，小于3个字符）
    int visit[n+1]={0};  //访问标记数组，没访问就是0，访问后变1
    for(int i=1;i<=n;i++)  //读结点的值
        scanf("%s",v[i].name);
    char a[5],b[5];  //用于读每条边的两个顶点值的变量
    int w;  //边的权值
    for(int i=0;i<m;i++)  //读m条边
    {
        if(type==0||type==2)  //如果是图，不用读权值
            scanf("%s%s",a,b);
        else  //如果是网，要读权值w
            scanf("%s%s%d",a,b,&w);
        int x=-1,y=-1;  //在v数组（存放着结点的值的数组）找到对应的下标x，y
        for(int j=1;j<=n;j++)
        {
            if(strcmp(v[j].name,a)==0)  //找到当前边的顶点a在v数组的下标
                x=j;
            else if(strcmp(v[j].name,b)==0)  //找到当前边的顶点b在v数组的下标
                y=j;
            if(x!=-1&&y!=-1)  //如果都找到，就直接退出循环
                break;
        }
        if(type<=1)  //如果是有向的，就只存一个方向的数据
            e[x].push(y);  //栈结构存储
        else  //如果是无向的，则两头都存
        {
            e[x].push(y);  //栈结构存储
            e[y].push(x);  //栈结构存储
        }
    }
    for(int i=1;i<=n;i++)  //对每个结点进行深搜
    {
        dfs(i,e,visit,v);  //深搜算法（参数多是因为没有写全局变量）
    }
    return 0;
}