算法与数据结构基础8：C++实现有向图邻接表存储

浏览数：15 / 时间：2015年06月08日

前面实现了链表和树，现在看看图。
链表是一对一的对应关系；
树是一对多的对应关系；
图是多对多的对应关系。

图一般有两种存储方式，邻接表和邻接矩阵。

先看邻接表。
邻接表就是将图中所有的点用一个数组存储起来，并将此作为一个链表的头，
链表中保存跟这个点相邻的点（边点），如果有权值，则在边点中增加一权值字段。

因此，有向图邻接表的空间复杂度为O(v+e)，无向图加倍。

C++实现代码如下：
// GraphList.h

#include <iostream>
#include <cstdio>

using namespace std;

// 边
struct Edge{
	int vName;
	int weight;
	struct Edge* next;
};

// 顶点(链表头)
struct Vertex{
	int vName;
	struct Edge* next;
};

// 有向图
class GraphList
{
public:
	~GraphList();

	void createGraph();
	void printGraph();

private:
	// 1. 输入定点数
	void inputVertexCount();
	// 2. 生成定点数组
	void makeVertexArray();
	// 3. 输入边数
	void inputEdgeCount();
	// 4. 输入边的起始点
	void inputEdgeInfo();
	// 5. 添加边节点至对应的链表中
	void addEdgeToList(int vFrom, int weight, int vTo);
private:
	int m_vCount;
	int m_eCount;
	Vertex* m_vVertex;
};

GraphList::~GraphList(){
	for (int i = 0; i < m_vCount; ++i){
		Edge* tmp = m_vVertex[i].next;
		Edge* edge = NULL;
		while(tmp){
			edge = tmp;
			tmp = tmp->next;
			delete edge;
			edge = NULL;
		}
	}
	delete[] m_vVertex;
}

void GraphList::inputVertexCount()
{
	cout << "please input count of vertex:";
	cin >> m_vCount;
}

void GraphList::makeVertexArray()
{
	m_vVertex = new Vertex[m_vCount];
	// 初始化
	for (int i = 0; i < m_vCount; ++i){
		m_vVertex[i].vName = i;
		m_vVertex[i].next = NULL;
	}
}

void GraphList::inputEdgeCount()
{
	cout << "please input count of edge:";
	cin >> m_eCount;
}

void GraphList::inputEdgeInfo()
{
	cout << "please input edge information:" << endl;
	for (int i = 0; i < m_eCount; ++i){
		cout << "the edge " << i << ":" << endl;

		// 起点
		int from = 0;
		cout << "From: ";
		cin >> from;
		
		// 权值
		int weight = 0;
		cout << "Weight:";
		cin >> weight;

		// 终点
		int to = 0;
		cout << "To: ";
		cin >> to;
		cout << endl;

		addEdgeToList(from, weight, to);
	}
}

void GraphList::addEdgeToList(int vFrom, int weight, int vTo)
{
	Edge* edge = new Edge();
	edge->vName = vTo;
	edge->weight = weight;
	edge->next = NULL;
	if (m_vVertex[vFrom].next){
		Edge* tmp = m_vVertex[vFrom].next;
		while(tmp->next){
			tmp = tmp->next;
		}
		tmp->next = edge;
	}else{
		m_vVertex[vFrom].next = edge;
	}
}

void GraphList::printGraph()
{
	for (int i = 0; i < m_vCount; ++i){
		Edge* tmp = m_vVertex[i].next;
		cout << "list:" << m_vVertex[i].vName << "->";
		while(tmp){
			cout << "(" << tmp->weight << ")";
			cout << tmp->vName << "->";
			tmp = tmp->next;
		}
		cout << "NULL" << endl;
	}
}

// **************************************************************************
// 流程控制
// **************************************************************************
void GraphList::createGraph()
{
	inputVertexCount();
	makeVertexArray();
	inputEdgeCount();
	inputEdgeInfo();
}

// main.cpp

// test for GraphList
#include "GraphList.h"
#include <cstdlib>

int main()
{
	GraphList graph;
	graph.createGraph();
	graph.printGraph();

	system("pause");

	return 0;
}

假如有如下的图：