一、图的基本类型

1.无向图：每条边都是无方向的

2.有向图：每条边都是有方向的

3.完全图：任意两个顶点都存在一个边

ㅤㅤㅤㅤ完全无向图ㅤㅤㅤㅤㅤㅤ完全有向图

$n$个顶点的完全无向图有$n(n-1)/2$条边

$n$个顶点的完全有向图有$n(n-1)$条边（是无向图的两倍）

无向图$G$中顶点数为$n$，则图至少有$0$条边，至多有$n(n-1)/2$条边。若$G$为有向图，则至少有$0$条边，至多有$n(n-1)/2$条边。

连通图：无向图中任意两个点都有路径可达

ㅤㅤㅤㅤ是连通图ㅤㅤㅤㅤㅤㅤㅤㅤㅤ不是连通图

二、邻接矩阵存储图

无向图：

无向图的左上半部分与右下半部分对称

顶点$i$的度$=$第$i$行（列）中$1$的个数

有向图：

有向图不一定对称

顶点的出度$=$第$i$行元素之和，顶点的入度$=$第$i$列元素之和，图的度$=1$的个数$*2$

总结：

无向图可以从v1走到v2，也可以从v2走到v1，所以a[v1][v2]和a[v2][v1]都要存

有向图可以从v1走到v2，但不能从v2走到v1，因为有向图是有方向的，所以只用存a[v1][v2]

三、邻接表（链式前向星）存图

无向图：

有向图：

一般来说，邻接表是用数组模拟链表的方式进行存储的，当然也可以用$vector$

四、图的遍历

一个有$n$个结点的无向连通图，这些结点以编号：$1、2、……n$进行编号，现给出结点间的连接关系。请以结点$1$为起点，优先访问小编号结点的顺序遍历并输出该图。

深度优先搜索（$dfs$）

我们只需要用邻接矩阵存图，然后从$1$号结点开始搜索。搜索这个结点的时候，先标记走过，然后输出，再向其他点搜索，如果该点没有访问过，则搜索该点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,e,a[20][20],x,y;
bool b[20];
void dfs(ll x1) {
    b[x1]=true;
    printf("%lld ",x1);
    //向其他点搜索
    for(ll i=1; i<=n; i++) {
        //如果没有走过而且可以走
        if(a[x1][i]==1&&!b[i]) dfs(i);
    }
}
int main() {
    scanf("%lld%lld",&n,&e);
    for(ll i=1; i<=e; i++) {
        scanf("%lld%lld",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    dfs(1);
    return 0;
}

广度优先搜索($bfs$)

用邻接矩阵存储图，然后用$b$数组存储该点是否访问过，这里我使用$STL$中的队列$queue$来标记。搜索的过程我就不多说了，跟深搜是差不多的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,e,x,y,a[20][20];
bool b[20];
queue<ll> q;
int main() {
    scanf("%lld%lld",&n,&e);
    for(ll i=1; i<=e; i++) {
        scanf("%lld%lld",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    b[1]=true;
    q.push(1);
    printf("1 ");
    while(!q.empty()) {
        //向其他点搜索
        for(ll i=1; i<=n; i++) {
            //如果没有走过而且可以走
            if(!b[i]&&a[q.front()][i]==1) {
                q.push(i);
                b[i]=true;
                printf("%lld ",i);
            }
        }
        q.pop();
    }
    return 0;
}