有向图的邻接表(Adjacency List)

#ifndef __LISTNODE_H__
#define __LISTNODE_H__
class EdgeNode
{
public:
  int adjVex;
  EdgeNode * next;
};
template <class T>
class VertexNode
{
public:
  T vertex;
  EdgeNode * firstEdgeNode;
};
#endif

#ifndef __ALGRAPH_H__
#define __ALGRAPH_H__
#include "listNode.h"
const int MaxSize = 10;
template <class T>
class ALGraph
{
public:
  ALGraph(T _adjList[], int _vertexNum, int _edgeNum);
  ~ALGraph();
public:
  void DFSTraverse(int _vertex);
  void BFSTraverse(int _vertex);
private:
  VertexNode<T> adjList[MaxSize];
  int vertexNum, edgeNum;
};
#endif

#include <iostream>
#include "listNode.h"
#include "ALGraph.h"
using namespace std;
template <class T>
ALGraph<T>::ALGraph(T _adjList[], int _vertexNum, int _edgeNum)
{
  vertexNum = _vertexNum;
  edgeNum = _edgeNum;
  for (int i = 0; i < vertexNum; i++)
  { 
  adjList[i].vertex = _adjList[i];
  adjList[i].firstEdgeNode = nullptr;
  }
  for (int i = 0; i < edgeNum; i++)
  {
  int vertex1, vertex2;
  cin >> vertex1 >> vertex2;
  EdgeNode * tempEdgeNode = new EdgeNode;
  tempEdgeNode->adjVex = vertex2;
  tempEdgeNode->next = adjList[vertex1].firstEdgeNode;
  adjList[vertex1].firstEdgeNode = tempEdgeNode;
  }
}
template <class T>
ALGraph<T>::~ALGraph()
{}
template <class T>
void ALGraph<T>::DFSTraverse(int _vertex)
{
  int tempVertex = 0;
  static int * visitedDFS = new int[vertexNum];
  cout << adjList[_vertex].vertex;
  visitedDFS[_vertex] = 1;
  EdgeNode * tempFirstEdgeNode = adjList[_vertex].firstEdgeNode;
  while (tempFirstEdgeNode != nullptr)
  {
  tempVertex = tempFirstEdgeNode->adjVex;
  if (visitedDFS[tempVertex] != 1)
    DFSTraverse(tempVertex);
  tempFirstEdgeNode = tempFirstEdgeNode->next;
  }
}
template <class T>
void ALGraph<T>::BFSTraverse(int _vertex)
{
  int front = -1, rear = -1;
  int *visitedBFS = new int[vertexNum];
  int *queue = new int[vertexNum];
  cout << adjList[_vertex].vertex;
  visitedBFS[_vertex] = 1;
  queue[++rear] = _vertex;
  while (front != rear)
  {
  _vertex = queue[++front];
  EdgeNode * tempFirstEdgeNode = adjList[_vertex].firstEdgeNode;
  while (tempFirstEdgeNode != nullptr)
  {
    if (visitedBFS[tempFirstEdgeNode->adjVex] != 1)
    {
    cout << adjList[tempFirstEdgeNode->adjVex].vertex;
    visitedBFS[tempFirstEdgeNode->adjVex] = 1;
    queue[++rear] = tempFirstEdgeNode->adjVex;
    }
    tempFirstEdgeNode = tempFirstEdgeNode->next;
  }
  }
}

#include <iostream>
#include "ALGraph.h"
#include "ALGraph.cpp"
using namespace std;
int main()
{
  int arr[] = { 0, 1, 2, 3 };
  ALGraph<int> G(arr, 4, 4);
  G.BFSTraverse(0);
  cout << endl;
  G.DFSTraverse(0);
  cout << endl;
  return 0;
}

//输入
0 1
0 2
2 3
3 0
//输出
0213
0231