目录
catalog.png
图的定义
数据结构中，图由顶点和边构成如下：
图1
上图中数字代表顶点（Vertex）,连接顶点的是边（Edge），通过边表示顶点之间的逻辑关系。
无向图
定义：若表示顶点关系的边没有方向（无向边），则此图为无向图，如图1。顶点Vi到Vj之间的边表示为(Vi,Vj)，代表Vi，Vj邻接。
-
顶点的度：
与某个顶点有关的边的数量，代表此顶点的度。如图1，顶点
1的度为2。 -
完全无向图
无向图中，如果每个顶点都存在到其他顶点的边，则此图为完全无向图：
UnGraph.png
完全无向图有n(n-1)/2条边，n为顶点数。
有向图
-
定义
当顶点之间的边有方向时，图为有向图。如下：
directed.png
并使用有序对<Vi，Vj>来表示顶点Vi，Vj之间的边，称为弧。Vi称为弧尾，Vj为弧头。例如，上图顶点A、D之间的边表示为：<A,D>表明方向A->D
-
出度、入度
以顶点Vi为弧尾的弧数量，表示Vi的出度，以顶点Vi为弧头的数量，表示Vi的入度。
-
完全有向图
任意顶点存在互为相反方向的边，称为完全有向图
网
图中的边或弧，存在对应的数字，这样的图称为网，边或弧对应的数字称为权。
network.png
上图的权值表示距离。
连通性
连通图
在无向图G中，存在从Vi到Vj的路径，则称Vi和Vj是连通的。如果G中任意两个顶点都是连通的，则称G为连通图。
connected.png
无向图中的极大连通子图称为连通分量，连通分量条件：
- 子图
- 子图要是连通的
- 连通子图含有极大顶点数
强连通图
在有向图G中，对于任意Vi,Vj,存在Vi->Vj 和Vj->Vi的路径，则称G是强连通图。
有向图的极大强连通子图称为强连通分量
图的存储结构
邻接矩阵
使用两个数组来表示图。
- 一个一维数组Vertex表示顶点
- 一个二维数组edge表示边。
edge[i][j]= W //表示权值
0 //i=j
Infinty // 表示边(i,j)不存在
Adjcency Matrix.png
邻接表
邻接表与邻接矩阵相比，使用链表代替二维数组。对于边数比顶点数少的情况，邻接矩阵存在着巨大的浪费，而使用链式结构可以很好的避免浪费。
- 使用一个一维数组表示顶点
- 使用单链表来表示每个顶点的邻接顶点
Adjcency List.png
其他结构
十字链表、多重邻接表
十字链表作用于有向图、多重邻接表作用于无向图，都是邻接表的进阶版本，不做详细介绍
邻接表代码实现
边节点结构：
typedef struct EdgeNode{ //边节点
int adjVertex;
Tweight weight; //权重
EdgeNode* next;
}EdgeNode;
顶点节点结构：
typedef struct VertexNode { //顶点节点
Tvertex vertex; //顶点值
EdgeNode* firstEdge; //指向的边
}VertexNode;
类声明：
template<typename Tvertex, typename Tweight>
class UndirectedGraph //邻接表实现无向图
{
private:
typedef struct EdgeNode{ //边节点
int adjVertex;
Tweight weight; //权重
EdgeNode* next;
}EdgeNode;
typedef struct VertexNode { //顶点节点
Tvertex vertex; //顶点值
EdgeNode* firstEdge; //指向的边
}VertexNode;
std::vector<VertexNode> graph; //保存顶点的数组
int verxNums; //顶点数量
int edgeNums; //边数量
public:
UndirectedGraph(int vn = 0,int en = 0):verxNums(vn),edgeNums(en){}
void CreateGraph();
void CreateGraph(std::vector<Tvertex> vertex,
std::pair<std::vector<int>, Tweight> edgeWeight[]);
};
图创建函数：
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph() {
//初始化顶点数组
for (int i = 0; i < verxNums; i++) {
VertexNode* v = new VertexNode;
std::cout << "Input vertex "<< i <<" value:" << std::endl;
std::cin >> v->vertex;
v->firstEdge = nullptr;
graph.push_back(*v);
}
//为顶点添加相关的边信息
for (int nums = 0; nums < edgeNums; nums++) {
int i, j;
Tweight weight;
std::cout << "Input the i,j of (vi,vj): ";
std::cin >> i >> j;
std::cout << "Input the weight of (vi,vj): ";
std::cin >> weight;
EdgeNode* e = new EdgeNode; //添加(vi,vj)
e->adjVertex = j;
e->weight = weight;
e->next = graph[i].firstEdge; //插入边节点
graph[i].firstEdge = e;
e = new EdgeNode; //无向图还需要添加(vj,vi)
e->adjVertex = i;
e->weight = weight;
e->next = graph[j].firstEdge;
graph[j].firstEdge = e;
}
}
为方便测试，编写了一个静态生成图的函数,内容基本一样，该函数从一个节点数组std::vector<Tvertex> vertex读入节点信息，一个pair结构数组std::pair<std::vector<int>, Tweight> edgeWeight[]表示边和权值：
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph(std::vector<Tvertex> vertex,
std::pair<std::vector<int>, Tweight> edgeWeight[]) {
for (int i = 0; i < verxNums; i++) {
VertexNode* v = new VertexNode;
v->vertex = vertex[i];
v->firstEdge = nullptr;
graph.push_back(*v);
}
for (int nums = 0; nums < edgeNums; nums++) {
int i, j;
Tweight weight;
i = edgeWeight[nums].first[0];
j = edgeWeight[nums].first[1];
weight = edgeWeight[nums].second;
EdgeNode* e = new EdgeNode; //添加(vi,vj)
e->adjVertex = j;
e->weight = weight;
e->next = graph[i].firstEdge;
graph[i].firstEdge = e;
e = new EdgeNode;
e->adjVertex = i; //添加(vj,vi)
e->weight = weight;
e->next = graph[j].firstEdge;
graph[j].firstEdge = e;
}
//显示相关信息
for (auto v : graph) {
std::cout << "Vertex: " << v.vertex << std::endl;
std::cout << "Edges: ";
for (auto p = v.firstEdge; p != nullptr;p = p->next) {
std::cout << p->adjVertex << " ";
}
std::cout << std::endl;
std::cout << std::endl;
}
}
图的遍历
深度优先（Depth First Search）
与树的中根遍历模式一样类似
DFS.png
如上图是按照搜索右边的节点规则，进行深度优先遍历，从A开始不断深入搜索A->B->C->D->E->F->G->H,搜索完H发现没有未遍历的邻接点，开始回退，退回到D，然后访问I，完成所有节点的遍历。
深度优先遍历实现：
- 与二叉树的遍历一样使用递归
- 使用一个长度为顶点数的数组来标记顶点是否被访问
代码实现：
//声明
template<typename Tvertex, typename Tweight>
class UndirectedGraph //邻接表实现无向图
{
private:
...
void DFS(std::vector<bool>& isVisted, int i); //深度优先遍历递归调用函数，外部无需访问该方法申明为私有
public:
...
void DFSTraverse();
...
};
//定义
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFS(std::vector<bool>& isVisted,int i) {
isVisted[i] = true;
std::cout << graph[i].vertex << " ";
for (auto p = graph[i].firstEdge; p != nullptr; p = p->next){ //遍历链表
if (!isVisted[p->adjVertex]) {
DFS(isVisted, p->adjVertex); //对链表元素继续DFS
}
}
}
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFSTraverse() {
std::vector<bool> isVisted(verxNums,false); //访问标识数组，初始化为false
for (int i = 0; i < verxNums; i++) { //防止存在子图的情况，未遍历子图
if (!isVisted[i]) {
DFS(isVisted,i);
}
}
std::cout << std::endl;
}
广度优先遍历
与树的层次遍历相似，一层一层往下遍历，对每一层做最大范围遍历。并且与树的层次遍历实现相同，使用队列保存未遍历元素
BFS.png
代码实现：
//声明
template<typename Tvertex, typename Tweight>
class UndirectedGraph //邻接表实现无向图
{
public:
...
void BFSTraverse();
};
//定义
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::BFSTraverse() {
std::vector<bool> isVisted(verxNums, false);
std::queue<VertexNode> Q;
VertexNode v;
for (int i = 0; i < verxNums; i++) { //防止存在子图的情况，未遍历子图
if (!isVisted[i]) {
Q.push(graph[i]);
isVisted[i] = true;
}
while (!Q.empty()) {
v = Q.front(); //去队头元素
std::cout << v.vertex << " ";
for (auto p = v.firstEdge; p != nullptr; p = p->next) {
if (!isVisted[p->adjVertex]) {
Q.push(graph[p->adjVertex]);
isVisted[p->adjVertex] = true;
}
}
Q.pop();
}
}
std::cout << std::endl;
}
完整代码和测试
#pragma once
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
/********************************************
* 时间：2021/1/2
* 作者：tanghf
* 类简介：使用邻接表实现无向图
********************************************/
template<typename Tvertex, typename Tweight>
class UndirectedGraph //邻接表实现无向图
{
private:
typedef struct EdgeNode{ //边节点
int adjVertex;
Tweight weight; //权重
EdgeNode* next;
}EdgeNode;
typedef struct VertexNode { //顶点节点
Tvertex vertex; //顶点值
EdgeNode* firstEdge; //指向的边
}VertexNode;
std::vector<VertexNode> graph;
int verxNums; //顶点数量
int edgeNums; //边数量
void DFS(std::vector<bool>& isVisted, int i); //深度优先遍历递归调用函数
public:
UndirectedGraph(int vn = 0,int en = 0):verxNums(vn),edgeNums(en){}
void CreateGraph(std::vector<Tvertex> vertex,
std::pair<std::vector<int>, Tweight> edgeWeight[]); //静态创建无向图
void CreateGraph(); //动态输入创建无向图
void DFSTraverse();
void BFSTraverse();
};
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph(std::vector<Tvertex> vertex,
std::pair<std::vector<int>, Tweight> edgeWeight[]) {
for (int i = 0; i < verxNums; i++) {
VertexNode* v = new VertexNode;
v->vertex = vertex[i];
v->firstEdge = nullptr;
graph.push_back(*v);
}
for (int nums = 0; nums < edgeNums; nums++) {
int i, j;
Tweight weight;
i = edgeWeight[nums].first[0];
j = edgeWeight[nums].first[1];
weight = edgeWeight[nums].second;
EdgeNode* e = new EdgeNode; //添加(vi,vj)
e->adjVertex = j;
e->weight = weight;
e->next = graph[i].firstEdge;
graph[i].firstEdge = e;
e = new EdgeNode;
e->adjVertex = i; //添加(vj,vi)
e->weight = weight;
e->next = graph[j].firstEdge;
graph[j].firstEdge = e;
}
for (auto v : graph) {
std::cout << "Vertex: " << v.vertex << std::endl;
std::cout << "Edges: ";
for (auto p = v.firstEdge; p != nullptr;p = p->next) {
int adjVxIndex = p->adjVertex;
std::cout << "(" << v.vertex << ","
<< graph[adjVxIndex].vertex << "),weight = "<< p->weight<<" ";
}
std::cout << std::endl;
std::cout << std::endl;
}
}
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::CreateGraph() {
//初始化顶点数组
for (int i = 0; i < verxNums; i++) {
VertexNode* v = new VertexNode;
std::cout << "Input vertex " << i << " value:" << std::endl;
std::cin >> v->vertex;
v->firstEdge = nullptr;
graph.push_back(*v);
}
//为顶点添加相关的边信息
for (int nums = 0; nums < edgeNums; nums++) {
int i, j;
Tweight weight;
std::cout << "Input the i,j of (vi,vj): ";
std::cin >> i >> j;
std::cout << "Input the weight of (vi,vj): ";
std::cin >> weight;
EdgeNode* e = new EdgeNode; //添加(vi,vj)
e->adjVertex = j;
e->weight = weight;
e->next = graph[i].firstEdge; //插入边节点
graph[i].firstEdge = e;
e = new EdgeNode; //无向图还需要添加(vj,vi)
e->adjVertex = i;
e->weight = weight;
e->next = graph[j].firstEdge;
graph[j].firstEdge = e;
}
//输出添加的信息
for (auto v : graph) {
std::cout << "Vertex: " << v.vertex << std::endl;
std::cout << "Edges: ";
for (auto p = v.firstEdge; p != nullptr; p = p->next) {
std::cout << p->adjVertex << " ";
}
std::cout << std::endl;
std::cout << std::endl;
}
}
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFS(std::vector<bool>& isVisted,int i) {
isVisted[i] = true;
std::cout << graph[i].vertex << " ";
for (auto p = graph[i].firstEdge; p != nullptr; p = p->next){
if (!isVisted[p->adjVertex]) {
DFS(isVisted, p->adjVertex);
}
}
}
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::DFSTraverse() {
std::vector<bool> isVisted(verxNums,false);
for (int i = 0; i < verxNums; i++) {
if (!isVisted[i]) {
DFS(isVisted,i);
}
}
std::cout << std::endl;
}
template<typename Tvertex, typename Tweight>
void UndirectedGraph<Tvertex, Tweight>::BFSTraverse() {
std::vector<bool> isVisted(verxNums, false);
std::queue<VertexNode> Q;
VertexNode v;
for (int i = 0; i < verxNums; i++) {
if (!isVisted[i]) {
Q.push(graph[i]);
isVisted[i] = true;
}
while (!Q.empty()) {
v = Q.front();
std::cout << v.vertex << " ";
for (auto p = v.firstEdge; p != nullptr; p = p->next) {
if (!isVisted[p->adjVertex]) {
Q.push(graph[p->adjVertex]);
isVisted[p->adjVertex] = true;
}
}
Q.pop();
}
}
std::cout << std::endl;
}
对如下图进行测试：
minispantree.png
main:
int main() {
UndirectedGraph<string,int> g(9,15);
pair <vector<int>, int> edgeWeight[15] = {
{{0,1},10},{{0,5},11},{{1,2},18},
{{1,6},16},{{1,8},12},{{2,8},8},
{{2,3},22},{{3,6},24},{{3,8},21},
{{3,7},16},{{3,4},20},{{4,5},26},
{{4,7},7},{{5,6},17},{{6,7},19},
};
vector<string> vertex = { "v0","v1","v2","v3","v4","v5","v6","v7","v8" };
g.CreateGraph(vertex,edgeWeight);
cout << "DFS:" << endl;
g.DFSTraverse();
cout << "BFS:" << endl;
g.BFSTraverse();
}
result.png
