2019-05-03 图的知识点
2019-05-03 本文已影响0人
桐桑入梦
听雨声
小知识点：
1. G=V+E
2. V不可以是空集，图不可以是空图
3. 有向图边使用<a,b>表示，无向图使用（a,b）表示
4. 简单图：不存在重复边；不存在顶点到自身的边；
5. 多重图定义和简单图相反
6. 完全图：注意有向图和无向图的区别，有向图有n(n-1）条弧，无向图有n(n-1)/2条
7. 生成子图：指的是一个图的子图，它们两者的顶点数量相同，两个图的阶相同
8. 对于G，并不是任何V和E的子集都可以构成图（因为边关联的顶点可能不在顶点集合中）
对于无向图：
10. 连通：是对于某两个顶点而言的，顶点a,b之间有路径存在，那么a,b是连通的
11. 连通图：是对于任意两个顶点而言的，如果任意两个顶点a,b之间有路径存在，那么图G是连通图
12. 连通分量：指的是无向图中的极大连通子图
（可以理解为图中可以相互连通的点的结合以及他们之间的边的集合，一个图往往可以分成多个
这样的集合）
13. 极大连通子图和极小连通子图区别：
极大连通子图是无向图的连通分量，我们设极大连通子图为G1(V1,E1),那么E1的元素的个数一定大于|V1|-1
极小连通子图既要保存图的连通，又要使得边数最小，我们假设极小连通子图为G2（V2,E2），那么一定有：E2元素个数=|V2|-1
对于有向图：
14. 若从顶点a到顶点b有路径，且从顶点b到顶点a有路径，则顶点a,b是强连通的
（连通是对某连个顶点而言的）
15. 若任何一对顶点都是强连通的，那么此图是强连通图
（对任意两个顶点而言的）
16. 强连通分量：极大强连通子图
17. 有向图讨论强连通性，强连通分量，无向图讨论连通性，连通分量
生成树和生成森林:
18. 连通图的生成树：包含n个顶点，n-1条边的极小连通子图
19. 非连通图的生成森林:每一个连通分量的生成树构成森林
顶点的度：
degree:度 in:入 out:出
TD（v）:顶点v的度 ID:入度 OD：出度
20. n个顶点e条边的无向图中：
TD(V1)+TD(V2)+...+TD(Vn)=2e
21. n个顶点e条边的无向图中：
TD(V1)+TD(V2)+...+TD(Vn)=2e
ID(V1)+ID(V2)+...+ID(Vn)=e
OD(V1)+OD(V2)+...+OD(Vn)=e
22. 边可以有权值，比如表示路费
23. 稀疏图边少，稠密图边比较多
24. 路径长度指的是两个顶点a,b之间的路径的边的个数
25. n个顶点的图，如果有某一条路径长度大于n-1，一定存在环
26. 简单路径：路径序列中，顶点不会重复出现
27. 简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不会重复出现的回路
无环有向图
在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式：
((a+b)b(c+d)+(c+d)e)(c+d)*e
使用二叉树描述容易出现重复，使用有向无环图可以减少重复
二叉树描述
有向无环图描述
eg.有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。这样两个问题都是可以通过对有向图进行拓扑排序和关键路径操作来解决的。
附加几个无环有向图辅助理解：
eg.最后这个DAG图比较特殊，我们如果让她从1---n进行编号，那么可以发现任意的边<i,j>需要满足i<j,如果使用邻接矩阵进行存储，那么可以使用三角矩阵进行存储。对于一个一般的有向无环图DAG,如果想使用三角矩阵进行存储，可以修改结点的编号，然后存储。
思考：如果修改结点的编号？首先进行拓扑排序，然后得到一个序列，把这个序列的第一个结点编号修改为1，第二个修改为1，以此类推。
习题中的问题：
1.路径的定义
B是错误的，因为一条路径可以存在相同的顶点，如果不存在相同的顶点，那么是简单路径，C中也是可以有相同的边。因此可以知道，一条路径可以使用顶点序列进行描述，也可以使用顶点和相邻顶点的序偶构成的边进行描述。
D需要满足图是连通图的前提下。
注意是任何情况！！！
题目意思是说是有多少种不同的生成树？嗯嗯
小知识点：
1.一个无向图有n个顶点和n-1条边，在最好的情况下，可以形成一个连通图并且没有回路，一个n个顶点的无向图在没有回路的前提下最多可以有n-1条边，超过n-1条边一定有回路。
2.DFS可以访问一个无向图的所有结点，那么这个无向图只要满足是连通图即可。
3.极大连通子图：如果图本来就不是连通的，那么每一个子部分包含他本身所有的顶点和边，那么她就是极大连通子图。
图的存储结构
eg.可以使用邻接矩阵存储有向图和无向图
顶点的度：
这里是把标记的部分累加起来，计算一个顶点的度，显然是针对一个无向图而言的。（这里可以也可以累加列进行计算）
存储小技巧：
无向图的邻接矩阵是对称的矩阵，因为无向图的邻接矩阵是对称矩阵，可以使用上（下）三角矩阵存储上半部分。
对于一个网：
eg.行和列相同的结点权值为0，有时候也会把这个设置成为无穷大
eg.有时候可以使用0，而不是无穷大
邻接矩阵的小知识点：
1.容易确定是否有边，但是确定边的数量需要O（n^2）；
2.若A为邻接矩阵，A^n 的元素A^n[i][j]等于顶点i到顶点j的长度为n的路径的数量.这里可以是有向图或者无向图.这里可以用弗洛伊德算法去理解.
邻接矩阵使用A,D表示的不同
例子：
题目：https://www.luogu.org/problemnew/show/P3758
题解：https://www.cnblogs.com/Dxy0310/p/9840451.html
加了一点点注释：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 39
#define maxm
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
return x*f;
}
int mp[maxn][maxn],B[maxn][maxn],C[maxn][maxn];
int n,m,k,ans,tot,cnt,t,p;
/*A=AB*/
void Martix_mul(int A[maxn][maxn],int B[maxn][maxn])
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
C[i][j]+=A[i][k]*B[k][j],C[i][j]%=p;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
A[i][j]=C[i][j],C[i][j]=0;
}
void Quick_mul(int b)
{
while(b)
{
if(b&1)
Martix_mul(B,mp);
Martix_mul(mp,mp);
b>>=1;
}
}
int main()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
n=read(),m=read(),p=2017;
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
mp[x][y]=mp[y][x]=1; //原来的一个无向图修改为有向图
}
for(int i=1;i<=n+1;i++)
{
mp[i][i]=1;
mp[i][n+1]=1;
B[i][i]=1; //初始化为单位矩阵
}
t=read();
++n;
Quick_mul(t);
for(int i=1;i<=n;i++)
ans+=B[1][i],ans%=p;
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType Vex[MaxVertexNum];
EdgeType Edge[MaxVertexNum][MaxVertexNum];
int vexnum,arcnum;
};
邻接表存储特点：
- 若无向图G，空间复杂度O（2|E|+|V|）.若有向图G，空间复杂度O（|E|+|V|）
- 使用邻接表确定两顶点之间是否有边效率低于邻接矩阵
- 计算顶点出度方便，入度麻烦
- 逆邻接表计算入度方便，出度麻烦
/*邻接表的存储结构*/
#define MaxVertexNum 100
typedef char VertexType;
typedef struct ArcNode{ //边结点ArcNode
int adjvex;
struct ArchNode *next;
}ArcNode;
typedef struct VNode{ //顶点VNode
VertexType data;
ArcNode *firstedge;
}VNode,AdjList[MaxVertexNum];
//AdjList是结构体数组类型，等价于struct VNode AdjList[MaxVertexNum]
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum;
}ALGraph;//图
引入十字链表的原因
十字链表
eg.边表结点后面两个元素的注释中的“指向”,指的是指针，自己理解容易搞混了。
十字链表存储的形式不唯一，但是他们表示的图都是确定的。
十字链表整理：
- 十字链表是有向图的一种链式存储结构，而顶点结点之间是顺序存储
- 入度和出度容易计算
- 每一个顶点和每一个弧都对应一个结点
/*十字链表的存储结构(针对有向图)*/
#define MaxVertexNum 100
typedef char VertexType;
//弧尾结点是起点，弧头结点是终点
typedef struct ArcNode{ //边结点
int tailvex,headvex; //弧尾结点，弧头结点
struct ArcNode *hlink,*tlink;
//tlink指向“和弧尾结点（起点）相同的下一条边”
//hlink指向“和弧头结点（终点）相同的下一条边”
}ArcNode;
typedef struct VNode{
VertexType data; //图中顶点的数据
ArcNode *firstin,*firstout;
//入边表的头指针和出边表的头指针
}VNode;
邻接多重表（针对无向图）
删除一条邻接多重表的边
临界多重表整理：
- 想要删除一个邻接多重表的边，需要修改两次指针，然后释放结点即可。
- 每一个边只有一个结点
#define MaxVertexNum 100
typedef struct ArcNode{ //边表结点
bool mark; //访问标记，记录这条边是否搜索过
int ivex,jvex; //弧的两个顶点
struct ArcNode *ilink,*jlink; //分别指向两个顶点的下一条边
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstedge; //指向第一条依附该顶点的边
};
typedef struct{
VNode adjmulist[MaxVertexNum]; //多重邻接表
int vexnum,arcnum; //顶点数和边数
}AMLGraph;
图的存储结构汇总：
1.邻接矩阵
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType Vex[MaxVertexNum];
EdgeType Edge[MaxVertexNum][MaxVertexNum];
int vexnum,arcnum;
};
2.邻接表
#define MaxVertexNum 100
typedef char VertexType;
typedef struct ArcNode{ //边结点ArcNode
int adjvex;
struct ArchNode *next;
}ArcNode;
typedef struct VNode{ //顶点VNode
VertexType data;
ArcNode *firstedge;
}VNode,AdjList[MaxVertexNum];
//AdjList是结构体数组类型，等价于struct VNode AdjList[MaxVertexNum]
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum;
}ALGraph;//图
3.十字链表
#define MaxVertexNum 100
typedef char VertexType;
//弧尾结点是起点，弧头结点是终点
typedef struct ArcNode{ //边结点
int tailvex,headvex; //弧尾结点，弧头结点
struct ArcNode *hlink,*tlink;
//tlink指向“和弧尾结点（起点）相同的下一条边”
//hlink指向“和弧头结点（终点）相同的下一条边”
}ArcNode;
typedef struct VNode{
VertexType data; //图中顶点的数据
ArcNode *firstin,*firstout;
//入边表的头指针和出边表的头指针
}VNode;
4.邻接多重表
#define MaxVertexNum 100
typedef struct ArcNode{ //边表结点
bool mark; //访问标记，记录这条边是否搜索过
int ivex,jvex; //弧的两个顶点
struct ArcNode *ilink,*jlink; //分别指向两个顶点的下一条边
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstedge; //指向第一条依附该顶点的边
};
typedef struct{
VNode adjmulist[MaxVertexNum]; //多重邻接表
int vexnum,arcnum; //顶点数和边数
}AMLGraph;
习题中的问题
1.若有一个有向图的邻接矩阵，对角线以下的元素为0，则该图的拓扑排序必定存在。答案上说是：由于邻接矩阵中对角线以下的元素全为0，若存在<i,j>,则必然i<j，由传递性可知，图中的路径的顶点标号是依次递增的，假设存在环 k->...->j->k ,则有 k<j<k ，矛盾，所以不存在环，因此拓扑序列一定存在[不能说明拓扑序列是唯一的]。
疑惑：若主对角线上出现非0元素怎么办？
考研数据结构只考简单图！！！！！！！
2.自己总是会把有向图当成无向图处理，真是让人窒息的操作！！！
这里需要注意的是别把有向图当成无向图，而且在邻接表中，边表结点只保存弧头指向的结点
3.
eg.自己认为是需要遍历所有的顶点和所有的边，因此时间复杂度是O（n+e）,但是和自己的想法不相同
4.画图的时候，路径之间不能直接相交，可以使用下面的形式：
从图的邻接表转换成邻接矩阵
void Convert(ALGraph &G,int arcs[M][N])
{
for(i=0;i<n;i++){
p=(G->v[i]).firstarc;
while(p!=NULL){
arcs[i][p->data]=1;
p=p->nextarc;
}
}
}
DFS,BFS
非常重要，需要理解
https://www.cnblogs.com/2020pengxiyue/p/8371241.html
bool visited[MaxVertexNum];
bool IsTree(Graph &G)//使用引用是为了效率高，否则占用大量用户栈空间
{
for (int i = 1; i <= G.vexnum; i++)
visited[i] = false;
int Vnum = 0, Enum = 0;
DFS(G,1,Vnum,Enum,visited);
if (Vnum == G.vexnum && Enum == 2 * G.vexnum - 2)
return true;
else
return false;
}
void DFS(Graph &G, int v, int &Vnum, int &Enum, int visited[])
{
visited[v] = true;
Vnum++;
int w = FirstNeighbor(G,v);
while (w != -1) {
Enum++;
if (!visited[w])
DFS(G,w,Vnum,Enum,visited);
w = NextNeightbor(G,v,w);
}
}
/*DFS非递归实现*/
算法思想：使用一个栈，记忆下一步可能访问的结点，使用一个访问数组visited[],
visited[i]记忆第i个顶点是否在栈内或者曾将在栈内
void DFS_Non_RC(Graph& G, int v)
{
int w;
Stack S;
InitStack(S);
for (int i = 0; i < G.vexnum; i++)
visited[i] = false;
Push(S,v);
visited[v] = true;
while (!IsEmpty(S)) {
Pop(S,k);
visit(k);
for(w=FirstNeightbor(G,k);w>=0;w=NextNeightbor(G,k,w))
if (!visited[w]) {
Push(S,w);
visited[w] = true;
}
}
}
//使用了栈，遍历的方式是从右端到左端的，不过仍然是深度优先遍历
//如果想要调整顺序，可以增加一个辅助栈调整一下顺序
