数据结构笔记（图：邻接表）

一、邻接表存储的基本思想：
对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表）
所有边表的头指针和存储顶点信息的一维数组构成了顶点表
邻接表有两种结点结构：顶点表结点和边表结点

vertex：数据域，存放顶点信息。
firstedge：指针域，指向边表中第一个结点。
adjvex：邻接点域，边的终点在顶点表中的下标。
next：指针域，指向边表中的下一个结点。
二、定义邻接表的结点

struct ArcNode{   
      int adjvex; 
      ArcNode *next;
};

template <class T>
struct VertexNode{
      T vertex;
      ArcNode *firstedge;
};

三、邻接表存储有向图的类

const int MaxSize=10;    //图的最大顶点数
template <class T>
class ALGraph
{    
   public:
       ALGraph(T a[ ], int n, int e);   
       ~ALGraph;    
       void DFSTraverse(int v);      
       void BFSTraverse(int v);      
   ………
  private:
       VertexNode adjlist[MaxSize];   
       int vertexNum, arcNum;       
};

四、邻接表中图的基本操作——构造函数
（一）基本思想

1. 确定图的顶点个数和边的个数；
2. 输入顶点信息，初始化该顶点的边表；
3. 依次输入边的信息并存储在边表中；
   3.1 输入边所依附的两个顶点的序号i和j；
   3.2 生成邻接点序号为j的边表结点s；
   3.3 将结点s插入到第i个边表的头部；

template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{   
   vertexNum=n; arcNum=e; 
   for (i=0; i<vertexNum; i++)   
   {
      adjlist[i].vertex=a[i];
      adjlist[i].firstedge=NULL;      
   } 
   for (k=0; k<arcNum; k++)   
    {
        cin>>i>>j;    
        s=new ArcNode; s->adjvex=j;  	        
        s->next=adjlist[i].firstedge;    
        adjlist[i].firstedge=s;
    }
}

五、邻接表中图的基本操作——深度优先遍历

template <class T>
void ALGraph::DFSTraverse(int v){        
    cout<<adjlist[v].vertex;  visited[v]=1;
    p=adjlist[v].firstedge;    
    while (p!=NULL)     {
        j=p->adjvex;
        if (visited[j]==0) DFSTraverse(j);
    p=p->next;           
    }
}

六、邻接表中图的基本操作——广度优先遍历

template <class T>
void ALGraph::BFSTraverse(int v){
   front=rear=-1;   
   cout<<adjlist[v].vertex;    visited[v]=1;   Q[++rear]=v;   
   while (front!=rear)  {
       v=Q[++front];    p=adjlist[v].firstedge;    
       while (p!=NULL)  {
            j= p->adjvex;
            if (visited[j]==0) {
                cout<<adjlist[j].vertex;  visited[j]=1; Q[++rear]=j;
            }
            p=p->next;
       }
    }
}