圖的鄰接表存儲；深度優先周遊；借助隊列的廣度優先周遊實作；

ALGraph.h

# ifndef _ALGRAPH_
# define _ALGRAPH_

# include <iostream>
using namespace std;

# define MaxVertexNum 256
typedef int InfoType;
typedef char VertexType;

typedef struct EdgeNode
{
	int adjvertex;
	InfoType info;
	struct EdgeNode * next;
}EdgeNode;

typedef struct VertexNode
{
	VertexType vertex;
	EdgeNode * firstedge;
}VertexNode;

typedef struct
{
	VertexNode adjlist[MaxVertexNum];
	int vertexNum;
	int edgeNum;
}AlGraph, * PALGraph;

PALGraph CreateGraph(void);

void DFS(PALGraph g, int i);
void DFSTraversal(PALGraph g);

void BFSTraversal(PALGraph g, int i);

# endif
           

SeqQueue.h

# ifndef _SEQQUEUE_
# define _SEQQUEUE_

# include <iostream>
using namespace std;

typedef int DataType;
# define MAXSIZE 256

typedef struct
{
	DataType data[MAXSIZE];
	int front;
	int rear;
}SeqQueue, * PSeqQueue;

PSeqQueue InitSeqQueue(void);
void DestroySeqQueue(PSeqQueue * pQ);
bool EmptySeqQueue(PSeqQueue Q);
bool FullSeqQueue(PSeqQueue Q);

bool InSeqQueue(PSeqQueue Q, DataType x);
bool OutSeqQueue(PSeqQueue Q, DataType * val);
bool FrontSeqQueue(PSeqQueue Q, DataType * val);

# endif
           

ALGraph.cpp

# include "ALGraph.h"
# include "SeqQueue.h"

bool visited[MaxVertexNum] = { 0 };

PALGraph CreateGraph(void)
{
	PALGraph g = (PALGraph)malloc(sizeof(AlGraph));

	if (NULL != g)
	{
		memset(g, 0, sizeof(AlGraph));
		g->vertexNum = 0;
		g->edgeNum = 0;

		cout << "Please input vertecNum and edgeNum: " << endl;
		cin >> g->vertexNum >> g->edgeNum;

		for (int i = 0; i < g->vertexNum; i++)
		{
			cout << "Please input the element value: " << endl;
			cin >> g->adjlist[i].vertex;
			g->adjlist[i].firstedge = NULL;
		}

		int i = 0;
		int j = 0;
		EdgeNode * p = NULL;
		for (int k = 0; k < g->edgeNum; k++)
		{
			cout << "please input two index: " << endl;
			cin >> i >> j;

			p = (EdgeNode *)malloc(sizeof(EdgeNode));
			if (NULL == p)
			{
				cout << "Memory allocate is error! " << endl;
				system("pause");
				exit(0);
			}
			p->adjvertex = j;
			p->info = 0;
			
			p->next = g->adjlist[i].firstedge; 
			g->adjlist[i].firstedge = p;
		}

		return g;
	}
	else
	{
		cout << "Memory allocate is error! " << endl;
		system("pause");
		return 0;
	}
}

void DFS(PALGraph g, int i)
{
	EdgeNode * p = NULL;
	int j = 0;

	cout << g->adjlist[i].vertex << endl;
	visited[i] = true;

	for (p = g->adjlist[i].firstedge; p != NULL; p = p->next)
	{
		j = p->adjvertex;
		if (!visited[j])
		{
			DFS(g, j);
		}
	}
}

void DFSTraversal(PALGraph g)
{
	for (int i = 0; i < g->vertexNum; i++)
	{
		visited[i] = false;
	}

	for (int i = 0; i < g->vertexNum; i++)
	{
		if (!visited[i])
		{
			DFS(g, i);
		}
	}
}

void BFSTraversal(PALGraph g, int i)
{
	EdgeNode * p = NULL;
	int j = 0;
	PSeqQueue q = InitSeqQueue();

	cout << g->adjlist[i].vertex << endl;
	visited[i] = true;
	InSeqQueue(q, i);

	while (!EmptySeqQueue(q))
	{
		OutSeqQueue(q, &i);

		for (p = g->adjlist[i].firstedge; p != NULL; p = p->next)
		{
			j = p->adjvertex;

			if (!visited[j])
			{
				cout << g->adjlist[j].vertex << endl;
				visited[j] = true;
				InSeqQueue(q, j);
			}
		}
	}
}
           

SeqQueue.cpp

# include "SeqQueue.h"

PSeqQueue InitSeqQueue(void)
{
	PSeqQueue Q = (PSeqQueue)malloc(sizeof(SeqQueue));

	if (NULL != Q)
	{
		Q->front = 0;
		Q->rear = 0;

		return Q;
	}
	else
	{
		cout << "Memory allocate is error! " << endl;
		system("pause");
		exit(0);
	}
}

void DestroySeqQueue(PSeqQueue * pQ)
{
	PSeqQueue Q = *pQ;

	if (NULL != Q)
	{
		free(Q);
		Q = NULL;
	}

	*pQ = NULL;
	return;
}

bool EmptySeqQueue(PSeqQueue Q)
{
	if (Q->front == Q->rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool FullSeqQueue(PSeqQueue Q)
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool InSeqQueue(PSeqQueue Q, DataType x)
{
	if (FullSeqQueue(Q))
	{
		return false;
	}
	else
	{
		Q->rear = (Q->rear + 1) % MAXSIZE;
		Q->data[Q->rear] = x;
		
		return true;
	}
}

bool OutSeqQueue(PSeqQueue Q, DataType * val)
{
	if (EmptySeqQueue(Q))
	{
		return false;
	}
	else
	{
		Q->front = (Q->front + 1) % MAXSIZE;
		*val = Q->data[Q->front];

		return true;
	}
}

bool FrontSeqQueue(PSeqQueue Q, DataType * val)
{
	if (EmptySeqQueue(Q))
	{
		return false;
	}
	else
	{
		*val = Q->data[(Q->front + 1) % MAXSIZE];

		return true;
	}
}
           

Main.cpp

# include "ALGraph.h"

int main(int argc, char ** argv)
{
	PALGraph g = CreateGraph();

	//EdgeNode * p = NULL;
	//for (int i = 0; i < g->vertexNum; i++)
	//{
	//	p = g->adjlist[i].firstedge; 

	//	while (NULL != p)
	//	{
	//		cout << g->adjlist[p->adjvertex].vertex << endl;
	//		p = p->next;
	//	}

	//	cout << endl;
	//}

	cout << "--------------------------------------------" << endl;
	
	BFSTraversal(g, 0);

	system("pause");
	return 0;
}