图

记顶点和边的集合位V和E，[V]和[E]表示顶点和边的个数，在V重，顶点被编号位0~[V]-1

1.邻接矩阵

• 邻接矩阵使用[V]*[V]的二维数组来表示图。g[i][j]表示的是顶点i和顶点j的关系，如果i和j之间有边相连，那么g[i][j]和g[j][i]就设为1，否则为0（无向图）

  
  无向图和对应的邻接矩阵

• 如果是有向图的话，i是起点，j是终点

  
  有向图和对应的邻接矩阵

• 带权图：g[i][j]表示的是顶点i到顶点j的边的权值。在边不存在的情况下，将其赋值为INF（较大的常数）

  
  带权图和对应的邻接矩阵
  

   

2.邻接表

3.图的搜索

title

n=3；输出No
思路：如果只用2种颜色，那么给定一个顶点的颜色后，和它相邻的顶点的颜色也就确定了。因此，选择任意一个顶点出发，依次确定相邻顶点的颜色，就可以判断是都可以被2种颜色染色了//用深搜。

这只是个模板【参考博客//cscec.com.cn/whpc_new/whal/201712/2775290.html】

#include<cstdio>
#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
using namespace std;
vector<int> G[1000];//图
int V;//顶点数
int color[1000];//顶点i的颜色（1 or -1）

//把顶点染成1或-1
bool dfs(int v,int c){
    color[v]=c;//把顶点v染成颜色c
    for(int i=0;i<G[i].size();i++){
        //如果相邻的顶点同色，则返回false
        if(color[G[v][i]]==c)
            return false;
        //如果相邻的顶点未被染色，则染成-c
        if(color[G[v][i]]==0&&!dfs(G[v][i],-c))
            return false; 
    }
    //如果所有顶点都染过色了，则返回true
    return true; 
} 

void solve(){
    for(int i=0;i<V;i++){
        if(color[i]==0){
            //如果顶点i还没被染色，则染成1
            if(!dfs(i,1)){
                printf("No\n");
                return ;
            } 
        }
    }
    printf("Yes\n");
}