MyException - 我的异常网
当前位置:我的异常网» 编程 » 数据结构:图的实现-邻接表

数据结构:图的实现-邻接表

www.MyException.Cn  网友分享于:2014-08-01  浏览:0次
数据结构:图的实现--邻接表

                          图的实现:邻接表

当图中的边数较少时,用邻接表来实现图结构,则会浪费很多内存空间。因此,考虑另一种实现图结构的方法:邻接表。在邻接表中主要有两种节点结构体:

顶点节点


边节点


直接看代码

类定义

#include<iostream>
#include<iomanip>
using namespace std;
//最大权值
#define MAXWEIGHT 100
//边节点
typedef struct edgenode_tag
{
	int adjvex;  //邻接点
	int weight;  //边的权值
	struct edgenode_tag *next;
}EdgeNode;
//顶点节点
typedef struct vertex_tag
{
	int vertex;   //顶点
	EdgeNode *next;
}Vertex;
class Graph
{
private:
	//是否带权
	bool isWeighted;
	//是否有向
	bool isDirected;
	//顶点数
	int numV;
	//边数
	int numE;
	//邻接表
	Vertex *adjList;
public:
	/*
	构造方法
	numV是顶点数,isWeighted是否带权值,isDirected是否有方向
	*/
	Graph(int numV, bool isWeighted = false, bool isDirected = false);
	//建图
	void createGraph();
	//析构方法
	~Graph();
	//获取顶点数
	int getVerNums()
	{return numV;}
	//获取边数
	int getEdgeNums()
	{return numE;}
	//插入边
	void insertEdge(int tail, int head, int weight = 1);
	void insertedge(int tail, int head, int weight);
	//设置指定边的权值
	void setEdgeWeight(int tail, int head, int weight);
	//打印邻接表
	void printAdjacentList();
	//检查输入
	bool check(int tail, int head, int weight = 1);
};

类实现

/*
构造方法
numV是顶点数,isWeighted是否带权值,isDirected是否有方向
*/
Graph::Graph(int numV, bool isWeighted, bool isDirected)
{
	while (numV <= 0)
	{
		cout << "输入的顶点数不正确!,重新输入 ";
		cin >> numV;
	}
	this->numV = numV;
	this->isWeighted = isWeighted;
	this->isDirected = isDirected;
	//边数初始化为0
	numE = 0;
	adjList = new Vertex[numV];  //指针数组
	for (int i = 0; i < numV; i++)
	{
		adjList[i].vertex = i;
		adjList[i].next = NULL;
	}
}
//建图
void Graph::createGraph()
{
	//用一个新的变量表示边数,numE的修改则留到insertedge()中
	int numEdge = 0;
	cout << "输入边数 ";
	while (cin >> numEdge && numEdge < 0)
		cout << "输入有误!,重新输入 ";

	int i, j, w;
	if (!isWeighted)  //无权图
	{
		cout << "输入每条边的起点和终点:\n";
		for (int k = 0; k < numEdge; k++)
		{
			cin >> i >> j;
			while (!check(i, j))
			{
				cout << "输入的边不对!重新输入\n";
				cin >> i >> j;
			}
			insertEdge(i, j);
		}
	}
	else  //有权图
	{
		cout << "输入每条边的起点、终点和权值:\n";
		for (int k = 0; k < numEdge; k++)
		{
			cin >> i >> j >> w;
			while (!check(i, j, w))
			{
				cout << "输入的边不对!重新输入\n";
				cin >> i >> j >> w;
			}
			insertEdge(i, j, w);
		}
	}
}
//析构方法
Graph::~Graph()
{
	int i;
	EdgeNode *p, *q;
	for (i = 0; i < numV; i++)
	{
		if (adjList[i].next)
		{
			p = adjList[i].next;
			while (p)
			{
				q = p->next;
				delete p;
				p = q;
			}
		}
	}
	delete[]adjList;
}
//设置指定边的权值
void Graph::setEdgeWeight(int tail, int head, int weight)
{
	if (!isWeighted)  //无权图
	{
		while (!check(tail, head))
		{
			cout << "输入的边不对!重新输入\n";
			cin >> tail >> head;
		}
		insertEdge(tail, head);
	}
	else  //有权图
	{
		while (!check(tail, head, weight))
		{
			cout << "输入的边不对!重新输入\n";
			cin >> tail >> head >> weight;
		}
		insertEdge(tail, head, weight);
	}
}
//插入边
void Graph::insertEdge(int vertex, int adjvex, int weight)
{
	insertedge(vertex, adjvex, weight);
	if (!isDirected)  //无向图
		insertedge(adjvex, vertex, weight);
}
void Graph::insertedge(int vertex, int adjvex, int weight)
{
	EdgeNode *p, *q, *r;
	p = q = r = NULL;
	if (adjList[vertex].next)   //非第一个节点
	{
		p = adjList[vertex].next;
		//移动p到合适位置
		while (p && (p->adjvex < adjvex))
		{
			q = p;
			p = p->next;
		}
		if (p && (p->adjvex == adjvex))  //修改已有边权值
			p->weight = weight;
		else
		{
			r = new EdgeNode;
			r->adjvex = adjvex;
			r->weight = weight;
			r->next = p;
			//当加入的新节点位于表的第一个位置
			if (adjList[vertex].next == p)
				adjList[vertex].next = r;
			else
				q->next = r;
			numE++;
		}
	}
	else
	{
		p = new EdgeNode;
		p->adjvex = adjvex;
		p->weight = weight;
		p->next = NULL;
		adjList[vertex].next = p;
		numE++;
	}
}
//输入检查
bool Graph::check(int tail, int head, int weight)
{
	if (tail >= 0 && tail < numV && head >= 0 && head < numV 
		&& weight > 0 && weight <= MAXWEIGHT)
		return true;
	else
		return false;
}
//打印邻接表
void Graph::printAdjacentList()
{
	int i;
	EdgeNode *edge = NULL;
	for (i = 0; i < numV; i++)
	{
		edge = adjList[i].next;
		if (edge) //为什么加一个if判断?跟后面的换行有关。若某顶点无邻接点(无边),则会空出一行
		{
			while (edge)
			{
				cout << "w(" << i << "," << edge->adjvex << ")=" << edge->weight << "  ";
				edge = edge->next;
			}
			cout << endl;
		}
	}
}
主函数

int main(void)
{
	cout << "******使用邻接表实现图结构***by David***" << endl;
	bool isDirected, isWeighted;
	int numV;
	cout << "建图" << endl;
	cout << "输入顶点数 ";
	cin >> numV;
	cout << "边是否带权值,0(不带) or 1(带) ";
	cin >> isWeighted;
	cout << "是否是有向图,0(无向) or 1(有向) ";
	cin >> isDirected;
	Graph graph(numV, isWeighted, isDirected);
	cout << "这是一个";
	isDirected ? cout << "有向、" : cout << "无向、";
	isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
	graph.createGraph();
	cout << "打印邻接表" << endl;
	graph.printAdjacentList();
	cout << endl;
	int tail, head, weight;
	cout << "修改指定边的权值" << endl;
	if (isWeighted)  //针对有权图
	{
		cout << "输入边的起点、终点和权值 ";
		cin >> tail >> head >> weight;
		graph.setEdgeWeight(tail, head, weight);
	}
	else  //针对无权图
	{
		cout << "输入边的起点、终点 ";
		cin >> tail >> head;
		graph.setEdgeWeight(tail, head, 1);
	}
	cout << "修改成功!" << endl;
	cout << "打印邻接矩阵" << endl;
	graph.printAdjacentList();
	system("pause");
	return 0;
}
运行



完整代码下载:图的实现:邻接表


转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/38323593


若有所帮助,顶一个哦!


专栏目录:数据结构与算法目录


文章评论

中美印日四国程序员比较
中美印日四国程序员比较
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
总结2014中国互联网十大段子
总结2014中国互联网十大段子
为什么程序员都是夜猫子
为什么程序员都是夜猫子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
鲜为人知的编程真相
鲜为人知的编程真相
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
那些争议最大的编程观点
那些争议最大的编程观点
 程序员的样子
程序员的样子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员的鄙视链
程序员的鄙视链
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我的丈夫是个程序员
我的丈夫是个程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
旅行,写作,编程
旅行,写作,编程
10个调试和排错的小建议
10个调试和排错的小建议
编程语言是女人
编程语言是女人
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
一个程序员的时间管理
一个程序员的时间管理
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Java程序员必看电影
Java程序员必看电影
如何成为一名黑客
如何成为一名黑客
程序员必看的十大电影
程序员必看的十大电影
漫画:程序员的工作
漫画:程序员的工作
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员和编码员之间的区别
程序员和编码员之间的区别
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有