1 基本概念

1.顶点：图中的数据元素
2.边：顶点之间的连接
3.权重：边可以带权重，用来表示从一个顶点到另一个节点的成本。
4.路径：路径是由边连接的顶点组成的序列
5.环：环是有向图中国的一条起点和终点为同一个节点的路径。
6.图的分类：按边有无方向分为有向图，无向图；按边有无权重分为权重图，无权重等等。其分类方式很多，就不一一列出。
7.度：无向图中顶点的边数，有向图中还分为入度和出度。
8.连图图：若图中任意两个顶点都是连通的，称为连通图，在有向图中，称为强连通图。

2 图的存储结构

图的存储结构主要有：1）邻接矩阵：点数组+二维矩阵。2）邻接表：数组+链表。3）十字链表。4）邻接多重表。5）边集数组。
这里主要介绍前两种。
比如简单的带权有向图

2.1 邻接矩阵

邻接矩阵就是通过一个二维矩阵来表示图中两两节点的连接关系或权重。其优点就是简单，缺点是对于大图来说，其是稀疏矩阵，存储空间较大。
邻接矩阵表示

2.2 邻接表

为了实现稀疏连接的图，更高效的方式是使用邻接表。

代码实现

C++版本

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

class Vertex {
public:
	Vertex() {}  //注意：这里需要自己写一个无参构造，因为写了有参构造，编译器不会提供无参构造
	Vertex(int key) {
		this->id = key;
	}

	//添加从一个顶点到另一个顶点的连接
	void addNeighbor(int nbr, int weight = 0) {
		this->connectedTo[nbr] = weight;
	}

	//返回当前节点的邻接表中的所有顶点
	vector<int> getConnections() {
		vector<int> vec;
		for (auto iter = connectedTo.begin(); iter != connectedTo.end(); iter++) {
			vec.push_back(iter->first);
		}
		return vec;
	}

	//返回当前顶点的key
	int getId() {
		return this->id;
	}

	//返回从当前顶点到以参数传入的顶点之间的边的权重
	int getWeight(int nbr) {
		return this->connectedTo[nbr];
	}

	int id;
	unordered_map<int, int> connectedTo;
	
};

class Graph {
public:
	Graph() {
		this->numVertices = 0;
	}

	//向图中添加顶点
	Vertex addVertex(int key) {
		this->numVertices++;
		Vertex newVertex(key);
		this->vertexUmap[key] = newVertex;
		return newVertex;
	}

	//返回某个顶点的邻接表表示
	Vertex getVertex(int key) {
		if (this->vertexUmap.find(key) != this->vertexUmap.end()) {
			return this->vertexUmap[key];
		}
		else {
			return NULL;
		}
	}

	//向图中添加边
	void addEdge(int key1, int key2, int cost=0) {
		if (this->vertexUmap.find(key1) == vertexUmap.end()) {
			this->addVertex(key1);
		}
		if (this->vertexUmap.find(key2) == vertexUmap.end()) {
			this->addVertex(key2);
		}
		this->vertexUmap[key1].addNeighbor(key2, cost);
	}

	//得到图中的所有顶点
	vector<int> getVertices() {
		vector<int> vec;
		for (auto iter = this->vertexUmap.begin(); iter != this->vertexUmap.end(); iter++) {
			vec.push_back(iter->first);
		}
		return vec;
	}

	unordered_map<int, Vertex> vertexUmap;
	int numVertices;
};

//测试
void test01() {
	Graph g;
	for (int i = 0; i < 6; i++) {
		g.addVertex(i);
	}
	cout << g.numVertices << endl;
	vector<int> vertices = g.getVertices();
	for (int i = 0; i < vertices.size(); i++) {
		cout << vertices[i] << " ";
	}
	cout << endl;
	g.addEdge(0, 1, 5);
	g.addEdge(0, 5, 2);
	g.addEdge(1, 2, 4);
	g.addEdge(2, 3, 9);
	g.addEdge(3, 4, 7);
	g.addEdge(3, 5, 3);
	g.addEdge(4, 0, 1);
	g.addEdge(5, 4, 8);
	g.addEdge(5, 2, 1);
	Vertex v = g.getVertex(5);
	cout << v.id << endl;
	vector<int> vec = v.getConnections();
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	cout << v.getWeight(2) << endl;
	for (auto iter = g.vertexUmap.begin(); iter != g.vertexUmap.end(); iter++) {
		vector<int> vec = g.getVertex(iter->first).getConnections();
		for (int i = 0; i < vec.size(); i++) {
			cout << iter->first << " " << vec[i] << endl;
		}
	}
}

void main() {
	test01();
	system("pause");
}

4 参考资料

《大话数据结构》
《Python数据结构与算法分析》