基于c++的图的基本功能实现

Graph.hpp

#ifndef _GRAPH_HPP
#define _GRAPH_HPP
#include <iostream>
#include <cstring>
#include "Queue.hpp"
using namespace std;

#define MAXY 128
#define INF 32767 //定义无穷大

typedef int InfoType;//头端点的值类型
typedef int dataType;//对端点的值类型统一化

typedef struct ANode
{     dataType adjvex;     struct ANode *nextarc;     int weight;
}ArcNode;//邻接点的定义
typedef struct Vnode
{     InfoType info;     ArcNode *firstarc;
}VNode;//顶点的定义
typedef struct
{     VNode adjlist[MAXY];     int n,e;
}AdjGraph;//定义图的完整的邻接表
class Graph//定义一个图的类
{
public:     Graph(int A[MAXY][MAXY], int n, int e);//有参构造     ~Graph();//析构函数     void show();//打印图的内容     void DFS(int v);//对固定的端点进行深度优先遍历     void DFS();//对图的端点进行深度优先遍历     void BFS(int v);//对固定的端点进行广度优先遍历     void BFS();//对图的端点进行广度优先遍历     bool connext();//判断图的连通性     void ExistPath(int u, int v, bool &has);//判断图的u到v的连通性
private:     AdjGraph *G;
};
#endif

Graph.cpp

#include "Graph.hpp"

Graph::Graph(int A[MAXY][MAXY], int n, int e){
	ArcNode *p;
	G = (AdjGraph *)malloc(sizeof(AdjGraph));
	for(int i = 0; i < n; i++){
		G->adjlist[i].firstarc = NULL;
	}
	for (int i = 0; i < n; ++i)
	{
		for(int j = n - 1; j >= 0; j--)
		{
			if(A[i][j] != 0 && A[i][j] != INF)
			{
				p = (ArcNode *)malloc(sizeof(ArcNode));
				p->adjvex = j;
				p->weight = A[i][j];
				p->nextarc = G -> adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G -> n = n;
	G -> e = e;
}

Graph::~Graph(){
	ArcNode *pre, *p;
	for (int i = 0; i < G->n; ++i)
	{
		pre = G->adjlist[i].firstarc;
		if(pre!=NULL){
			p = pre -> nextarc;
			while(p != NULL){
				free(pre);
				pre = p;
				p = p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
}

void Graph::show(){
	ArcNode *p;
	for (int i = 0; i < G->n; ++i)
	{
		p = G->adjlist[i].firstarc;
		char ch = i + 65;
		cout << ch << ":";
		while(p != NULL){
			cout << p->adjvex << " [" << p->weight << "] " << "->";
			p = p->nextarc;
		}
		cout<< " ^"<<endl;
	}
}
int visited[MAXY] = {0};

void Graph::DFS(int v)
{
	ArcNode *p;
	visited[v] = 1;
	cout << v << ' ';
	p = G->adjlist[v].firstarc;
	while(p != NULL)
	{
		if(visited[p->adjvex] == 0){
			DFS(p->adjvex);
		}
		p = p->nextarc;
	}
}
void Graph::DFS()
{
	memset(visited, 0, sizeof(visited));
	for(int i = 0; i < G->n; ++i){
		if(visited[i] == 0){
			DFS(i);
		}
	}
}
void Graph::BFS(int v)
{
	memset(visited, 0, sizeof(visited));
	int w;
	ArcNode *p;
	queue q;
	cout << v <<' ';
	visited[v] = 1;
	q.en(v);
	while(q.empty() == 0)
	{
		w = q.de();
		p = G->adjlist[w].firstarc;
		while(p != NULL){
			if(visited[p->adjvex] == 0){
				cout << p->adjvex <<' ';
				visited[p->adjvex] = 1;
				q.en(p->adjvex);
			}
			p = p->nextarc;
		}
	}
	cout << endl;
}
void Graph::BFS()
{
	memset(visited, 0, sizeof(visited));
	for(int i = 0; i < G->n; ++i){
		if(visited[i] == 0){
			BFS(i);
		}
	}
}
bool Graph::connext()
{
	memset(visited, 0, sizeof(visited));
	DFS(0);
	cout << endl;
	for (int i = 0; i < G->n; ++i)
	{
		if(visited[i] == 0){
			return false;
		}
	}
	return true;
}
void Graph::ExistPath(int u, int v, bool &has)
{
	visited[u] = 1;
	if(v == u){
		has = true;
		return ;
	}
	ArcNode *p = G->adjlist[u].firstarc;
	while(p != NULL){
		int w = p->adjvex;
		if(visited[w] == 0)
			ExistPath(w, v, has);
		p = p->nextarc;
	}
}

Queue.hpp

#ifndef _QUEUE_HPP
#define _QUEUE_HPP 
#include <iostream>
typedef int data_t;
typedef struct node{
	data_t data;
	struct node *next;
}linkqueue;//链式队列的定义
class queue
{
public:
	queue();//构造函数
	~queue();//析构函数
	int empty();//判断空
	void en(int v);//入队
	int de();//出队
private:
	linkqueue *qhead;
};
#endif

Queue.cpp

#include "Queue.hpp"

queue::queue()
{
	qhead = new linkqueue;
	qhead->data = -1;
	qhead->next = NULL;
}
queue::~queue()
{
	linkqueue *q = qhead->next;
	while(q != NULL){
		qhead->next = q->next;
		free(q);
		q = qhead->next;
	}
}
int queue::empty()
{
	if(qhead->next != NULL){
		return 0;
	}
	return 1;
}
void queue::en(int v)
{
	linkqueue *H = new linkqueue;
	H->data = v;
	H->next = NULL;
	linkqueue *q = qhead;
	while(q->next != NULL){
		q = q -> next;
	}
	q->next = H;
}
int queue::de()
{
	int temp;
	linkqueue *q = qhead->next;
	qhead->next = q->next;
	temp = q->data;
	free(q);
	return temp;
}

main.cpp

#include "Graph.hpp"

int main(int argc, char const *argv[])
{
	int a[MAXY][MAXY] = {{0,INF,10,INF,31},
						 {INF,0,INF,15,INF},\
						 {10,INF,0,INF,51},\
						 {INF,15,INF,0,INF},\
						 {31,INF,51,INF,0}};
	Graph graph(a,5,4);
	graph.show();
	graph.DFS();
	cout << endl;
	graph.show();
	graph.BFS();
	cout << graph.connext() << endl;
	bool flag = false;
	graph.ExistPath(0,4,flag);
	cout << flag << endl;
	return 0;
}

Makefile

OBJ = main.o Graph.o Queue.o
CC = g++
CFLAGS = -Wall -g -O
CTAG = app

$(CTAG):$(OBJ)
	$(CC) $^ -o $@

main.o:main.cpp
Graph.o:Graph.cpp
Queue.o:Queue.cpp

clean:
	rm $(OBJ) $(CTAG)