图：
PAT (Advanced Level) Practice 用到图的存储方式，但没有用到图的算法的题目
1122 Hamiltonian Cycle (25)
1126 Eulerian Path (25)
1134 Vertex Cover (25)
1142 Maximal Clique (25)
1154 Vertex Coloring (25)
图的遍历：
1.定义：
- 顶点的度：与该顶点相连的边的条数
- 顶点和边量化的属性分别为点权和边权
2.存储
邻接矩阵：
- 对称的矩阵
- 若题目中不存在权值，G[i][j]=1表示顶点i和顶点j之间有边，G[i][j]=0表示顶点i和顶点j之间不存在边
- 如果存在权值，G[i][j]存放边权，不存在的边可以设边权为0、-1或是一个很大的数（INF=0x3f3f3f3f）
- 邻接矩阵只适用于顶点数目不太大（一般不超过1000）的题目
邻接表：
- 若只存放每条边的终点编号，vector 元素类型定义为 int 即可
vector<int> Adj[N];
Adj[u].push_back(v);
- 若同时存放终点编号和边权，可建立结构体，vector 元素类型定义为结构体
struct Node{
int v;
int weight;
};
vector<Node> Adj[N];
Adj[u].push_back({
v,weight});
DFS遍历图：
DFS的伪代码：
//注意：如果已知给定的图是一个连通图，则只需要一次ＤＦＳ就能完成遍历
DFS(u) {
//访问顶点u
vis[u]=true;//设置u已被访问
for(从u出发能到达的所有顶点v)//枚举从u出发可以到达的所有顶点v
if vis[v]==false //如果v未被访问
DFS(v);//递归访问v
}
DFSTrave(G) {
//遍历图G
for(G的所有顶点u) //对G的所有顶点u
if vis[u]==false //如果u未被访问
DFS(u); //访问u所在的连通块
}
定义：
定义maxn为最大顶点数，ＩＮＦ为无穷大
const int maxn=1000;//最大顶点数
const int INF=0x3f3f3f3f;//无穷大
DFS遍历邻接矩阵：
邻接矩阵
int n,G[maxn][maxn];
bool vis[maxn]= {
false};
void DFS(int u,int depth) {
//u为当前访问的顶点标号，depth为深度
vis[u]=true;//设置u已被访问
//如果需要对u进行一些操作，在这里进行
//对所有从u出发的分支顶点进行枚举
for(int v=0; v<n; v++) {
//对每个顶点v
if(vis[v]==false&&G[u][v]!=INF) {
//如果v未被访问，且u可到达v
DFS(v,depth+1);//访问v，深度加1
}
}
}
void DFSTrave() {
//遍历图G
for(int u=0; u<n; u++) {
//对每个顶点u
if(vis[u]==false) {
//如果u未被访问
DFS(u,1); //访问u和u所在的连通块，1表示初始为第一层
}
}
}
DFS遍历邻接表：
邻接表
vector<int> Adj[maxn];
int n;
bool vis[maxn]={
false};
void DFS(int u,int depth){
vis[u]=true;
for(int i=0;i<Adj[u].size();i++){
int v=Adj[u][i];
if(vis[v]==false){
DFS(v,depth+1);
}
}
}
void DFSTrave(){
for(int u=0;u<n;u++){
if(vis[u]==false){
DFS(u,1);
}
}
}
BFS遍历图：
BFS的伪代码：
BFS(u){
queue q;
将u入队;
inq[u]=true;
while(!q.empty()){
取出q的队首元素u进行访问；
for(从u出发可达的所有顶点v)
if(inq[v]=false){
将v入队；
inq[v]=true;
}
}
}
BFSTrave(G){
for(G的所有顶点u)
if(inq[u]==false){
BFS(u);
}
}
BFS遍历邻接矩阵：
邻接矩阵
int n,G[maxn][maxn];
bool inq[maxn]={
false};
void BFS(int u){
queue<int> q;
q.push(u);
inq[u]=true;
while(!q.empty()){
int u=q.front();
q.pop();
for(int v=0;v<n;v++){
if(inq[v]==false&&G[u][v]!=INF){
q.push(v);
inq[v]=true;
}
}
}
}
void BFSTrave(){
for(int u=0;u<n;u++){
if(inq[u]==false){
BFS(u);
}
}
}
BFS遍历邻接表：
邻接表
vector<int> Adj[MAXN];
int n;
bool inq[MAXN] = {
false};
void BFS(int u){
queue<int> q;
q.push(u);
inq[u] = true;
while (!q.empty()){
int u = q.front();
q.pop();
for (int i = 0; i < Adj[u].size(); i++){
int v = Adj[u][i];
if (!inq[v]){
q.push(v);
inq[v] = true;
}
}
}
}
void BFSTrave(){
for (int u = 0; u < n; u++)
if (!inq[u])
BFS(u);
}
输出结点层号（邻接表）：
- 与树的BFS遍历一样，可能需要输出连通块内所有其他顶点的层号
- 定义结构体来存放顶点层号
- 修改邻接表中的元素为Node（int->Node）
- 当前层号为L，它所有出边的终点的层号都为L+1
struct Node{
int v;
int level;
};
vector<Node> Adj[N];
void BFS(int s){
queue<Node> q;
Node start = {
s,0};
q.push(start);
inq[start.v] = true;
while(!q.empty()){
Node now = q.front();
q.pop();
int u = now.v;
for (int i = 0; i < Adj[u].size(); i++){
Node next = Adj[u][i];
next.level = now.level + 1;
if (!inq[next.v]){
q.push(next);
inq[next.v] = true;
}
}
}
}
京公网安备 11010502036488号