图基本概念
慢慢的，我们从一对一的结构（线性表）到一对多的结构（树）再到本篇讲的多对多的结构（图），元素之间的逻辑关系变得越来越复杂，没关系， 任何困难都难不倒，激情的程序猿！这篇文章，我们就以图为例，讨论一下图遍历方式，并引入优先搜索的感念，为下一篇（图的3大应用）做准备！ 首先呢，简单回顾一下图的相关概念，看你还记得多少：(以n个定点m条边的图为例)
弧头、弧尾、边、有向图、无向图、完全图(m=n(n-1)/2)、有向完全图(m=n(n-1))、稀疏图(m<nlogn)、权、出度、入度、 (m>n-1)回路（环）、 非连通图(m<n-1)、连通图、连通分量（极大连通子图）、生成树、强连通图、强连通分量!等相关概念~
然后，图的相关代码已经托管到Github上了~我是代码，快点我
另外呢，现在编程时想多尝试模版，所以大部分实现使用了模版，具体模版有没有真正起到多态的作用呢？哈哈，我心里也没底儿， 各位大神如果看到奇奇怪怪的模版参数，见谅一下，强忍着看看吧，见谅见谅~，当然能在最下面提出修改意见最好不过了！先行谢过！
数据结构定义
图常用的存储结构有2种：
- 1：邻接矩阵
- 2：邻接表
本文及下一节在设计的时候呢，就统一使用邻接矩阵作为图的数据结构： （无向图用1表示节点之间有连接，0表示无连接，有向图非0表示权重，∞表示无连接）
来，一起先看看数据结构的定义： 2个类，第一个是节点类，第二个是图类
#define MAX 10000
#define PMAX 10
#define PMIN 1
template <typename T>
class vertex
{
public:
T data;
int priority;//1-10
vertex(T num,int p):data(num),priority(p){}
void vprint(){cout<<"点：("<<data<<")的优先级为："<<priority<<endl;}
};
//有向图，用邻接矩阵的形式表示
template <typename T>
class Grap
{
public:
int n;//图的纬度
vector<vector<int> > G; //邻接矩阵, 0表示2点之间无直接连接，非0值表示2点之间的权重
vector<vertex<T> > V;//端点
vector<bool> visited; //遍历状态
vector<int> Tvisited; //遍历状态，专用于DFS拓扑排序算法
Grap(int m):n(m),G(m,vector<int>(m,0)),V(m,vertex<T>(m,10)),visited(m,false),Tvisited(m,0)
{
}
~Grap()
{
n=0;
}
void init();
void DFS_travel();
void BFS_travel();
void PFS_travel();//优先级优先搜索
void prime(int a);//最小生成树
void dijkstra(int a);//最优路径规划
void Tsort(int s);//拓扑排序
void TsortQueue();
void TsortDFS(int v,stack<vertex<T> > * st);//基于DFS 拓扑排序
void DFS(int v);
void PFS(int v);
int nextV(int self,int index);
void updatePriority(int s,int w);
void DUP(int s,int w);//dijkstra 最优路径规划优先级更新算法
void PUP(int s,int w);//prime 最小生成树优先级更新算法
};
有了上面数据结构的定义，接着我们就可以引入下面的算法了：
深度优先搜索(DFS)
深度优先搜索的基本原理类似树的先序遍历，使用递归搜索的方法简化编程。
步骤如下：
- 1：循环所有节点，有未遍历的节点进行DFS搜索，防止非联通图导致露点；
- 2：访问当前节点；
- 3：对当前节点的下一个节点，进行DFS搜索，若访问到最后一个节点，则返回
template <typename T>
void Grap<T>::DFS_travel()//深度优先搜索
{
for(int i=0;i<this->n;i++)
this->visited[i]=false;
for(int j=0;j<this->n;j++)
{
if(!this->visited[j])
DFS(j);
}
}
template <typename T>
void Grap<T>::DFS(int v)
{
this->visited[v]=true;
this->V[v].vprint();//visited
for(int num=nextV(v,0);num<this->n;num=nextV(v,num+1))
{
if(!this->visited[num])
DFS(num);
}
}
宽度优先搜索(BFS)
宽度优先搜索类似树的层序遍历，那么自然就想到了要使用队列进行辅助存储！
步骤如下：
- 1：循环所有节点，有未遍历的节点进行BFS搜索，防止非联通图导致露点；
- 2：访问当前节点并入队；
- 3：如果队不为空，出队，依次访问出队元素的邻接点并入队，直到队为空
template <typename T>
void Grap<T>::BFS_travel()//宽度优先搜索
{
for(int i=0;i<this->n;i++)
this->visited[i]=false;//init visited
queue<T> que;
for(int j=0;j<this->n;j++)//防止非联通图存在
{
if(!this->visited[j])
{
this->visited[j]=true;
this->V[j].vprint();//visited
que.push(j);
while(!que.empty())//一个联通图访问完毕
{
int v = que.front();que.pop();
for(int num=nextV(v,0);num<this->n;num=nextV(v,num+1))
{
if(!this->visited[num])
{
this->visited[num]=true;
this->V[num].vprint();//visited
que.push(num);
}
}
}
}
}
}
优先级优先搜索(PFS)
牛B的来了，下面提出归一化理论：
优先级优先搜索是对BFS和DFS的抽象，基本框架与上面一样，每遍历一个点需要更新所有点的优先级
但是呢，归一是有代价的，时间复杂度也从O(n+e)变成了 O(n^2) 哈哈，好在变化不大~
算法步骤如下：
- 1：循环所有节点，有未遍历的节点进行PFS搜索，防止非联通图导致露点；
- 2：访问当前节点
- 3：更新所有节点的优先级
- 4：找出该节点邻居节点中优先级最高的节点，更新当前节点，转至2
优先级搜索的重中之重便是updatePriority的编写了！
//优先级优先搜索
template <typename T>
void Grap<T>::PFS_travel()
{
for(int i=0;i<this->n;i++)
this->visited[i]=false;//init visited
int s=0;
int v=s;
do
{
if(!visited[v])
this->PFS(v);
}while(s!=(++v)%(this->n));//这样写好处：可以从任意点开始，遍历一次所有节点
}
template <typename T>
void Grap<T>::PFS(int v)
{
int minind=0;
int minpri=PMAX;
this->visited[v]=true;
(this->V[v]).vprint();
while(true)
{
minpri=PMAX;
for(int i1=nextV(v,0);i1<this->n;i1=nextV(v,i1+1))//更新所有邻接点的优先级
{
this->updatePriority(v,i1);
}
for(int i=0;i<this->n;i++)
{
if((!this->visited[i])&&(minpri>this->V[i].priority))// 1-10 值越小，优先级越高
{
minind=i;
minpri=this->V[i].priority;
}
}
if(this->visited[minind])
break;//优先级最高的已经访问过，说明所有节点访问完毕
else
{
this->visited[minind]=true;
(this->V[minind]).vprint();
v=minind;
}
}
}
总结
为什么说BFS和DFS是PFS的特殊情况呢？下面我们来分析：
共同点：
三者的基本流程均可以归纳为：
- 遍历->更新优先级（可选）->寻找最大优先级->下一步遍历
不同点：
PFS与BFS/DFS相比，流程中多了一个updatePriority的操作，其实呢，BFS/DFS都有自己的优先级，他们都有自己的个性：
DFS：“我认为孩子节点的优先级高于邻居节点！”
BFS：“我认为邻居节点的优先级高于孩子节点！”
BFS和DFS凭借自己的个性，把时间复杂度降为O(n+e),这一点是PFS只能羡慕的！
好了，到这里我们就可以看出3者之间的联系与区别了吧！其实PFS的好处不仅仅如此，后面一节图的3大应用，更加可以看出PFS的统一之处！
准备好长大嘴巴，尽情地吃鲸吧！！！
下一节：图的3大应用