数据结构学习笔记(图)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构学习笔记(图)

希希里之海 2017-06-02 21:49:00 浏览447
展开阅读全文

                          一
                        (基本概念)
1.图的定义:图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

2.与线性表、树的比较:
(1)线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称之为顶点。
(2)线性表中可以没有数据元素,称为空表。树中可以没有结点,叫做空树。在图结构中,不允许没有顶点。
(3)线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

3.无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(Vi,Vj)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧。用有序偶<Vi,Vj>来表示,Vj称为弧尾,Vj称为弧头。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。

*无向边用小括号“()”表示,而有向边则用尖括号“<>”表示。

4.在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。

5.在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。

6.在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。

*对于具有n个顶点和e条边数的图,无向图0≤e≤n(n-1)/2, 有向图0≤e≤n(n-1)。

7.有很少条边或弧的图称为稀疏图,反之称为稠密图。

8.与图的边或弧相关的数叫做权。这种带权的图通常称为网。

9.顶点v的度是和v相关联的边的数目。
边数其实就是各定点度数和的一半。
以顶点v为头的弧的数目称为v的入度,以v为尾的弧的数目称为v的出度。

10.图中顶点与顶点之间的路径却是不唯一的。
路径的长度是路径上的边或弧的数目。
第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

 

                          二
1.无向图中的极大连通子图称为连通分量。强调:
*要是子图;
*子图要是连通的;
*连通子图含有极大顶点数;
*具有极大顶点数的连通子图包含依附于这些顶点的所有边。

2.从Vi到Vj和从Vi到Vj都存在路径,则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

3.一个连通图的生成树是一个极小的连通子图,它含有图中全部的n各顶点,但只有足以构成一棵树的n-1条边。

4.如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多于n-1条边,必定构成一个环。不过有n-1条边并不一定是生成树。

5.如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。

6.一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不想交的有向树的弧。

 

                          三

                        (术语总结)
1.图按照有无方向分为无向图和有向图。无向图由顶点和边构成,有向图由顶点和弧构成。弧有弧尾和弧头之分。

2.图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

3.图中顶点之间有领接点、依附的概念。无向图顶点的边数叫做度,有向图顶点分为入度和出度。

4.图上的边或弧上带权则称为网。

5.图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称强连通图。图中有子图,若子图极大连通则就是连通分量,有向则称强连通分量。

6.无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0,其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

 

                          四
                       (图的存储结构)
1、图不可能用简单的顺序存储结构来表示。

2.图的五种不同的存储结构:
(1)邻接矩阵:图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

*对称矩阵就是n阶矩阵的元满足aij=aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角相对应的元全都是相等的(即是无向图)。

a.判定任意两顶点是否有边无边就非常容易了。
b.要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和。
c.求顶点Vi的所有邻接点就是矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

*判断有向图顶点Vi到Vj是否存在弧,只需要查找矩阵中arc[i][j]为1的顶点。

*图的邻接矩阵存储结构代码:
typedef char VertexType; /*顶点类型应由用户定义*/
typedef int EdgeType; /*边上的权值类型应由用户定义*/
#define MAXVEX 100 /*最大顶点数,应由用户定义*/
#define INFINITY 65535 /*用65535来表示正无穷*/
typedef struct
{
VertexType vexs[MAXVEX]; /*顶点表*/
EdgeType arc[MAXVEX][MAXVEX] /*邻接矩阵,可看做边表*/
int numVertexes, numEdges; /*图中当前的顶点数和边数*/
}MGraph;

*无向网图的创建代码:
/*建立无向网图的邻接矩阵表示*/
void CreateMGraph(MGraph *G)
{
int i, j, k, w;
printf("输入顶点数和边数:\n");
scanf("%d, %d", &G->numVertexes,&G->numEdges); /*输入顶点数和边数*/
for(i=0;i<G->numVertexes; i++) /*读入顶点信息,建立顶点表*/
scanf(&G->vexs[i]);
for(i=0;i<G->numVertexes; i++)
for(j=0;j<G->numVertexes; j++)
G->arc[i][j]=INFINITY; /*邻接矩阵初始化*/
for(k=0; k<G->numEdges; k++) /*读入numEdges条边,建立邻接矩阵*/
{
print("输入边(Vi,Vj)上的下标、下标j和权w:\n");
scanf("%d, %d, %d", &i, &j, &w); /*输入边(Vi,Vj)上的权w*/
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j]; /*因为是无向图,矩阵对称*/
}
}

#从代码中也可以得到,n个顶点和e条边的无向网图的创建,时间复杂度为O(n+n2+e),其中对邻接矩阵Garc的初始化耗费了O(n2)的时间。


(2)邻接表:数组与链表相结合的存储方法称为邻接表。
*邻接表的处理方法是这样:
1.图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。
2.图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点Vi的边表,有向图则称为顶点Vi作为弧尾的出边表。

*顶点表的各个结点由data和first edge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点的顶点表中的下标,next则存储指向边表中下一个结点的指针。

*对于带权值得网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。

#结点定义:
typedef char VertexType; /*顶点类型应由用户定义*/
typedef int EdgeType; /*边上的权值应由用户定义*/

typedef struct EdgeNode /*边表结点*/
{
int adjvex; /*邻接点域,存储该顶点对应的下标*/
EdgeType weight; /*用于存储权值,对于非网图可以不需要*/
struct EdgeNode *next; /*链域,指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode /*定义表结点*/
{
VertexType data; /*顶点域,存储顶点信息*/
EdgeNode *firstedge; /*边表头指针*/
}VertexNode, AdjList[MAXVEX];

typedef struct
{
AdjList adjList;
int numVertexes, numEdges; /*图中当前顶点数和边数*/
}GraphAdjList;


#无向图的邻接表的创建:
/*建立图的邻接表结构*/
void CreateALGraph(GraphAdjList *G)
{
int i, j, k;
EdgeNode *e;
printf("输入顶点数和边数:\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); /*输入顶点数和边数*/
for (i=0; i<G->numVertexes; i++) /*读入顶点信息,建立顶点表*/
{
scanf(&G->adjLIst[i].data); /*输入顶点信息*/
G->adjLIst[i].firstedge=NULL; /*将边表置为空表*/
}
for(k=0; k<G->numEdges; k++) /*建立边表*/
{
printf("输入边(Vi, Vj)上的顶点序号:\n");
scanf("%d, %d", &i, &j); /*输入边(Vi,Vj)上的顶点序号*/
e=(EdgeNode*)malloc(sizeof(EdgeNode)); /*向内存申请空间*/
/*生成边表结点*/
e->adjvex=j; /*邻接序号为j*/
e->next=G->adjList[i].firstedge; /*将e指针指向当前顶点指向的结点*/
G->adjList[i].firstedge=e; /*将当前顶点的指针指向e*/
e=(EdgeNode*)malloc(sizeof(EdgeNode)); /*向内存申请空间*/
/*生成边表结点*/
e-adjvex=i; /*邻接序号为i*/
e->next=G->adjList[j].firstedge; /*将e指针指向当前顶点指向的结点*/
G->adjList[j].firstedge=e; /*将当前顶点的指针指向e*/
}
}

*时间复杂度为O(n+e)。


                         五
                       (图的遍历)
1.概念:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历。

2.需要在遍历过程中把访问过的顶点打上标记,以避免访问多次而不自知。具体办法是设置一个访问数组visited[n],n是图中顶点的个数,初值为0,访问过后设置为1.

3.图的遍历:深度优先遍历和广度优先遍历。
(1)深度优先遍历(DFS):
深度优先遍历其实就是一个递归的过程,相当于树的前序遍历。
从图中某个顶点v出发,访问此顶点,然后从v的未访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。
对于非连通图,只需要对它的连通分量分别进行深度优先遍历。

**对于n个顶点e条边的图来说,邻接矩阵的方式访问需要O(n2)的时间;对于邻接表来说,需要O(n+e)时间。
显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。

(2)广度优先遍历(BFS):
类似树的层序遍历。
*广度优先遍历和深度优先遍历的时间复杂度是一样的。邻接矩阵访问时间为O(n2),邻接表访问时间为O(n+e)。

比较:深度优先遍历更适合目标比较明确,以找到目标为主要目的的情况,而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。


                          六
                       (最小生成树)
我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树,有两种算法:普里姆算法和克鲁斯卡尔算法。

1、普里姆算法:
以某顶点为起点逐步找各顶点上最小权值得边来构建最小生成树的。
假设N=(P,{E})是连通图,TE是N上最小生成树中边的集合。算法从U={u。}(u。属于V),TE={}开始。重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找一条代价最小的边(u。,v。)并入集合TE,同时v。并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。
时间复杂度为O(n2)。

2.克鲁斯卡尔算法:
以边为目标去构建。
假设N=(V,{E})是连通图,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将次变加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。
克鲁斯卡尔算法的时间复杂度为O(elog2e)。

总结:对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。

 

                         七
                       (最短路径)
对于网图来说,最短路径,是指两顶点之间经过的边上权值最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。

1.迪杰斯特拉(Dijkstra)算法:
这是一个按路径长度递增的次序产生最短路径的算法。
时间复杂度为O(n2)。
如果是图中任意一个顶点到另一顶点的距离,时间复杂度为O(n3)。

代码如下:
#define MAXVEX 9
#define INFINITY 65535
typedef int Pathmatirx[MAXVEX];
typedef int ShortPathTable[MAXVEX];
typedef int ShortPathTable[MAXVEX];

void ShortestPath_Dijkstra(MGraph G, int V0, Pathmatirx *P, ShortPathTable *D)
{
int v, w, k, min;
int final[MAXVEX];
for (v=0; v<G.numVertexes; v++)
{
final[v] = 0;
(*D)[v] = G.matirx[v0][v];
(*p)[v] = 0;
}
(*D)[v0] = 0;
final[v0] = 0;
final[v0] = 1;
for (v=1; v<G.numVertexes; v++)
{
mun = INFINITY;
for (w=0; w<G.numVertexes; w++)
{
if (!final[w] && (*D)[w]<min)
{
k=w;
min=(*D)[w];
}
}
final[k]=1;
for (w=0; w<G.numVertexes; w++)
{
if(!final[w] && (min+G.matirx[k][w]<(*D)[w]))
{
(*D)[w] = min + G.matirx[k][w];
(*p)[w]=k;
}
}
}
}

2.弗洛伊德(Floyd)算法
比较经过顶点的权值,如果经过的顶点路径比原两点间的路径更短,将当前两点间的权值设为更小的一个。

代码如下:
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/*Floyd算法,求网图G中各顶点V到其余顶点w最短路径P[v][w]及带权长度D[v][w]*/
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
{
int v, w, k;
for (v=0; v<G.numVertexes; ++w); /*初始化D与P*/
{
(*D)[v][w]=G.matirx[v][w]; /*D[v][w]值即为对应点间的权值*/
(*P)[v][w]=w;
}
}
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
if((*D)[v][w]>(*D)[v][k] + (*D)[k][w])
{
/*如果经过下标为k顶点路径比原两点间路径更短*/
/*将当前两点间权值设为更小的一个*/
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
(*P)[v][w]=(*P)[v][k];
}
}
}
}

时间复杂度为O(n3)。


                         八
                       (拓扑排序)
1.无环,即是图中没有回路的意思。

2.在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网。

3。设G={V,E}是一个具有n个顶点的有向图,V中的顶点序列V1,V2,......,Vn,满足若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

4.拓扑排序,其实就是一个有向图构造拓扑序列的过程。构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环(回路)的AOV网;如果输出顶点数少了,也说明这个网存在环(回路),不是AOV网。

5.拓扑排序算法:
(1)对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
(2)由于拓扑排序的过程中,需要删除顶点,显然用邻接表会更加方便。

**拓扑排序的整个算发起的时间复杂度为O(n+e)。

6.在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网。我们把AOE网中没有入边的顶点称为始点或源点,没有出边的顶点称为终点或汇点。

7.AOV网是顶点表示活动的网,它只描述活动之间的制约关系,而AOE网是用边表示活动的网,边上的权值表示活动持续的时间。

8.把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径。

 

网友评论

登录后评论
0/500
评论
希希里之海
+ 关注