图的概念：
逻辑结构：多对多
graph 图 g
vertex 顶点 v
edge 边\弧 e
图G是由两个集合V和E构成，G = (V,E),其中V是顶点的有限非空集合，E是V中顶点偶对的有限集，这些顶点偶对称为边（弧）
重边：两个顶点不只有一条边
自边：顶点自身形成一条边
图的分类：
不同的维度：
1.方向性：有向图和无向图
2.环：带环图和无环图
//环：从一个点x出发，沿着边走，最终可以回到x
注：有向无环图（DAG）
3.边权：无权图 带权图
图的基本术语：
1.简单图：若不存在顶点到自身的边，且同一条边不重复出现，则称这样的图为简单图
2.无向图：在图中，如果代表边的顶点偶对是无序的，则为无向图
3.有向图：在图中，如果代表边的顶点偶对是有序的，则为有向图
//有向边（弧）
//起点：弧尾
//终点：弧头
//注：无向图可以看成有向图
4.完全图：图中每两个顶点都有一条边
//完全有向图：n（n-1）条边
//完全无向图：n（n-1）/2条边
5.端点，邻接点；
端点：边的两个顶点
邻接点：上述两个顶点互为邻接点
6.顶点的度，入度和出度
//对于无向图而言
度：该点所连的边数
//对于有向图而言
入度；入边的个数
出度：出边的个数
度：出度+入度（一定为偶数）
7.子集：与子树类似
8.路径，路径长度：
路径：顶点序列
路径长度：边的数目
简单路径：一条路径上除开始点和结束点可以相同外，其余顶点均不相同（路径中不含环）
9.回路，环
欧拉环路：经过图中各边一次且恰好一次的环路
哈密尔顿环路：经过图中各顶点一次且恰好一次的环路
10.连通，连通图和连通分量（针对无向图）
1.连通：如果顶点x和y之间存在可以相互抵达的路径，则称两个顶点连通
2.连通图：图中任意两个顶点都连通
3.连通分量：无向图中的极大连通子图称为图的连通分量
注：连通图只有一个极大连通子图（自身）
非连通图有多个极大连通子图
注:极大连通子图（连通分量）
极小连通子图（图的生成树）：在保证各点连通的情况下，边最少
11.强连通图和强连通分量（针对有向图，含义同上）
12.稠密图和稀疏图
一个图接近完全图时，称为稠密图，当一个图含有较少边数时，称为稀疏图，一般以nlogn作为分界线（n为节点个数）
13.权和网
边上带有权的图称为带权图，也称之为网
//注：自边权值看作零，两个点之间没有连接权值看作无穷大
14.连通图的生成树（针对无向图）
连通图的生成树是一个极小的连通子图
图的存储：
1.边集数组
2.邻接矩阵
3.邻接表
4.十字链表
5.多重邻接表
有向图/无向图：边集数组，邻接矩阵，邻接表
有向图：十字链表
无向图：多重邻接表
做题：邻接矩阵，链式前向星（邻接表） //链式前向星后续再学习
存储图：
（1）边集数组：不太方便，效率低，但是简单
存点：数组存点集
存边：起点，终点，边权
（2）邻接矩阵：如果为稀疏图，存在较大空间浪费
存点：数组存点集
存边：二维数组（邻接矩阵），下标就是点的编号
//无权图可以用bool类型二维数组
有向图；i->j j->i e[i][j] != e[j][i]
无向图：i->j j->i e[i][j] == e[j][i]
（3）邻接表：方便算出度，不方便算入度（对于有向图而言）
//为了方便计算入度，可以建立逆邻接表，但不方便计算出度
//二者结合形成十字链表
存点：数组存点集
存边：
1.无向图
把每个顶点的邻接点构成线性表，因为线性表大小不定，所以使用链表
2.有向图
邻接表：顶点后面挂的单链表，由其出边邻接点构成
逆邻接表：顶点后面挂的单链表，由其入边邻接点构成
（4）十字链表：结构复杂，操作简单
把有向图的邻接表和逆邻接表结合起来
结构复杂，使用简单
（5）多重邻接表
同上
//注：做题常用邻接矩阵和邻接表
图的遍历：从图中某点出发，把所有点访问且仅访问一次
1.深度优先遍历（DFS）----->递归/栈
1.右手原则：在没有碰到重复顶点的情况下，分叉口始终是向右边走，每路过一个顶点就做一个记号
2.左手原则：在没有碰到重复顶点的情况下，分叉口始终是向左边走，每路过一个顶点就做一个记号
步骤：
1.首先选定一个未被访问的顶点V作为起始顶点，并将其标记为已经访问过
2.然后搜索与顶点V邻接的所有顶点，判断这些顶点是否被访问过，如果有未被访问过的顶点W,再选取与顶点W邻接的未被访问的一个顶点进行访问，依次重复进行。当一个顶点的所有的邻接顶点都被访问过时，则依次回退到最近被访问的顶点。若该顶点还有其他邻接点未被访问，则从这些未被访问的顶点中取出一个并重复上述过程，直到与起始顶点V相邻接的所有顶点都被访问过为止。
3.若此时图中依然有顶点未被访问，则再选取其中一个顶点作为起始顶点并进行遍历，转第二步，反之，则遍历结束。//即可能该图为非连通图，有多个极大连通子图
2.广度优先遍历（BFS）----->队列
注：图遍历序列不唯一
遍历时间复杂度（DFS与BFS一样）
邻接矩阵（n^2） //n为点的个数
邻接表（n+m） //n为点的个数，m为边的个数
BFS优缺点：
缺点：在搜索过程中，BFS必须要保存搜索过程中的状态，用于判重
优点：一般用于找无权图最短路径
DFS优缺点：
缺点：容易超时/或爆栈
优点：使用空间少，一般用于找所有的解
边集数组:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
class Edge
{
public:
int start;//起点
int end;//终点
int w;//权值
};
class Graph
{
public:
Edge* e;//边集
int* vertex;//点集
int size;//点的个数
public:
Graph(int sz):size(sz)
{
vertex = new int[sz];
e = new Edge[sz * (sz - 1)];//若为无向图，则(sz * (sz - 1)) / 2
if (vertex == nullptr || e == nullptr)
{
cout << "开辟失败" << endl;
}
}
void Find(int x)//找邻接点
{
for (int i = 0; i < size * (size - 1); ++i)
{
if (e[i].start == x)
{
cout << e[i].end << endl;
}
if (e[i].end == x)
{
cout << e[i].start << endl;
}
}
}
};
int main()
{
int a(4);
Graph g(a);
return 0;
}
邻接矩阵:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//有权无向图为例
class Graph
{
public:
int** edge;//邻接矩阵
int* vertex;//点集
int size;//点的个数
int size2;//边的个数
public:
Graph(int sz,int sz2) :size(sz),size2(sz2)
{
vertex = new int[sz];
edge = new int* [sz];
if (vertex == nullptr || edge == nullptr)
{
cout << "开辟失败" << endl;
}
for (int i = 0; i < sz; ++i)
{
edge[i] = new int[sz];
if (edge[i] == nullptr)
{
cout << "开辟失败" << endl;
}
}
}
void Find(int x)//找邻接点,有权无向图,权值大于零
{
for (int i = 0; i < size; ++i)
{
if (edge[x][i] > 0)
{
cout << i << endl;
}
}
}
};
int main()
{
int a(4);
Graph m(a,a);
return 0;
}
邻接表:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//无向带权图为例
class Node
{
public:
int adjv;//邻接点编号
int m_w;//权值
Node* next;
};
class Graph_Node
{
public:
int vertex_i;//点的编号
Node* first;//不使用头节点，直接使用头指针
};
class Graph
{
public:
int size1;//点的个数
int size2;//边的个数
Graph_Node* g;//邻接表
public:
Graph(int sz1,int sz2):size1(sz1),size2(sz2)
{
g = new Graph_Node[sz1];
if (g == nullptr)
{
cout << "开辟失败" << endl;
}
//初始化点
for (int i = 0;i < sz1; ++i)
{
cin >> g[i].vertex_i;
g[i].first = nullptr;
}
//输入边和权值
int x(0);
int y(0);
int w(0);
for (int i = 0; i < sz2; ++i)
{
cin >> x >> y >> w;
//y为x邻接点
Node* s = new Node;
s->adjv = y;
s->m_w = w;
//进行头插
s->next = g[x].first;
g[x].first = s;
//x为y邻接点(开辟一块新的空间)
s = new Node;
s->adjv = x;
s->m_w = w;
//进行头插
s->next = g[y].first;
g[y].first = s;
}
}
};
int main()
{
return 0;
}
十字链表:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//十字链表节点结构
class Link_Node
{
public:
//存储点的数据，若下标与数据不对应，则先找到数据对应下标
int tail_v;//弧尾（起点），加入到弧尾出边单链表
int head_v;//弧头（终点），加入到弧头入边单链表
int wi;//权值
Link_Node* tail_out_next;//弧尾出边单链表下一个节点
Link_Node* head_in_next;//弧头入边单链表下一个节点
};
class Vertex_Node
{
public:
int vertex_i;//点的编号
Link_Node* first_out;//出边单链表头指针
Link_Node* first_in;//入边单链表头指针
};
class Graph
{
public:
int size1;//点的个数
int size2;//边的个数
Vertex_Node* v;//十字链表实现
public:
Graph(int sz1,int sz2):size1(sz1),size2(sz2)
{
v = new Vertex_Node[sz1];
if (v == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//初始化点
for (int i = 0; i < sz1; ++i)
{
cin >> v[i].vertex_i;
v[i].first_in = nullptr;
v[i].first_out = nullptr;
}
//进行两次头插
//输入边和权值
int x(0);
int y(0);
int w(0);
for (int i = 0; i < sz2; ++i)
{
cin >> x >> y >> w;
Link_Node* s = new Link_Node;
s->tail_v = x;
s->head_v = y;
s->wi = w;
//第一次头插
//s插入到弧尾x出边单链表中
s->tail_out_next = v[x].first_out;
v[x].first_out = s;
//第二次头插
//s插入到弧头y入边单链表中
s->head_in_next = v[y].first_in;
v[y].first_in = s;
}
}
}
};
int main()
{
Graph g(4, 6);
int ans(0);
int x(0);
cin >> x;
Link_Node* p = g.v[x].first_out;
while (p != nullptr)
{
ans++;
p = p->tail_out_next;
}
cout << ans;
return 0;
}
/*
1 0 3
0 1 4
1 2 2
2 0 5
0 3 6
2 3 8
2
*/
多重邻接表:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//多重邻接表
//无向图邻接表一条边存储两次，浪费空间
class Link_Node
{
public:
//存储点的数据，若下标与数据不对应，则先找到数据对应下标
//两个端点
int vi;
int vj;
int wi;//权值
Link_Node* vi_next;//vi单链表下一个节点
Link_Node* vj_next;//vj单链表下一个节点
};
class Vertex_Node
{
public:
int vertex_i;//点的编号
Link_Node* first;//边单链表头指针
};
class Graph
{
public:
int size1;//点的个数
int size2;//边的个数
Vertex_Node* v;//多重邻接表实现
public:
Graph(int sz1,int sz2):size1(sz1),size2(sz2)
{
v = new Vertex_Node[sz1];
if (v == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//初始化点
for (int i = 0; i < sz1; ++i)
{
cin >> v[i].vertex_i;
v[i].first = nullptr;
}
//输入边和权值
int x(0);
int y(0);
int w(0);
for (int i = 0; i < sz2; ++i)
{
cin >> x >> y >> w;
Link_Node* s = new Link_Node;
s->vi = x;
s->vj = y;
s->wi = w;
//第一次头插(先vi)
s->vi_next = v[x].first;
v[x].first = s;
//第二次头插(后vj)
s->vj_next = v[y].first;
v[y].first = s;
}
}
}
};
int main()
{
Graph g(4, 5);
int ans(0);
int x(0);
cin >> x;
Link_Node* p = g.v[x].first;
while (p != nullptr)
{
ans++;
if (p->vi == x)
{
p = p->vi_next;
}
else
{
p = p->vj_next;
}
}
cout << ans << endl;
return 0;
}
/*
0
1
2
3
0 1 3
0 3 5
0 2 5
1 3 6
3 2 6
*/
BFS:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//队列实现，循环队列
//将点的下标入队
template<class T>
class m_queue
{
public:
T* data;
int size;
int front;
int rear;
public:
m_queue(int sz):size(sz)
{
data = new T[sz];
if (data == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
rear = 0;//指向队尾元素下一个元素
front = 0;
}
}
void En_queue(T k)
{
//牺牲一个位置与判空区分
if ((rear + 1) % size == front)
{
cout << "队列已满" << endl;
}
else
{
data[rear] = k;
//cout << k << "入队" << endl;
//实现循环效果
rear = (rear + 1) % size;
}
}
T De_queue()
{
int x(0);
//保存出队元素
if (front == rear)
{
cout << "队空" << endl;
return -1;
}
else
{
x = data[front];
front = (front + 1) % size;
//cout << x << "出队" << endl;
return x;
}
}
bool m_empty()
{
if (front == rear)
{
return true;
}
else
{
return false;
}
}
};
//以一个无权无向图为基础 进行BFS
//存储方式：邻接表
class Edge_Node
{
public:
int adj_v;//邻接点下标
Edge_Node* next;
};
class Graph_Node
{
public:
char vertex_i;//顶点编号
Edge_Node* first;//边链表
};
class Graph
{
public:
int size1;//点的个数
int size2;//边的个数
Graph_Node* g;//邻接表
bool* visit;//记录是否访问过
public:
Graph(int sz1,int sz2):size1(sz1),size2(sz2)
{
g = new Graph_Node[sz1];
visit = new bool[sz1];
if (g == nullptr || visit == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
//初始化
for (int i = 0; i < size1; ++i)
{
cin >> g[i].vertex_i;
g[i].first = nullptr;
visit[i] = false;
}
//读入数据
int x(0);
int y(0);
for (int i = 0; i < size2; ++i)
{
cin >> x >> y;
//两次头插
Edge_Node* s = new Edge_Node;
//y为邻接点
s->adj_v = y;
s->next = g[x].first;
g[x].first = s;
s = new Edge_Node;
//x为邻接点
s->adj_v = x;
s->next = g[y].first;
g[y].first = s;
}
}
}
//为了避免重复入队，一入队便标记
void BFS()
{
//声明队列
m_queue<int> q(100);
//存储出队元素
int x(0);
Edge_Node* p = nullptr;
for (int i = 0; i < size1; ++i)
{
if (visit[i] == false)
{
//以下标为i点做起点
//把i点入队
q.En_queue(i);
visit[i] = true;
while (!q.m_empty())
{
x = q.De_queue();
//访问
cout << g[x].vertex_i << endl;
//下标为x点邻接点入队
p = g[x].first;
while (p != nullptr)
{
if (visit[p->adj_v] == false)
{
q.En_queue(p->adj_v);
visit[p->adj_v] = true;
}
p = p->next;
}
}
}
}
}
};
int main()
{
Graph g(9, 15);
g.BFS();
return 0;
}
//也可以将点的编号入队，但如果将编号入队，
//需要先根据编号找到对应下标
/*
测试用例：
9
15
ABCDEFGHI
0 1
0 5
1 6
5 6
2 1
1 8
2 8
6 7
2 3
3 8
3 7
3 4
4 7
4 5
3 6
*/
DFS:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//以一个无权无向图为基础 进行DFS
//存储方式：邻接矩阵
class Graph
{
public:
int** edge;//邻接矩阵
char* vertex;//点集数组
bool* visit;//存储已经访问过的点(与点集数组下标对应)
int size1;//点的个数
int size2;//边的个数
public:
Graph(int sz1, int sz2) :size1(sz1), size2(sz2)
{
vertex = new char[sz1];
visit = new bool[sz1];
edge = new int* [sz1];
if (visit == nullptr || edge == nullptr || vertex == nullptr)
{
cout << "开辟失败" << endl;
}
for (int i = 0; i < sz1; ++i)
{
edge[i] = new int[sz1];
if (edge[i] == nullptr)
{
cout << "开辟失败" << endl;
}
}
for (int i = 0; i < sz1; ++i)
{
cin >> vertex[i];
visit[i] = false;
}
int x(0);
int y(0);
//假设x，y之间有一条边
for (int i = 0; i < sz2; ++i)
{
cin >> x >> y;
edge[x][y] = 1;
edge[y][x] = 1;
}
}
//以下标为零的点开始遍历
//DFS和DFSg两层循环避免图为非连通图时只遍历一个极大连通子图
void DFS()
{
for (int i = 0; i < size1; ++i)
{
if (visit[i] == false)
{
//标记为已经访问
visit[i] = true;
DFSg(i);
}
}
}
void DFSg(int x)
{
//访问点x
cout << vertex[x] << endl;
//再访问x邻接点
for (int i = 0; i < size1; ++i)
{
//没访问过且为x邻接点
if (visit[i] == false && edge[x][i] == 1)
{
//标记为已经访问
visit[i] = true;
DFSg(i);
}
}
}
};
int main()
{
Graph g(9, 15);
g.DFS();
return 0;
}
/*
测试用例：
9
15
ABCDEFGHI
0 1
0 5
1 6
5 6
2 1
1 8
2 8
6 7
2 3
3 8
3 7
3 4
4 7
4 5
3 6
*/
