图
一：图的表示
1.邻接矩阵表示法
int G[N][N];
2.邻接表
//使用（可变数组）vector进行表示，十分方便。
vector<int> Adj[5];
//当要添加一个元素时，例，对于顶点1，添加到顶点3的一条路径
Adj[1].push_back(3);
struct Node{
int v; //边的终点编号
int w; //边权
//这里我们使用自定义构造函数
Node(int a, int b) : v(a), w(b) {}
};
vector<Node> Adj[n];
//对于顶点1，添加到顶点3，权值为4的路径
Adj[1].push_back(Node(3,4));
图的遍历
1.使用深度优先搜索（DFS）遍历
使用深度DFS遍历图的过程就是，沿着一条路径一直走，当走到尽头的时候，退回到当前路径上离
当前顶点最近的还存在未遍历的分支顶点的岔道口，然后沿着这条岔道口前进。依次类推，直到遍历完整个图
int n, G[101][101];
bool vis[101] = {false};
//u为当前要访问的顶点，depth为当前顶点所处的深度
void DFS(int u, int depth) {
//将当前正在访问的顶点设为true，即表示已经被遍历过了
vis[u] = true;
//对所有能从u出发的能到达的分支顶点进行枚举遍历
for(int v=0; v<n; v++) {
//如果当前顶点未被遍历过且对于u顶点来说能够到达的话，则进行DFS遍历
if(vis[v] == false && G[u][v] != INT_MAX) {
DFS(v, depth+1);
}
}
}
//进行遍历
void DFS_Trverse () {
//对每个顶点u进行遍历
//这里为什么要这样是因为可能这个图并不是一个连通图，而是分为好几个连通块，所以对每个顶点进行一下遍历
//也就意味着，如果是一个连通图，一次DFS便全都会遍历完，后面的顶点的DFS都不会进去。
//以下的BFS也是同类意思
for(int u=0; u<n; u++) {
if(vis[u] = false) {
//对u和u所在的连通块进行访问，此时最初深度为1
DFS(u,1);
}
}
}
//创建一个vector的数组
vector<int> Adj[101];
int n;
bool vis[101] = {false};
//u为当前要访问的顶点，depth为当前顶点所处的深度
void DFS(int u, int depth) {
//将当前正在访问的顶点设为true，即表示已经被遍历过了
vis[u] = true;
//遍历当前顶点所在的连通块
for(int i=0; i<Adj[u].size(); i++) {
int v = Adj[u][i];
//当vis[v]未被访问，则进行DFS
if(vis[v] == false) {
DFS(v, depth+1);
}
}
}
//进行遍历
void DFS_Trverse () {
//对每个顶点u进行遍历
for(int u=0; u<n; u++) {
if(vis[u] = false) {
//对u和u所在的连通块进行访问，此时最初深度为1
DFS(u,1);
}
}
}
使用广度优先搜索(BFS)遍历
使用BFS遍历图的过程就是，按层进行访问。比如从开始点出发，先访问完下一层也就是跟这个点相连接的点，
然后再去访问跟第一层几个点所相连的第二层的几个点。使用队列实现。
基本思想：建立一个队列，并把初始顶点加入队列，此后每次都取出队首顶点进行访问，并把从该顶点能到达的
并且未被加入过队列的顶点都加入队列，依次进行，直到队列为空
//n为顶点数
int n, G[101][101];
//用于表示是否加入过队列
bool inq[101] = {false};
//访问u所在的连通块
void BFS(int u) {
//定义队列q;
queue<int> q;
//将初始顶点加入队列
q.push(u);
inq[u] = true;
//循环，终止条件：队列为空
while(!q.empty()) {
//取出队首元素
int a = q.pop();
//将a能到达的顶点加入队列
for(int v=0; v<n; v++) {
if(inq[v]==false && G[a][v]!=0) {
q.push[v];
inq[v] = true;
}
}
}
}
//对整个图进行BFS
void BFSTrave() {
//这里为什么要对每个顶点进行遍历，有疑问的同学可以看看上面DFS的解释
for(int u=0; u<n; u++) {
if(inq[u]==false) {
BFS(u);
}
}
}
int n;
vecotr<int> Adj[101];
bool inq[101] = {false};
void BFS(int u) {
queue<int> q;
q.push(u);
q[u] = true;
while (!q.empty()) {
int a = q.pop();
for(int i=0; i<Adj[a].size(); i++) {
int v = Adj[a][i];
if(inq[v]==false) {
q.push(v);
inq[v] = true;
}
}
}
}
//遍历整个图
void BFSTrave() {
for(int u=0; u<n; u++) {
if(inq[u]==false) {
BFS(u);
}
}
}
最短路径问题
最短路径解决的单源最短路问题。即给定一个图和一个起点，求从起点到其他顶点的最短距离或最短路径
Dijkstra算法
条件：首先有一个bool数组记录该顶点是否被访问过，还有一个数组d[]记录从起点到该顶点的最短距离
数组d的每个数可以初始化为一个很大的数，比如INT_MAX,表示该点不可达。
思路：从该点(a)出发，找出一个与点(a)已知距离最近的一个点(b)进行访问，到达点(b)后，看是否能够
借助点(b)使得从点(a)能够到达其他点比原来的记录的d更近，如果能，则更新d
然后又找一个距离最小且未被访问的点进行下一轮
也就意味着这是一个不断访问最小距离点，并借此更新到其他点的最短距离的过程
int n, G[101][101];
int d[101];
bool vis[101] = {false};
//以s为出发点
void Dijkstra(int s) {
//将d全部初始化为一个特别大的数，表示不可到达
fill(d, d+n, INT_MAX);
//到s的距离为0
d[s] = 0;
//最多进行n次循环，因为每次循环都会经过一个可到达的点。
// 如果是非连通图，还有些点一定不可达
for(int i=0; i<n; i++) {
//找出一个离源点已知距离最近的点
//第一次循环，j就是s点。因为此时只有s点可达
int u = -1, min = INT_MAX;
for(int j=0; j<n; j++) {
if(vis[j]==false && d[j]<min) {
u = j;
min = d[j];
}
}
//当u还是-1时，表示已经找不到还未到达的点了。
if(u == -1) {
return;
}
//到此就表示已经访问过了该点
vis[u] = true;
//进行最短路径更新
for(int j=0; j<n; j++) {
//当该点未访问过，可由u到达，且经点u的距离比原来记载的更小，则进行更新
if(vis[i]==false && G[u][j]!=INT_MAX && p[u]+G[u][j]<dp[j]) {
dp[j] = dp[u] + G[u][j];
}
}
}
}
int n;
struct Node{
int u;
int d;
};
vector<Node> Adj[101];
int d[101];
bool vis[101] = {false};
void Dijkstra(int s) {
fill(d, d+n, INT_MAX);
d[s] = 0;
for(int i=0; i<n; i++) {
int u = -1, min = INT_MAX;
for(int j=0; j<n; j++) {
if(vis[j]==false && dp[j]<min) {
u = j;
min = dp[j];
}
}
if(u==-1) {
return;
}
vis[u] = true;
for(int j=0; j<Adj[u].size(); j++) {
struct Node node = Adj[u][j];
if(vis[node.u]==false && dp[node.u]!= INT_MAX && dp[node.u]+node.d < dp[j]) {
dp[node.u] = dp[u] + node.d;
}
}
}
}
以上，我们可以求出最短距离是多少。但如果我们要求出最短路径又该怎么办呢？
解决方法：我们可以加上一个pre数组，表示在到某点的最短路径上的前一个顶点
这个顶点更新的位置可以放在最短距离更新的地方
然后通过一个递归循环出最短路径
以下为递归函数，打印出最短路径
//s为起点，v为要访问的顶点
void DFS(int s, int v) {
//递归终止条件
if(s == v) {
printf("%d", s);
}
DFS(s, pre[v]);
printf("%d", v);
}
|