C++ 不知图系列之基于链接表的无向图最短路径搜索

1. 前言

图的常用存储方式有 2 种：

• 邻接炬阵。

• 链接表。

邻接炬阵的优点和缺点都很明显。优点是简单、易理解，但是对于大部分图结构而言，都是稀疏的，使用矩阵存储，空间浪费就较大。

链接表相比较邻接矩阵存储方案，使用起来更方便，对于空间的使用是刚好够用原则，不会产生太多空间浪费。理解起来可能会有点难度。

本文将以链接表方式存储图结构，在此基础上实现无向无权图最短路径搜索。

2. 链接表

2.1 存储思路

使用链接表实现图的存储时，有主表和子表概念。

• 主表： 用来存储图对象中的所有顶点数据。
• 子表： 每一个顶点自身会维护一个子表，用来存储与其相邻的所有顶点数据。

如下图结构中有 5 个顶点，使用链接表保存时，需要主表 1 张，子表 5 张。链接表的优点是能够紧凑地表示稀疏图。

2.2 图的存储实现

2.2.1 项点类

因顶点本身是具有特定的数据含义（如，可能是城市、公交车站、网址、路由器……），需要一个顶点类承载顶点的有效数据。并在顶点类中提供维护自身信息的函数。

#include 
#include 
#include 
#include 
using namespace std;
template
struct Vertex {
	// 顶点的编号
	int vid;
	// 顶点有效负荷
	T value;
	// 是否被访问过:False 没有 True:有
	bool visited ;
    
    //相邻顶点类型
	template
	struct NeighborVertex {
		Vertex *vertex;
		//和相邻顶点的权重
		int weigth;
		//兄弟顶点
		NeighborVertex *next;
		NeighborVertex(	Vertex *ver,int weigth) {
			this->vertex=ver;
			this->weigth=weigth;
			this->next=NULL;
		}
	};
	// 相邻顶点链表
	NeighborVertex *  head;
	//搜索时的前驱结点
	Vertex* preVertex;
    //无参构造
	Vertex() {
		this->vid=0;
		this->visited=false;
		this->head=NULL;
	}
    //有参构造
	Vertex(int vid,T value) {
		this->vid=vid;
		this->visited=false;
		this->head=NULL;
		this->value=value;
	}
	/*
	*在链表中使用头部插入方案添加邻接顶点
	*nbrVer:相邻顶点
	*weight:无向无权重图，权重默认设置为 1
	*/
	void addNeighbor(Vertex *nbrVer,int weigth) {
		NeighborVertex * newNbrVer=new NeighborVertex(nbrVer,weigth);
		//头部添加
		if(this->head==NULL) {
			this ->head=newNbrVer;
		} else {
			newNbrVer->next=this->head;
			this->head=newNbrVer;
		}
	}
	
    /*
	*   显示与当前顶点相邻的顶点
	*/
	vector *> showAllNeighbor() {
		NeighborVertex *move=this->head;
		vector *> allNeighbor;
		while(move!=NULL) {
			allNeighbor.push_back(move->vertex);
			move->vertex->desc();
			cout<<"_权重"<weigth<<"\t";
			move=move->next;
		}
		return allNeighbor;
	}
	/*
	*判断与某顶点是否相邻，并返回权重  0 表示与此顶点不相邻
	*/
	int  isNeighbor(NeighborVertex *ver) {
		NeighborVertex *move=this->head;
		while(move!=NULL && move->vertex->value!=ver->value) {
			move=move->next;
		}
		if (move==NULL)
			return 0;
		else
			return move->weigth;
	}

	//顶点的自我显示
	void desc() {
		cout<<"顶点["<vid<<"_"<value<<"]";
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

顶点类结构需要说明地方：

• visited：用于搜索路径算法中，检查节点是否已经被搜索过。
• head：存储与顶点相邻的顶点信息，也称为相邻顶点，相邻顶点需要包括 2 方面信息，一是顶点Vertex信息，二是权重。这里提供了NeighborVertex类型，在Vertex类型的基础之上封装了权重。

2.2.2 图类

图类用于维护l图中的所有顶点以及顶点之间的关系，以及针对于图的相关算法。

template
class Graph {
	private:
		// 一维数组，存储节点
		Vertex** vertexs;
		// 顶点编号,从 0 开始
		int vnums;
		//一维数组大小
		int size;
	public:
		Graph(int size) {
			//初始一给数组大小
			this->vertexs=new Vertex*[size];
			this->vnums=0;
			this->size=size;
		}
		//添加新顶点
		Vertex * addVertex(T value);
		//为顶点添加相邻顶点
		void addNeighbor(T parentValue,T nbrValue,int weight);
		//按值查找顶点
		Vertex * findVertexByValue(T value);
		//按编号查找顶点
		Vertex * findVertexById(int id);
		//显示所有顶点
		void showAllVers();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

查找函数：

查找算法有 2 种方案：

• 按值查找。

/*
*按值查找顶点是否存在
*/
template
Vertex * Graph::findVertexByValue(T value) {
	for(int i=0; i::vnums; i++) {
		if(Graph::vertexs[i]==NULL)
			continue;
		if(Graph::vertexs[i]->value==value) {
			return Graph::vertexs[i];
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 按编号查找。

/*
*按编号查找顶点是否存在
*/
template
Vertex * Graph::findVertexById(int id) {
	for(int i=0; i::vnums; i++) {
		if(Graph::vertexs[i]->vid==id) {
			return Graph::vertexs[i];
		}
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

添加新顶点函数： 先查找是否存在顶点，没有就添加。

顶点的编号由图对象内部指定，便于统一管理。

/*
*添加新的顶点
*/
template
Vertex * Graph::addVertex(T value) {
	//检查此顶点是否存在
	Vertex * ver= Graph::findVertexByValue(value);
	if(ver==NULL) {
		//创建新的顶点
		ver=new  Vertex(Graph::vnums,value);
		Graph::vertexs[Graph::vnums]=ver;
		Graph::vnums++;
	}
	return ver;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

添加顶点之间的关系：

//为顶点添加相邻顶点
template
void Graph::addNeighbor(T parentValue,T nbrValue,int weight) {
	Vertex * parentVer= Graph::findVertexByValue(parentValue);
	if(parentVer==NULL)
		parentVer=Graph::addVertex(parentValue);
	Vertex * nbrVer= Graph::findVertexByValue(nbrValue);
	if(nbrVer==NULL)
		nbrVer=Graph::addVertex(nbrValue);
	//调用顶点的函数
	parentVer->addNeighbor(nbrVer,weight);
}
1
2
3
4
5
6
7
8
9
10
11
12

显示所有顶点：

template
void Graph::showAllVers() {
	for(int i=0; i::vnums; i++) {
		Graph::vertexs[i]->desc();
		cout<showAllNeighbor();
		cout<

int main(int argc, char** argv) {
	//实例化图
	Graph *graph=new Graph(10);
	//添加几个顶点 A，B C D E
	char vers[5]= {'A','B','C','D','E'};
	for(int i=0; i<5; i++) {
		graph->addVertex(vers[i]);
	}
	//添加顶点之间的关系（A -(3)-》B ）
	graph->addNeighbor('A','B',3);
	//添加顶点之间的关系（A -(5)-》D ）
	graph->addNeighbor('A','D',5);
	//添加顶点之间的关系（B -(4)-》c ）
	graph->addNeighbor('B','C',4);
	//添加顶点之间的关系（C -(6)-》D）
	graph->addNeighbor('C','D',6);
	//添加顶点之间的关系（C -(1)-》E）
	graph->addNeighbor('C','E',1);
	//添加顶点之间的关系（D -(2)-》E）
	graph->addNeighbor('D','E',2);
	//添加顶点之间的关系（E -(7)-》B）
	graph->addNeighbor('E','B',7);
	//输出所的顶点
	graph->showAllVers();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 template
class Graph {
	private:
         //省略……
         //保存所有使用广度算法搜索到的路径
		vector *> >  allPaths;
	public:
         //省略……
		//把某一顶点的相邻顶点压入队列
		void pushQueue(queue *> & myQueue,Vertex * vertex);
		//广度搜索路径
		void bfsNearestPath(T from,T to);
		//输出广度搜索到的所有路径
		void showAllPaths();
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//把某一顶点的相邻顶点压入队列
template
void  Graph::pushQueue(queue *> & myQueue,Vertex *  vertex) {
	//查找  vertex 的相邻顶点
	cout<value<<"相邻顶点:"< *> allVers=vertex->showAllNeighbor();	
	for(int i=0; ivisited==false) {
			//设置前驱顶点
			allVers[i]->preVertex=vertex;
			//压入队列中
			myQueue.push(allVers[i]);
			//设置为已经压入
			allVers[i]->visited=true;
		}
	}
	cout<