- 中文名
- 图
- 外文名
- Graph
- 学 科
- 数学
- 分 类
- 有/无向图等
- 拼 音
- tú
- 释 义
- 表示物件与物件之间的关系的数学对象
主要有以下两种定奔雅义。
图G是一个宙霸格有序二元组(V,E),其中V称为顶集(Vertices Set),E炼碑称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。凳局击其中,顶集的元素被殃元采称为顶点(Vertex),边集的元素被称为边(edge)。
E的元素都是二元组,用(x,y)表示,其中x腊迁殃脚,y∈V。 [1]
图G是指一个三元组(V,E,I),其中V称为顶集,E称为边集,E与V不相交;I称为关联函数,I将E中兵夜主的旋探每一个元素映射到 。如果e被映射到(u,v),那么称边e连接顶点u,v,而u,v则称作e的端点,u,v此时关于e相邻。同时,若两条边i,j有一个公共顶点u,则称i,j关于u相邻。
阶(Order):图G中点集V的大小称作图G的阶。
子图(Sub-Graph):当图G'=(V',E')其中V‘包含于V,E’包含于E,则G'称作图G=(V,E)的子图。每个图都是本身的子图。
生成子图(Spanning Sub-Graph):指满足条件V(G') = V(G)的G的子图G'。
导出子图(Induced Subgraph):以图G的顶点集V的非空子集V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图;以图G的边集E的非空子集E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。
度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。
入度(In-degree)和出度(Out-degree):对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。
自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。
路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk,其中ei的顶点为vi及vi - 1,k称作路径的长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。一条路径称为一简单路径(simple path),如果路径中除起始与终止顶点可以重合外,所有顶点两两不等。
行迹(Trace):如果路径P(u,v)中的边各不相同,则该路径称为u到v的一条行迹。
轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。
闭的行迹称作回路(Circuit),闭的轨称作圈(Cycle)。
(另一种定义是:walk对应上述的path,path对应上述的track。Trail对应trace。)
桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。
邻接表存储表示
一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。在邻接表中,对图中每个顶点建立一个单链表(并按建立的次序编号),第i个单链表中的结点表示依附于顶点vi的边(对于有向图是以顶点vi为尾的弧)。每个结点由两个域组成:邻接点域(adjvex),用以指示与vi邻接的点在图中的位置,链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网(带权图)的信息,则还需要在结点中增加一个存放权值的域(info)。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网,都需要在每个单链表前设一表头结点,这些表头结点的第一个域data用于存放结点vi的编号i,第二个域firstarc用于指向链表中第一个结点。
在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,记作,它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点,则最多有n(n-1)条弧,我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度,以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中,边记作(vi,vj),它蕴涵着存在< vi,vj>和两条弧。若无向图中有n个顶点,则最多有n(n-1)/2条弧,我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同,则这条路径是一条回路。
若路径中顶点没有重复出现,则称这条路径为简单路径。
(1)创建一个图结构 CreateGraph(G)
(2)检索给定顶点 LocateVex(G,elem)
(3)获取图中某个顶点 GetVex(G,v)
(4)为图中顶点赋值 PutVex(G,v,value)
(6)返回下一个邻接点 NextAdjVex(G,v,w)
(7)插入一个顶点 InsertVex(G,v)
(8)删除一个顶点 DeleteVex(G,v)
(9)插入一条边 InsertEdge(G,v,w)
(11)遍历图 Traverse(G,v)
在一个图中,每条边或弧可以拥有一个与之相关的数值,我们将它称为权。这些权可以具有一定的含义,比如,表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图或网的生成树不是唯一的,从不同的顶点出发可以生成不同的生成树,但n个结点的生成树一定有n-1条边
下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是:16+11+5+6+18=56;第二棵生成树的权值是:16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。
构造最小生成树的方法:最初生成树为空,即没有一个结点和一条边,首先选择一个顶点作为生成树的根,然后每次从不在生成树中的边中选择一条权值尽可能小的边,为了保证加入到生成树中的边不会造成回路,与该边邻接的两个顶点必须一个已经在生成树中,一个则不在生成树中,若网中有n个顶点(这里考虑的网是一个连通无向图),则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为:设置2个集合,U集合中的元素是在生成树中的结点,V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点,并将它放入U集合,然后在那些一端顶点在U集合中,而另一端顶点在V-U集合中的边中找一条权最小的边,并把这条边和那个不在U集合中的顶点加入到生成树中,即输出这条边,然后将其顶点添加到U集合中,重复这个操作n-1次。
下面我们考虑一下如何实现这个操作过程的算法。
分析 :(1)它主要有两项操作:按条件选择一条边和将顶点加入到U集合中;(2)网中的每个顶点不是在U集合中,就是在V-U集合中。为了提高算法的时间、空间效率,我们将为这个算法设计一个辅助数组closedge,用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点,在辅助数组中存在一个相应的分量closedge[i-1],它包括两个域,一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值,若该顶点进入U集合,则值为0;另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示:
#define MAX_NUM 10
struct
{
int adjvex;
float lowcist;
}closedge[MAX_NUM];
整个算法的执行过程可以描述为:
{初始化closedge数组的内容;
选择某个顶点k作为生成树的
根结点,并将它加入到U集合中;
重复下列操作n-1次:
l选择一条满足条件的边;
l输出这条边的两个端点;
l修改V-U集合中的顶点信息,即与U集合中构成最小
权值的边。
}
void Mini_SpanTree(GraphG,intk,intn)
{//G是网的邻接矩阵,k是生成树根结点的序号,n是网的顶点数目
for(j=0;j<n;j++)
if(j!=k)closedge[j]={k,G[k][j]};
closedge[k].lowcost=0;
for(i=1;i<n;i++)
{
k=minmun(closedge);
printf(k,closedge[k].adjvex);
closedge[k].lowcost=0;//将顶点加入U集合中
for(j=0;j<n;j++)
if(closedge&&G[k][j]<closedge[j].lowcost)
closedge[j]={k,G[k][j]};
}
}
邻接矩阵:
具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M,则当是该有向图中的一条弧时,M[i,j]=1;否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数;入度为第i列中"1"的个数,并且有向图弧的条数等于矩阵中"1"的个数。
无向图的邻接矩阵
具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M,则当(vi,vj)是该无向图中的一条边时,M[i,j]=M[j,i]=1;否则,M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半,这是因为每条边在矩阵中描述了两次。
#define MAX_VERTEX_NUM 20
typedef struct graph{
Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int n;
}Graph;
边结点的结构为:
elem是顶点内容,firstedge是指向第一条边或弧结点的指针。
在C语言中,实现邻接表表示法的类型定义如下所示:
#define MAX_VERTEX_NUM 30//最大顶点个数
typedef struct EdgeLinklist{//边结点
int adjvex;
struct EdgeLinklist*next;
}EdgeLinklist;
typedef struct VexLinklist{//顶点结点
Elemtype elem;
EdgeLinklist* firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
(1) 创建有向图邻接表
void Create_adj(AdjListad j,int n){
for(i=0;i<n;i++){//初始化顶点数组
scanf(&adj.elem);
adj.firstedge=NULL;
}
scanf(&i,&j);//输入弧
while(i){
s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//创建新的弧结点
s->adgvex=j-1;
s->next=adj[i-1].firstedge;//将新的弧结点插入到相应的位置
adj[i-1].firstegde=s;
scanf(&i,&j);//输入下一条弧
}
}
void Create_adj(AdjListadj,intn){
for(i=0;i<n;i++){//初始化邻接表
scanf(&adj.elem);
adj.firstedge=NULL;
}
scanf(&i,&j);//输入边
while(i){
s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s1->adgvex=j-1;
s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));
s2->adgvex=i-1;
s1->next=adj[i-1].firstedge;
adj[i-1].firstegde=s1;
s2->next=adj[j-1].firstedge;
adj[j-1].firstegde=s2;
scanf(&i,&j);
}
}
深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为:从图中某个顶点v出发,访问该顶点,然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点,直至图中所有与v有路径相通的顶点都被访问完为止。
深度优先遍历算法实现:
为了便于在算法中区分顶点是否已被访问过,需要创建一个一维数组visited[0..n-1](n是图中顶点的数目),用来设置访问标志,其初始值visited(0≤i≤n-1)为"0",表示邻接表中下标值为i的顶点没有被访问过,一旦该顶点被访问,将visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
对于无向图,这个算法可以遍历到v顶点所在的连通分量中的所有顶点,而与v顶点不在一个连通分量中的所有顶点遍历不到;而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点,就需要在上述深度优先遍历算法的基础上,增加对每个顶点访问状态的检测:
int visited[0..n - 1] = { 0,0,...0 };
void DFSTraverse(AdjListadj)
{
for (v = 0; v < n; v++)if (!visited[v])DFS(adj, v);
}
Boolean visited[MAX_VERTEX_NUM];//访问标志数组
Status(*VisitFunc)(intv);//VisitFunc是访问函数,对图的每个顶点调用该函数
void DFSTraverse(Graph G, Status(*Visit)(intv)) {
VisitFunc = Visit;
for (v = 0; v < G.vexnum; ++v)
visited[v] = FALSE;//访问标志数组初始化
for (v = 0; v < G.vexnum; ++v)
if (!visited[v])
DFS(G, v);//对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v) {//从第v个顶点出发
递归地
深度优先遍历图G
visited[v] = TRUE; VisitFunc(v);//访问第v个顶点
for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
//FirstAdjVex返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回空(0),//若w是v的邻接顶点,NextAdjVex返回v的(相对于w的)下一个邻接顶点。
//若w是v的最后一个
邻接点,则返回空(0)。
if (!visited[w])
DFS(G, w);//对v的尚未访问的邻接顶点w调用DFS
}
对图的广度优先遍历方法描述为:从图中某个顶点v出发,在访问该顶点v之后,依次访问v的所有未被访问过的邻接点,然后再访问每个邻接点的邻接点,且访问顺序应保持先被访问的顶点其邻接点也优先被访问,直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。
下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题:
(1)在广度优先遍历中,要求先被访问的顶点其邻接点也被优先访问,因此,必须对每个顶点的访问顺序进行记录,以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序,就可以利用队列结构的操作特点,将访问的每个顶点入队,然后,再依次出队,并访问它们的邻接点;
int visited[0..n-1]={0,0,...0};
InitQueue(Q); //Q是队列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}
Boolean visited[MAX_VERTEX_NUM];//访问标志数组
Status(*VisitFunc)(intv);//VisitFunc是访问函数,对图的每个顶点调用该函数
void BFSTraverse(Graph G, Status(*Visit)(intv)) {
VisitFunc = Visit;
for (v = 0; v < G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q);//置空辅助队列Q
for (v = 0; v < G.vexnum; ++v)
if (!visited[v]) {
visited[v] = TRUE; VisitFunc(v);
EnQueue(Q, v);//v入队列
while (!QueueEmpty(Q)) {
DeQueue(Q, u);//队头元素出队并置为u
for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
if (!Visited[w]) {//w为u的尚未访问的邻接顶点
Visited[w] = TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}
拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列vi1,vi2,...,vin满足下列条件:若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在顶点vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
拓扑排序的方法:
(1)从图中选择一个入度为0的顶点且输出之;
(2)从图中删掉该顶点及其所有以该顶点为弧尾的弧;
下面给出算法实现的基本过程:
{ 将所有入度为0的顶点入栈;
当栈非空时重复执行下列操作:
从栈中退出顶点k;
(1)将k顶点的信息输出;
}
#define MAX_VERTEX_NUM 30//最大顶点个数
typedef struct EdgeLinklist{//边结点
int adjvex;
struct EdgeLinklist*next;
}EdgeLinklist;
typedef struct VexLinklist{//顶点结点
Elemtype elem;
int indegree;//记录顶点的入度
EdgeLinklist* firstedge;
}VexLinklist,AdjList[MAX_VERTEX_NUM];
Status TopologicalSort(AdjListadj)
{
InitStack(s);
for (i = 0; i < MAX_VERTEX_NUM - 1; i++)
if (adj.indegree == 0)Push(s, i);
while (!StackEmpty(s)) {
Pop(s, i);
printf(i);
for (p = adj.firstedge; p; p = p->next) {
adj.indegree -= 1;
if (adj.indegree == 0)Push(s, i);
}
树
平面图
完全图:每一对不同顶点间都有边相连的的图,记作Kn。
二分图:顶集,且每一条边都有一个顶点在X中,而另一个顶点在Y中。
完全二分图:二分图G中若任意两个X和Y中的顶点都有边相连。若,则图G记作Km,n。
正则图:如果图中所有顶点的度皆相等,则此图称为正则图
图是一个有序对,V是结点集,E是边集,当½V½,½E½有限时,称为有限图;否则称无限图.
无向边, 与无序结点(v,u)相关联的边;有向边,与有序结点相关联的边.
无向图,每条边都是无向边的图,记作G=; 每条边都是有向边的图,记作D=.
混合图,既有有向边,也有无向边的图.
自回路(环),关联于同一个结点的边.
无向平行边,联结相同两个结点的多于1条的无向边;有向平行边,联结两个结点之间的多于1条且方向相同的有向边.
简单图,不含平行边和自回路的图.
在有向图D=中,以v(ÎV)为起点的边之条数为出度deg+(v);以v(ÎV)为终点的边之条数为入度deg-(v)..
有n个结点的且每对结点都有边相连无向简单图,无向完全图Kn. 此时有 ;有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图,.此时有
生成子图,设图G=, 若E¢ÍE, 则图<.V,E¢>是的生成子图. 即结点与原图G相同的子图,为生成子图.
Boolean visited[MAX_VERTEX_NUM];//访问标志数组
Status(*VisitFunc)(intv);//VisitFunc是访问函数,对图的每个顶点调用该函数
void DFSTraverse(Graph G,Status(*Visit)(intv)){
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;//访问标志数组初始化
for(v=0;v<G.vexnum;++v)
if(!visited[v])
DFS(G,v);//对尚未访问的顶点调用DFS
}
void DFS(Graph G,int v){//从第v个顶点出发
递归地
深度优先遍历图G
visited[v]=TRUE;VisitFunc(v);//访问第v个顶点
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回空(0),//若w是v的邻接顶点,NextAdjVex返回v的(相对于w的)下一个邻接顶点。
//若w是v的最后一个
邻接点,则返回空(0)。
if(!visited[w])
DFS(G,w);//对v的尚未访问的邻接顶点w调用DFS
}
Boolean visited[MAX_VERTEX_NUM];//访问标志数组
Status(*VisitFunc)(intv);//VisitFunc是访问函数,对图的每个顶点调用该函数
void BFSTraverse(Graph G,Status(*Visit)(intv)){
VisitFunc=Visit;
for(v=0;v<G.vexnum,++v)
visited[v]=FALSE;
initQueue(Q);//置空辅助队列Q
for(v=0;v<G.vexnum;++v)
if(!visited[v]){
visited[v]=TRUE;VisitFunc(v);
EnQueue(Q,v);//v入队列
while(!QueueEmpty(Q)){
DeQueue(Q,u);//队头元素出队并置为u
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!Visited[w]){//w为u的尚未访问的邻接顶点
Visited[w]=TRUE;VisitFunc(w);
EnQueue(Q,w);
}
}
}
}