邻接表广度深度遍历

#include<iostream>
#include<queue>
using namespace std;
const int MaxVertexNum = 100; 
bool visited[MaxVertexNum];
int relationNonDir[][2] = {{0,1},{0,2},{1,2},{1,3},{2,6},{2,5},{3,5},{3,4},{4,5}};////无向图

class EdgeNode{
public:
    int val;
    int weight;
    EdgeNode* next;
    EdgeNode():val(0),next(NULL),weight(1){}
    EdgeNode(int v):next(NULL),val(v),weight(1){}
    EdgeNode(int val,int wei):next(NULL),val(val),weight(wei){}
};

class VertexNode
{
public:
    int val;
    EdgeNode* firstedge;
    VertexNode():val(0),firstedge(NULL){}
};

class GraphLL{
public:
    int Num;
    VertexNode* v;
    GraphLL(const int n):Num(n)
    {
        v = new VertexNode[n];
        for(int i = 0;i< n;i++)
        {
            (v+i)->val = i;
        }
    }
};

GraphLL* createNondirectional(int n)
{
    GraphLL * g = new GraphLL(n);
//    int Num = sizeof(relationNonDir)/(sizeof(relationNonDir[0])*sizeof(relationNonDir[0][0]));
    int Num = 9;
    for(int i = 0;i< Num;i++)
    {
        VertexNode* vi = g->v + relationNonDir[i][0];
        EdgeNode* vd = new EdgeNode(relationNonDir[i][1]);
        vd->next = vi->firstedge;
        vi->firstedge = vd;

        vi = g->v + relationNonDir[i][1];
        vd = new EdgeNode(relationNonDir[i][0]);
        vd->next = vi->firstedge;
        vi->firstedge = vd;
    }

    return g;
}

void DFSD(GraphLL* g,int i)
{
    cout<<(g->v + i)->val<<" ";
    visited[i] = true;
    EdgeNode* p = (g->v + i)->firstedge;
    while(p)
    {
        if(!visited[p->val])
         DFSD(g,p->val);
       p = p->next;
    }

}
void DFS(GraphLL* g)
{
    for(int i = 0;i< g->Num;i++)
        visited[i] = false;
    for(int i = 0;i< g->Num;i++)
        if(!visited[i]) 
            DFSD(g,i);
}

void BFS(GraphLL* g)
{
   for(int i = 0;i< g->Num;i++)
        visited[i] = false;

   queue<int> q;
   q.push(g->v->val);
   visited[g->v->val] = true;
   while(!q.empty())
   {
       int temp = q.front();
       cout<<temp<<" ";
       q.pop();
       EdgeNode* p = (g->v + temp)->firstedge;
       while(p)
       {
           if(false == visited[p->val])
           {
               q.push(p->val);
               visited[p->val] = true;
           }
           p = p->next;////注意，这里面没有else 
       }
   }
}

void displayLinkList(GraphLL* g)
{
    for(int i = 0;i< g->Num;i++)
    {
        cout<<(g->v + i)->val;
        cout<<": ";
        EdgeNode* p = (g->v + i)->firstedge;
        while(p)
        {
            cout<<p->val<<" ";
            p = p->next;
        }
        cout<<endl;
    }
}
int main()
{
 GraphLL* g =  createNondirectional(7);
 displayLinkList(g);
 DFS(g); cout<<endl;
 BFS(g);
}