邻接表：深度优先遍历和广度优先遍历

9天没有摸C语言，手很生啊！

唉，考试终于结束了，就剩三门了。

算法、数据结构太重要了，不要忽视啊！

#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
int v[MAXSIZE];//标志位，判断该结点有没有被访问

typedef struct ArcNode //定义表节点
{
    int adjvex;
    struct ArcNode *next;
}ArcNode;

typedef struct VNode //定义头结点
{
    int data;
    ArcNode *firstarc;
}VNode,AdjList[MAXSIZE];

typedef struct //定义图的整体数据结构
{
    int vexnum,arcnum;//边数、弧数
    AdjList vertices;
}ALGraph;

void Init(ALGraph &G)//初始化无向图
{
    int i,n,m,a,b;
    ArcNode *s;
    cin>>n>>m;
    G.arcnum=m;
    G.vexnum=n;
    for(i=1;i<=G.vexnum;i++)//初始化
    {
        G.vertices[i].firstarc=NULL;//一开始都指向NULL
        G.vertices[i].data=i;//初始化节点编号从1~n
    }
    for(i=0;i<G.arcnum;i++)
    {
        cin>>a>>b;
        /*a指向b*/
        s=new ArcNode[sizeof(ArcNode)];
        s->adjvex=b;
        s->next=G.vertices[a].firstarc;
        G.vertices[a].firstarc=s;
        /*b指向a*/
        s=new ArcNode[sizeof(ArcNode)];
        s->adjvex=a;
        s->next=G.vertices[b].firstarc;
        G.vertices[b].firstarc=s;
    }
}

int FirstAdjVex(ALGraph G,int k)//返回图G中与k相邻且未被访问过的点的编号，如果不存在这样的点返回-1
{
    ArcNode *s;
    s=G.vertices[k].firstarc;
    if(!s)
        return -1;
    while(s&&v[s->adjvex])//如果不空又访问过，就看下一个
        s=s->next;
    if(s)//不空说明找到了
        return s->adjvex;
    else//否则返回-1
        return -1;
}

int NextAdjVex(ALGraph G,int k,int w)//返回图G中与k相邻、除了编号是w之外的未被访问过的点的编号，如果不存在这样的点返回-1
{
    ArcNode *s;
    s=G.vertices[k].firstarc;
    if(!s)
        return -1;
    while(s&&(v[s->adjvex]||s->adjvex==w))//不空，并且要么是访问过，要么是w，这样的点我们统统忽略
        s=s->next;
    if(s)//不空说明找到了
        return s->adjvex;
    else//否则-1
        return -1;
}

void DFS(ALGraph G,int k)//对节点k进行深度优先遍历
{
    int w;
    v[k]=1;//进来就置1
    cout<<G.vertices[k].data<<" ";//遍历输出
    for(w=FirstAdjVex(G,k);w!=-1;w=NextAdjVex(G,k,w))//找到所有和k相邻的节点的编号，挨个深搜递归
        if(!v[w])
            DFS(G,w);
}

void DFSTraverse(ALGraph G)//对所有点进行深度优先遍历
{
    int i;
    memset(v,0,sizeof(v));
    for(i=1;i<=G.vexnum;i++)
        if(!v[i])
            DFS(G,i);
}

void BFS(ALGraph G)//广度优先遍历
{
    int i,k,w;
    queue<int> q;//定义一个队列，存的是节点号，不是指针！
    memset(v,0,sizeof(v));//因为之前深搜过，这里重新置0一下
    for(i=1;i<=G.vexnum;i++)//依次对每个顶点进行考察
        if(!v[i])//只要不空
        {
            v[i]=1;//只要不空，进来第一件事就是置1
            cout<<G.vertices[i].data<<" ";//置1之后马上输出
            q.push(G.vertices[i].data);//输出完了之后就入队
            while(!q.empty())//只要队列不空
            {
                k=q.front();//取队首元素
                q.pop();//然后队首出队
                for(w=FirstAdjVex(G,k);w!=-1;w=NextAdjVex(G,k,w))//将所有和队首邻接的顶点依次入队，入一个，输出一个，别忘了还要置1哟~
                    if(!v[w])
                    {
                        v[w]=1;
                        cout<<G.vertices[w].data<<" ";
                        q.push(w);
                    }
            }
        }
}

int main()
{
    ALGraph G;
    Init(G);
    cout<<"DFS:";
    DFSTraverse(G);
    cout<<endl;
    cout<<"BFS:";
    BFS(G);
}