图（Graph是一种复杂的非线性结构它可以描述数据间的关系被广泛使用。

图 G 由两个集合 V 和 E 组成记为 。V是顶点的有穷非空集合E是边的集合。通常也将 G 的顶点集和边集表示为 V(G) 和 E(G)。其中E(G)可以是空集如果它是空集那么 G 只有顶点。

图的定义和概念

有向图边上有箭头只能从箭头的引出的结点到被指向的结点不能逆着箭头走。

无向图边上无箭头可以随便走。

结点的度无向图中与结点相连的边的数量。

结点的入度有向图中以结点为终点的边的数量。

结点的出度有向图中以结点为起点的边的数量。

权值可以理解为边的长度。

连通如果结点 U 和 V 之间通过若干个边和结点能从 U 到达 V则称 U 和 V 连通。

回路起点和终点相同的路径。

完全图一个 n 阶的完全无向图含有 n*(n-1)/2 条边一个 n 阶的完全有向图含有 n*(n-1) 条边。

稠密图一个边数接近完全图的图。

稀疏图一个边数远少于完全图的图。

强连通分量有向图中任意两点都连通的最大子图。特殊的一个点也算一个强连通分量。

图的存储结构

二维数组邻接矩阵存储

定义 int G[101][101];

G[i][j] 的值表示点 i 到点 j 的边的权值定义如下

G[i][j]{1或权值0或无穷

深度优先和广度优先遍历

从图中某一顶点出发系统的访问图中所有顶点并且每个顶点只被访问一次这种操作叫做图的遍历。为了不重复访问我们使用一个数组 visit[] 被访问过就变成 true反之 false。这两种方法（广度和深度优先遍历时间复杂度都是 O(n*n)。

深度优先遍历

深度优先遍历和深度优先搜索相似它是先访问一个点再访问与这个点相连的所有点当这个点所有相连的点访问完再退回下一个点。

广度优先遍历

它基本不用和广度优先搜索相似和深度优先遍历相似这里不讲解。

一笔画问题

如果一个图存在一笔画则一笔画的路径叫做欧拉路如果起点和终点相同则这个路径叫欧拉回路。

奇点是与一个点相连的边数是奇数的点。我们有如下两个定理

（1存在欧拉路的条件图是连通的且有且只有两个奇点。

（2存在欧拉回路的条件图是联通的且有0个奇点。

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int p[N],q[N];
int n,m;
int sum=0,flag=0;
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        q[a]++;//由于是无向图需要把所有边加上
        q[b]++;
        a=find(a),b=find(b);
        if(a!=b) p[a]=b;
    }
    for(int i=1;i<=n;i++) 
        if(p[i]==i) sum++;
       if(sum==1)
       {
           for(int i=1;i<=n;i++)
           {
               if(q[i]%2!=0)
                   flag++;
           }
       }
     else {cout<<"N"<<endl;return 0;}
     if(flag==0 || flag==2) cout<<"Y"<<endl;//一笔画的规律（奇数点个数为0或者2
     else cout<<"N"<<endl;
    return 0;
}

例题-图的遍历

图的遍历

题目描述

给出 N 个点M条边的有向图对于每个点 v求 A(v) 表示从点 v 出发能到达的编号最大的点。

输入格式

第 1 行 2 个整数 N,M表示点数和边数。

接下来 M 行每行 2 个整数 Ui,Vi表示边 (Ui,Vi)。点用 1,2,.....,N 编号。

输出格式

一行 N 个整数 A(1),A(2),......,A(N)。

样例 #1

4 3
1 2
2 4
4 3

样例输入 #1

样例输出 #1

4 4 3 4

按题目来每次考虑每个点可以到达点编号最大的点不如考虑较大的点可以反向到达哪些点

循环从N到1则每个点i能访问到的结点的A值都是i

每个点访问一次这个A值就是最优的因为之后如果再访问到这个结点那么答案肯定没当前大了

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; //vector存图 

void dfs(int x, int d) {
    if(A[x]) return; //访问过 
    A[x] = d;
    for(int i=0; i<G[x].size(); i++)
        dfs(G[x][i], d);
}

int main() {
    int u, v;
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; i++) {
        scanf("%d%d", &u, &v);
        G[v].push_back(u); //反向建边 
    }
    for(int i=N; i; i--) dfs(i, i); 
    for(int i=1; i<=N; i++) printf("%d ", A[i]);
    printf("\n");
    return 0;
}