c++数据结构-图（详解附算法代码，一看就懂）

图（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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39