邻接表形式的图的建立与dfs遍历

#include <vector> 
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 10000;
#define N 6
bool visited[maxn];
struct Node {
	int vertex;//弧头或者边所连的点
	Node* pNext;//下一条依附于该点的弧或边
};
struct Head {
	char data;
	Node* first;//依附于该顶点的第一条边
};
typedef Head* Graph;
Graph createGraph()
{
	Graph graph = new Head[N];
	int i = 0;
	for (int i = 0; i < N; i++)
		graph[i].data = 'A' + i;
	Node* p00 = new Node;
	Node* p01 = new Node;
	Node* p10 = new Node;
	Node *p11 = new Node;
	Node* p12 = new Node;
	Node* p20 = new Node;
	Node* p21 = new Node;
 	Node* p30 = new Node;
	Node* p31 = new Node;
	Node* p40 = new Node;
	Node* p41 = new Node;
	Node* p42 = new Node;
	Node* p50 = new Node;
	Node* p51 = new Node;
	p00->vertex = 1;
	p00->pNext = p01;
	p01->vertex = 2;
	p01->pNext = NULL;
	p10->vertex = 0;
	p10->pNext = p11;
	p11->vertex = 3;
	p11->pNext = p12;
	p12->vertex = 4;
	p12->pNext = NULL;
	p20->vertex = 0;
	p20->pNext = p21;
	p21->vertex = 5;
	p21->pNext = NULL;
	p30->vertex = 1;
	p30->pNext = p31;
	p31->vertex = 4;
	p31->pNext = NULL;
	p40->vertex = 1;
	p40->pNext = p41;
	p41->vertex = 3;
	p41->pNext = p42;
	p42->vertex = 5;
	p42->pNext = NULL;
	p50->vertex = 2;
	p50->pNext = p51;
	p51->vertex = 4;
	p51->pNext = NULL;
	graph[0].first = p00;
	graph[1].first = p10;
	graph[2].first = p20;
	graph[3].first = p30;
	graph[4].first = p40;
	graph[5].first = p50;
	return graph;
}
int firstVertex(Graph Gp, int pos) {
	if (Gp[pos].first)
		return Gp[pos].first->vertex;
	else
		return -1;
}
int nextVertex(Graph Gp, int pos,int cur) {
	Node* p = Gp[pos].first;
	while (p->vertex != cur)
		p = p->pNext;
	if (p->pNext)
		return p->pNext->vertex;
	else
		return -1;
}
void DFS(Graph Gp, int begin) {
		cout << Gp[begin].data;
		visited[begin] = 1;
	    int i;
	i = firstVertex(Gp, begin);
	if (i >= 0)
	{
		if (!visited[i])
			DFS(Gp, i);
		//visited[i] = 0;
	}
	while (nextVertex(Gp, begin, i) != -1)
	{
		i = nextVertex(Gp, begin, i);
		if (i >= 0)
		{
			if (!visited[i])
				DFS(Gp, i);
			//visited[i] = 0;
		}
	}
 	return;
}
void DFS_traverse(Graph Gp, int begin)
{
	int i;
	for (i = 0; i < N; i++)
		visited[i] = 0;
	DFS(Gp, begin);
	for (i = 0; i < N; i++)
	{
		if (!visited[i])
			DFS(Gp, i);
	}
}
queue<int> Q;
void BFS(Graph Gp, int begin)
{
	cout << Gp[begin].data;
	visited[begin] = 1;
	int i, pVertex;
	Q.push(begin);
	while (!Q.empty())
	{
		pVertex = Q.front();
		Q.pop();
		for (i = firstVertex(Gp, pVertex); i >= 0; i = nextVertex(Gp, pVertex, i))
		{
			if (!visited[i])
			{
				cout << Gp[i].data;
				visited[i] = 1;
				Q.push(i);
			}
		}
	}
}

int main()
{
	Graph Gp = createGraph();
	DFS(Gp, 0);
	cout << endl;
	memset(visited, 0, maxn);
	BFS(Gp, 0);
}