图是一种较为复杂的数据结构,图中任意两个数据之间都有可能关联。
1.图的相关术语定义
图中的数据元素称为顶点,V是顶点的集合。从顶点a到顶点b有一条弧,a称为弧尾,b称为弧头,此时弧是有方向的,这样的图称为有向图。如果以无序对(a,b)代替这两个有序对,称a,b之间的一条边,而不是弧,这样的图称为无向图。
用n表示图中的顶点个数,用e表示边或弧的数目。对无向图来说,n个顶点最多有n*(n-1) / 2条边,所以e的取值范围在0 - n*(n-1) / 2。当e取最大值时,此时的图称为完全图。
同理,当e = n*(n - 1),称为有向完全图。e < nlogn称为稀疏图,否则称为稠密图。
顶点的度是以顶点v的相关连的边或弧的数目,入度是一顶点v为弧头的弧的个数,出度是以顶点v为弧尾的弧的个数。
从顶点a到顶点b的路径就是a到b的顶点序列,起点和重点相同的路径称为回路或环。序列中不重复出现顶点的路径称为简单路径。
在无向图中,如果从顶点a到顶点b有路径,称a和b是连通的。如果图中任意两个顶点都是连通的,称为连通图。连通分量指的是无向图中的极大连通子图。
在有向图中,如果任意两个顶点a,b有a到b的路径和b到a的路径,称为强连通图,强连通分量是有向图中的极大强连通子图。
一个连通图的生成树是一个极小连通子图,包括所有顶点和n-1条边。如果一个有n个顶点的图,边e < n-1,则图是非连通的;如果e > n-1肯定有环,但是有n-1条边的图不一定有生成树。
2.图的存储结构
- 数组表示法(邻接矩阵),通过一个n*n的二维数组来存放边,一个数组存放顶点。
- 邻接表,一种链式存储方式,为每一个顶点建立一个单链表,用来表示依附于顶点v的边或以v为弧尾的弧。每个节点有3个域,邻接点域adjvex表示与v邻接的顶点在图中的位置,链域nextarc只想下一条边或弧的节点(依然是v的邻接点),数据域存储边或弧的信息info。每个链表上附上一个头结点,包括一个数据域data,存放顶点信息,和链域firstarc。表头结点一般用顺序存储,以达到随机访问。表节点 adjvex,nextarc,info;头结点 data,firstarc
- 十字链表,为有向图的另一种存储方式,基于邻接表,在其基础做了下改造。首先是头结点 data,firstin,firstout。data同邻接表,firstin指向以顶点v为弧头的弧节点,firstout指向以v为弧尾的弧节点。弧节点 tailvex,headvex,hlink,tlink,info。info域表示弧的信息,尾域tailvex和头域headvex指向弧节点所关联的头结点位置。hlink指向弧头相同的下一个弧节点,tlink指向弧尾相同的下一个弧节点。
- 邻接多重表,是无向图的另一种形式存储结构,由于邻接表中每一条边(a,b)都有两个顶点,分别在第a和第b个链表中,这个操作上带来不便。邻接多重表把边改了一下 mark,ivex,ilink,jvex,jlink,info。mark用来标记边是否被访问过,ivex表示顶点i的位置,ilink表示依附于顶点i的下一条边,jvex和jlink同理。
3.图的遍历
图的遍历有两种算法,DFS和BFS
DFS(深度优先搜索)
从图中选出一个顶点v出发,如果v的邻接点未被访问,设邻接点为w,访问w,然后再以w为起点做同样的方式访问。如果w的邻接点都被访问了,则返回上一顶点,也就是v,继续访问。
void DFSall(Graph *G){ //考虑到图不一定是连通的,所以需要一个函数来遍历每个节点,且初始化 for(int i = 0; i < G -> vexnum; i++) visit[i] = 0; for(int i = 0; i < G -> vexnum; i++) if(!visit[i]) DFS(G, i); } void DFS(Graph *G, int i){ //采用邻接表 arcnode * p = G -> firstarc; visit[i] = 1; cout << i; //visit node i; while(p != NULL){ if(!visit[p -> data]) DFS(G, p -> data); p = p -> nextarc; } }
邻接表有e条边,按边查询节点只需要遍历e次就可以找到所有节点,所以时间复杂度是O(n + e)。如果使用邻接矩阵,查询节点需要O(n^2)。
BFS(广度优先搜索)
从任一顶点v出发,如果v的邻接点未被访问,就访问该顶点。依次将顶点v的邻接点访问完后,将访问的几点存储起来,在取集合中的第一个顶点,按上述方式继续访问。
void BFS(Graph *G){ for(int i = 0; i < G -> vexnum; i++) visit[i] = 0; queue q; for(int i = 0; i < G -> vexnum; i++){ if(!visit[i]){ visit[i] = 1; cout << i; q.push(i); while(!q.empty()){ int t = q.top(); for(arcnode *p = G -> head[t] -> firstarc; p != NULL; p = p -> nextarc){ if(!visit[p -> data]){ visit[p -> data] = 1; q.push(p -> data); cout << p -> data; } } q.pop(); } } }
时间复杂度同DFS