邻接表的C++模板机制

建立ALGraph类
ALGraph.h
#ifndef ALGRAPH_H
#define ALGRAPH_H

int visited[100];
const int MaxSize=10;
struct ArcNode      //定义边表节点
{
    int adjvex;     //临界点域
    ArcNode * next; //指针域
};
template<class DataType>
struct VertexNode   //定义定点表节点
{
    DataType vertex;    //数据项
    int in;             //入度
    ArcNode * firstedge;//
};

template<class DataType>
class ALGraph
{
public:
    ALGraph(DataType a[],int n,int e);  //构造函数,建立一个有n个顶点e条边的图
    //~ALGraph();      //析构函数,释放邻接表中各边表节点的存储空间
    void DFSTraverse(int v);        //深度优先遍历
    void BFSTraverse(int v);        //广度优先遍历
    void TopSort(ALGraph G);        //拓扑排序

private:
    VertexNode<DataType> adjlist[MaxSize];//存放顶点表的数组
    int VertexNum,arcNum;                 //图的顶点数和边数
};

#endif // ALGRAPH_H

再写ALGraph.cpp
#include "ALGraph.h"
#include<iostream>
#include<cstring>
using namespace std;
int i,j,k;  //循环变量

template<class DataType>
ALGraph<DataType>::ALGraph(DataType a[],int n,int e)
{
    VertexNum=n;
    arcNum=e;
    for(i=0; i<VertexNum; i++)
    {
        adjlist[i].vertex=a[i];
        adjlist[i].firstedge=NULL;
        adjlist[i].in=0;
    }
    ArcNode *s;
    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 DataType>
void ALGraph<DataType>::DFSTraverse(int v)
{
    cout<<adjlist[v].vertex;
    visited[v]=1;
    ArcNode *p=adjlist[v].firstedge;
    while(p!=NULL)
    {
        j=p->adjvex;
        if(visited[j]==0)
            DFSTraverse(j);
        p=p->next;
    }
}

template<class DataType>
void ALGraph<DataType>::BFSTraverse(int v)
{
    int Q[100]= {0};
    int front,rear;
    front=rear=-1;
    cout<<adjlist[v].vertex;
    visited[v]=1;
    Q[++rear]=v;
    while(front!=rear)
    {
        v=Q[++front];
        ArcNode *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;
        }
    }

}

template<class DataType>
void ALGraph<DataType>::TopSort(ALGraph G)
{
    int S[100]= {0};
    int top=-1;
    int count=0;
    int j;
    for(i=0; i<G.VertexNum; i++)
        if(G.adjlist[i].in==0) S[++top]=i;
    while(top!=-1)
    {
        j=S[top--];
        cout<<G.adjlist[j].vertex;
        count++;
        ArcNode *p=G.adjlist[j].firstedge;
        while(p!=NULL)
        {
            k=p->adjvex;
            G.adjlist[k].in--;
            if(G.adjlist[k].in==0) S[++top]=k;
            p=p->next;
        }
    }
    if(count<G.VertexNum) cout<<"有回路";

}


int main()
{
    char a[9]= {'A','B','C','D','E','F','G','H','I'};
    ALGraph<char> G(a,9,11);
    memset(visited,0,sizeof(visited));
    G.BFSTraverse(0);
    cout<<endl;

    memset(visited,0,sizeof(visited));
    for(int i=0; i<9; i++)
        if(visited[i]==0)
            G.DFSTraverse(i);
    cout<<endl;

    G.TopSort(G);
    return 0;
}
/*测试数据：
0 1
0 2
0 3
1 4
2 4
3 5
4 6
4 7
5 7
6 8
7 8
*/