GF2026C1图的定义、存储和遍历

• 导航页

……

---

前言

点击关闭/展开(推荐查看完点击)

讲完单调队列开始讲图论了.

---

$dxd$的讲义

---

图分为有向图和无向图、无权图和加权图、稀疏图和稠密图、完全图和补图、树和森林、图的生成树和生成森林、平面图、平面图。

例题:图的m着色问题

---

开始编程前，首先先学会建图。

#include<iostream>
using namespace std;
int g[1001][1001],n,m,u,v;
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>u>>v;
    g[u][v]=1;
    g[v][u]=1;//若为无向图，则一条边需要当两条边来存储
  }
}

遍历图有两种常见入门方法:

深搜

void dfs(int u){
  cout<<u<<" ";//输出当前访问节点，或根据题意对节点进行相应处理
  vis[u]=true;//标记已访问
  for(int i=1;i<=n;i++){
    if(g[u][i]==1&&!vis[i]) dfs(i);//查找下一个邻接点
  }
}

广搜

void bfs(int s){
  queue<int> q;
  q.push(s);
  vis[s]=true;
  while(!q.empty()){
    int u=q.front();
    q.pop();
    cout<<u<<" ";//输出当前访问节点，或根据题意对节点进行相应处理
    for(int i=1;i<=n;i++){
      if(g[u][i]==1&&!vis[i]){//查找下一个邻接点
        q.push(i);
        vis[i]=true;//标记已访问
        }
      }
    }
}

可分别采用这两种方式，查看同一个图的节点访问顺序。

相邻矩阵存储方式在建图和遍历中使用方便，通过标记进行增边删边的方式也很快捷。但是这种方式消耗的空间非常大，且空间的利用率并不高。