图的基本概念
1.图的定义
由顶点和边组成的集合，G=(V,E)
2.基本概念
邻接点：
对于无向图u v来说，uv互为邻接点
对于有向图u->v来说，v是u的邻接点，但u不是v的临界点
路径：
一个顶点到另一个顶点所经过的顶点构成的序列
有向图：
边是有方向的，单项
无向图：
边是无方向的，双向
有权图：
边有实际意义，也就是权重
无权图：
边无实际意义，无权重，有边置1，无边置0
完全图：
任意两个顶点之间都有两边
连通图：
任意两个顶点之间都有路径
稀疏图：
边远远小于顶点数(n<<m)
稠密图：
边远远大于顶点数(n>>m)
图的存储方式
前言：
图的常见存储方式有
邻接矩阵、邻接表、链式前向星
邻接多重表、十字链表
1.邻接矩阵
<注意>
邻接矩阵的大小至于顶点数有关，为n方，于变数m无关
邻接矩阵的优点是可以在O(1)的时间复杂度下快速找到邻接点，直接g[u] [v]==1?
缺点也很明显，有效边和无效边都存储，太占空间了，适用于稠密图，这样无效边就会变小，不会浪费空间了
遍历n个顶点的邻接点的时间复杂度是O(n^2)
无向无权图
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+10;
//g[i][j]的状态时1/0 1表示ij之间右边 0表示ij之间没边
int g[N][N];//邻接矩阵
int main() {
//输入n个顶点，m条边 的无向无权图
int n,m;cin>>n>>m;
//输入边，初始化邻接矩阵
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
/* 1 2 3 4 5 6 7
*1 0 1 1 1 0 0 0
*2 1 0 0 0 1 0 0
*3 1 0 0 0 0 0 0
*4 1 0 0 0 0 1 0
*5 0 1 0 0 0 0 0
*6 0 0 0 1 0 0 1
*7 0 0 0 0 0 1 0
* 可以发现矩阵是对称的却其中非零元素个数是2m个
* */
for(int i=1;i<=n;i++){
cout<<i<<"的邻接点为：";
for(int j=1;j<=n;j++){
if(g[i][j]) cout<<j<<" ";
}cout<<endl;
}
return 0;
}
有向无权图
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+10;
int g[N][N];//邻接矩阵
int main() {
//输入n个顶点，m条边 的无向无权图
int n,m;cin>>n>>m;
//输入边，初始化邻接矩阵
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=1;
}
/* 1 2 3 4 5 6 7
*1 0 1 1 1 0 0 0
*2 0 0 0 0 1 0 0
*3 0 0 0 0 0 0 0
*4 0 0 0 0 0 1 0
*5 0 0 0 0 0 0 0
*6 0 0 0 0 0 0 0
*7 0 0 0 0 0 1 0
* 可以发现矩阵是非对称的却其中非零元素个数是m个
* */
for(int i=1;i<=n;i++){
cout<<i<<"的邻接点为：";
for(int j=1;j<=n;j++){
if(g[i][j]) cout<<j<<" ";
}cout<<endl;
}
return 0;
}
2.邻接表
<注意>
邻接表不会存储无效的边，所以它不会浪费空间
但是它无法直接定位邻接点，邻接矩阵能直接定位邻接点时它申请矩阵的横纵坐标表示的就是顶点的值，直接g[i] [j] 判断是否为1就可以判断j是否是i的邻接点，但是邻接表中的二维vector数组的横纵坐标表示的不是顶点的值，所无法直接定位，而邻接表用的是二维静态vector数组，u顶点的vector[u]数组里面放的都是u的邻接点，不是邻接点不放
因为邻接表采用的是二维静态vector数组，所以它的空间大小也于m边数量无关，至于顶点数n有关
无向无权图
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+10;
//二维静态vector数组 邻接表 每个vector[u] 里面都是存的u的邻接点
vector<int> g[N];
int main() {
//输入n个顶点，m条边 的无向无权图
int n,m;cin>>n>>m;
//输入边，初始化邻接矩阵
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
//无向图 邻接表
g[u].push_back(v);g[v].push_back(u);
}
/*
* vector<int> g[1] 2 3 4
* vector<int> g[2] 1
* vector<int> g[3] 1
* vector<int> g[4] 1 6
* vector<int> g[5] 2
* vector<int> g[6] 4 7
* vector<int> g[7] 6
* */
for(int i=1;i<=n;i++){
cout<<i<<"的邻接点为：";
for(int j=0;j<g[i].size();j++){
//邻接表里面存的就是邻接点
cout<<g[i][j]<<" ";
}cout<<endl;
}
return 0;
}
有向无权图
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+10;
//二维静态vector数组 邻接表 每个vector[u] 里面都是存的u的邻接点
vector<int> g[N];
int main() {
//输入n个顶点，m条边 的无向无权图
int n,m;cin>>n>>m;
//输入边，初始化邻接矩阵
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
//有向图 邻接表
g[u].push_back(v);;
}
/*
* vector<int> g[1] 2 3 4
* vector<int> g[2] 1
* vector<int> g[3] 1
* vector<int> g[4] 1 6
* vector<int> g[5] 2
* vector<int> g[6] 4 7
* vector<int> g[7] 6
* */
for(int i=1;i<=n;i++){
cout<<i<<"的邻接点为：";
for(int j=0;j<g[i].size();j++){
//邻接表里面存的就是邻接点
cout<<g[i][j]<<" ";
}cout<<endl;
}
return 0;
}
总结：
邻接矩阵中，行列坐标表示顶点，数组值表示是否存在邻接点
邻接表中，行坐标表示顶点，行坐标的vector数组中存储的是它的邻接点
图论算法
DFS
1.DFS（栈）
DFS就是沿着一条路走到黑，知道路没有了再回头，栈可以后进先搜
用邻接矩阵实现
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N=1e4+10;
int g[N][N],n,m;
//标记数组，用来标记已经入栈过的顶点
bool vis[N];
void DFS(int s){
stack<int> stk;
//起始点入栈，入栈就标记
stk.push(s);vis[s]=true;
while(!stk.empty()){
int cur=stk.top();stk.pop();
cout<<cur<<" ";
//把栈顶顶点所有的邻接点入栈
//邻接矩阵
for(int i=1;i<=n;i++){
//入栈过的就不能再搜了
if(!vis[i]&&g[cur][i]) stk.push(i),vis[i]=true;
}
//邻接表
for(int i=0;i<g[cur].size();i++){
//入栈过的就不能再搜了
if(!vis[i]) stk.push(g[cur][i]),vis[g[cur][i]]=ture;
}
}
}
int main() {
cin>>n>>m;
int s;cin>>s;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
DFS(s);
return 0;
}
入栈就标记，出栈就搜邻接点，没被搜过的入栈
2.DFS(递归)
递归分为两部分，搜索部分和回溯部分
#include <iostream>
using namespace std;
const int N=1e4+10;
int n,m,g[N][N];
bool vis[N];
//dfs(int status)状态，s为搜索状态
void dfs(int s){//正在搜索s
//正在搜索的先输出
cout<<s<<" ";
//找当前搜索状态的邻接点
for(int i=1;i<=n;i++){
if(g[s][i]&&!vis[i]){
vis[i]=1;dfs(i);
}
}
}
/*
* cout<<1 2 3 5 7 6 8 4
* vis 1 3 5 6 8 4
* 1.DFS(1) cout<<1 i=2 vis[2]=1 DFS(2) i=7 vis[7]=1 DFS(7) i=8 vis[8]=1 DFS(8)X
* 2.DFS(8) cout<<8 i=4 vis[4]=1 DFS(4)X
* 3.DFS(4) cout<<4 X
* 2.DFS(7) cout<<7 i=6 vis[6]=1 DFS(6)X
* 3.DFS(6) cout<<6 X
* 2.DFS(2) cout<<2 i=3 vis[3]=1 DFS(3)X
* 3.DFS(3) cout<<3 i=5 vis[5]=1 DFS(5)X
* 4.DFS(5) cout<<5 X
* */
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
int s;cin>>s;
//启动dfs前要把初始状态标记
vis[s]=1;
dfs(s);//搜索的初始状态
return 0;
}
3.连通块问题(求连通块数量)
循环深搜
#include <iostream>
using namespace std;
const int N=1e4+10;
int n,m,g[N][N];
bool vis[N];
//dfs(int status)状态，s为搜索状态
void dfs(int s){//正在搜索s
for(int i=1;i<=n;i++){
if(g[s][i]&&!vis[i]){
vis[i]=1;dfs(i);
}
}
}
int main(){
int cnt=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
//循环深搜
for(int i=1;i<=n;i++){
//只要没被标记就深搜
if(!vis[i]){
vis[i]=true;
dfs(i);
//深搜一次就cnt++
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
4.DFS求无权图最短路径长度
#include <iostream>
using namespace std;
const int N=1e4+10;
int n,m,s,t,ans=0,g[N][N];
bool vis[N];
//dfs(int status)状态，s为搜索状态
void dfs(int s,int depth){
if(s==t){
ans=min(ans,depth-1);return;
}
for(int i=1;i<=n;i++){
if(g[s][i]&&!vis[i]){
vis[i]=1;
dfs(i,depth+1);
//回溯阶段把标记取消，这样可以多次在不同路径找到终点，从而找到最短路径
vis[i]=0;
}
}
}
/* vis 1
* s=1 t=4
* 1.dfs(1) ans=0 i=1 vis[1]=1 dfs(2) vis[2]=0 i=5 vis[5]=1 dfs(5) vis[5]=0 X
* 2.dfs(5) ans=0 i=4 vis[4]=1 dfs(4) vis[4]=0 X
* 3.dfs(4) ans=2 X
* 2.dfs(2) ans=0 i=3 vis[3]=1 dfs(3) vis[3]=0 X
* 3.dfs(3) ans=0 i=4 vis[4]=1 dfs(4) vis[4]=0 X
* 4.dfs(4) ans=3 X
* cout<<ans=2
* */
int main(){
int cnt=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
cin>>s>>t;//最短路径的起点和终点
vis[s]=true;
dfs(s,1);
cout<<ans<<endl;
return 0;
}
dfs解决最短路问题时间复杂度：O(2^n)
组合问题时间复杂度为：O(2^n)，n最多为25，算法不会超时
排列问题时间复杂度为：O(n!)，n最多为11，算法不会超时
不会产生排列情况
5.DFS求无权图最短路径
#include <iostream>
#include <vector>
using namespace std;
const int N=128;
vector<char> path,res;
char s,t;
bool vis[N];
int m,ans=0x3f3f3f3f,g[N][N],k;
void dfs(char s,int depth){
if(s==t) {
if(ans>depth-1){
ans=depth-1;
res=path;
}
return ;
}
for(char c='A';c<='Z';c++){
if(!vis[c]&&g[s][c]){
vis[c]=true;
path.push_back(c);
dfs(c,depth+1);
path.pop_back();
vis[c]=false;
}
}
}
/*
* vis A
* path A
* res A E F
* 1.dfs(A) c=B vis[B]=1 push B dfs(B) c=E vis[E]=1 push E dfs(E) c=F vis[F]=1 push F dfs(F)
* 2.dfs(F) ans=2 res X
* 2.dfs(E) c=D vis[D]=1 push D dfs(D) X
* 3.dfs(D) c=C vis[C]=1 push C dfs(C) X
* 4.dfs(C) c=B vis[B]=1 push B dfs(B) X
* 5.dfs(B) X
* 2.dfs(B) c=C vis[C]=1 push C dfs(C) X
* 3.dfs(C) c=D vis[D]=1 push D dfs(D) X
* 4.dfs(D) c=E vis[E]=1 push E dfs(E) pop c=F vis[F]=1 push F dfs(F) pop X
* 5.dfs(F) ans=4 res X
* 5.dfs(E) c=F vis[F]=1 push F dfs(F) pop X
* 6.dfs(F) ans=5 res X
* */
int main(){
cin>>m;
for(int i=1;i<=m;i++){
char u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
cin>>s>>t;
vis[s]=true;
path.push_back(s);
dfs(s,1);
cout<<"最短路长度为"<<ans<<endl;
cout<<"最短路径为：";
for(int i=0;i<res.size()-1;i++){
printf("%c->",res[i]);
}
printf("%c",res[res.size()-1]);
return 0;
}
BFS
1.BFS输出图中元素
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1e4+10;
int g[N][N],n,m,st;
bool vis[N];
//input:
//1 2
//2 3
//3 4
//1 9
//9 5
//5 6
//6 7
//7 4
//1 8
//8 6
//1
//output:
//1 2 8 9 3 6 5 4 7
void bfs(int s){
queue<int> q;
q.push(s);vis[s]=1;
while(!q.empty()){
int cur=q.front();cout<<cur<<" ";q.pop();
for(int i=1;i<=n;i++){
if(!vis[i]&&g[cur][i]){
q.push(i);vis[i]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
cin>>st;
bfs(st);
return 0;
}
2.BFS解决连通块问题
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1e4+10;
int g[N][N],n,m,cnt;
bool vis[N];
//input:
//8 5
//
//1 2
//2 3
//4 5
//6 7
//6 8
//
//ouput:
//3
void bfs(int s){
queue<int> q;
q.push(s);
while(!q.empty()){
int cur=q.front();q.pop();
for(int i=1;i<=n;i++){
if(!vis[i]&&g[cur][i]){
q.push(i);vis[i]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
bfs(i);
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
3.BFS求最短路
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1e4+10;
struct node{
int id,depth;
};
int g[N][N],n,m,st,t,ans;
int pre[N];
bool vis[N];
//9 10
//
//1 2
//2 3
//3 4
//1 9
//9 5
//5 6
//6 7
//7 4
//1 8
//8 6
//
//1 7
//ouput:
//3
//1 8 6 7
//bfs求最短路的时间复杂度是O(n+m)
void bfs(node s){//由于bfs不是递归，无法将层数和搜索状态绑定，只能使用结构体将搜索状态和层数绑定
queue<node> q;
q.push(s);vis[s.id]=1;
while(!q.empty()){
node cur=q.front();q.pop();
if(cur.id==t){
ans=cur.depth-1;
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]&&g[cur.id][i]){
q.push({i,cur.depth+1});
pre[i]=cur.id;
vis[i]=1;
}
}
}
}
void getpath(int s){
if(!s) return ;
getpath(pre[s]);
cout<<s<<" ";
}
//1.g(7) g(6) 7
//2.g(6) g(8) 6
//3.g(8) g(1) 8
//4.g(1) g(0) 1
//5.g(0) X
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u][v]=g[v][u]=1;
}
cin>>st>>t;
bfs({st,1});
cout<<ans<<endl;
getpath(t);
return 0;
}
4.迷宫问题
DFS解决-能否走出迷宫
#include <iostream>
using namespace std;
const int N=1e4+10;
int n,m,sx,sy,tx,ty;
char g[N][N];//二维迷宫
bool vis[N][N],flag;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
//8 8
//*****...
//*.S...**
//*****.**
//*****..*
//*T..**.*
//.**.**.*
//..*....*
//...*****
//YES
void dfs(int px,int py){
if(px==tx&&py==ty){//当前状态为终点
flag=true;
return ;
}
//向着邻接点DFS
for(int i=0;i<4;i++){
int bx=px+dx[i],by=py+dy[i];
//合法性判断
if(bx<1||bx>n||by<1||by>m||g[bx][by]=='*'||vis[bx][by]) continue;
vis[bx][by]=1;
dfs(bx,by);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(g[i][j]=='S') sx=i,sy=j;
else if(g[i][j]=='T') tx=i,ty=j;
}
}
vis[sx][sy]=1;
dfs(sx,sy);
if(flag){
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
return 0;
}
BFS解决-能否走出迷宫
#include <iostream>
#include <queue>
#include<Windows.h>
using namespace std;
const int N=1e4+10;
int n,m,sx,sy,tx,ty;
char g[N][N];//二维迷宫
bool vis[N][N],flag;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int x,y,depth;
};
//8 8
//*****...
//*.S...**
//*****.**
//*****..*
//*T..**.*
//.**.**.*
//..*....*
//...*****
//YES
void bfs(node s){
queue<node> q;
q.push(s);vis[s.x][s.y]=1;
while(!q.empty()){
node cur=q.front();q.pop();//当前搜索状态
if(cur.x==tx&&cur.y==ty){
flag=true;
cout<<cur.depth-1<<endl;
return;
}
for(int i=0;i<4;i++){
int bx=cur.x+dx[i],by=cur.y+dy[i];
if(bx<1||bx>n||by<1||by>m||g[bx][by]=='*'||vis[bx][by]) continue;
vis[bx][by]=1;
q.push({bx,by,cur.depth+1});
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='S') sx=i,sy=j;
else if(g[i][j]=='T') tx=i,ty=j;
}
}
bfs({sx,sy,1});
if(flag){
cout<<"YES"<<endl;
}
else
cout<<"NO"<<endl;
return 0;
}
