欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的邻接表存储;深度优先遍历;借助队列的广度优先遍历实现;

程序员文章站 2022-05-22 09:58:02
...

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;
}