图的操作
一、问题描述
图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。
二、基本要求
1、选择合适的存储结构完成图的建立；
2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列；
3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；
三、测试数据
四、算法思想
1、邻接矩阵
顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。
2、邻接表
邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。
3、图的深度遍历
深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
4、图的广度遍历
广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
五、模块划分
一、基于邻接矩阵的深广度遍历
1．StatusInitQueue(LinkQueueQ)
根据已知Q初始化队列
2．StatusQueueEmpty(LinkQueueQ)
判断队列是否为空
3．StatusEnQueue(LinkQueueQ,QElemTypee)
将e压入队尾
4．StatusDeQueue(LinkQueueQ,QElemTypee)
取队头元素e
5．intLocateVex(MGraphG,VertexTypev)
定位定点v
6．voidCreateGraph(MGraphG)
建立无向图的邻接矩阵
7．voidPrintGraph(MGraphG)
输出邻接矩阵的无向图
8．intFirstAdjVex(MGraphG,intv)
第一个邻接点的定位
9．intNextAdjVex(MGraphG,intv,intw)
查找下一个邻接点
10．voidDfs(MGraphG,intv)
实现图的一次遍历
11．voidDfsTraverse(MGraphG)
实现图的深度遍历
12．voidBfsTraverse(MGraphG)
实现图的广度遍历
13．Main
主函数
二、基于邻接表实现图的深广度遍历
1．StatusInitQueue(LinkQueueQ)
根据已知Q初始化队列
2．StatusQueueEmpty(LinkQueueQ)
判断队列是否为空
3．StatusEnQueue(LinkQueueQ,QElemTypee)
将e压入队尾
4．StatusDeQueue(LinkQueueQ,QElemTypee)
取队头元素e
5．voidcreateALGraph(ALGraphG)
建立无向图的邻接矩阵
6．voidPrintGraph(MGraphG)
输出邻接矩阵的无向图
7．intFirstAdjVex(MGraphG,intv)
第一个邻接点的定位
8．intNextAdjVex(MGraphG,intv,intw)
查找下一个邻接点
9．voidDfs(MGraphG,intv)
实现图的一次深度遍历
10．voidDfsTraverse(MGraphG)
实现图的深度遍历
11．voidBFS(ALGraphG,intv)
实现图的一次广度遍历
12．voidBfsTraverse(MGraphG)
实现图的广度遍历
13．Void…………………………………Main
主函数
六、数据结构//(ADT)
1、基于邻接矩阵的图的类型定义
typedefstructArcCell
{VRTypeadj;/图中有1/0表示是否有边，网中表示边上的权值/
/InfoTypeinfo;与边相关的信息/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{VertexTypevexs[MAX_VERTEX_NUM];/顶点向量/
AdjMatrixarcs;/邻接矩阵/
intvexnum,arcnum;/图中当前顶点数和边数/
}MGraph;
2、基于邻接表的图的类型定义
typedefstructArcNode
{
intadjvex;
structArcNodenextarc;
}ArcNode;/表节点/
typedefstruct
{
TElemTypedata;
ArcNodefirstarc;
}VNode,AdjList[MAXVER];/表节点/
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;/图中当前顶点数和边数/
}ALGraph;
七、源程序
一、基于邻接矩阵的图的深度、广度遍历
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#defineTRUE1
#defineFALSE0
#defineOVERFLOW-2
#defineOK1
#defineERROR0
typedefintStatus;
#defineINFINITYINT_MAX/最大值“无穷”/
#defineMAX_VERTEX_NUM20/最大顶点个数/
typedefintBoolean;
typedefcharVertexType[20];
typedefintVRType;
/以下为队列的操作/
/队列的类型定义/
typedefintQElemType;
typedefstructQNode
{QElemTypedata;
structQNodenext;
}QNode,QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
/初始化队列/
StatusInitQueue(LinkQueueQ)
{(Q).front=(Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(Q).front)exit(OVERFLOW);
(Q).front->next=NULL;
returnOK;}
/判断队列是否为空/
StatusQueueEmpty(LinkQueueQ)
{if(Q.front==Q.rear)
returnTRUE;
else
returnFALSE;}
/入队列/
StatusEnQueue(LinkQueueQ,QElemTypee)
{QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p->data=e;p->next=NULL;
(Q).rear->next=p;
(Q).rear=p;
returnOK;}
/出队列/
StatusDeQueue(LinkQueueQ,QElemTypee)
{QueuePtrp;
if((Q).front==(Q).rear)returnERROR;
p=(Q).front->next;
e=p->data;
(Q).front->next=p->next;
if((Q).rear==p)(Q).rear=(Q).front;
free(p);
returnOK;}
/以下为图的操作/
/图的类型定义/
typedefstructArcCell
{VRTypeadj;/图中有1/0表示是否有边，网中表示边上的权值/
/InfoTypeinfo;与边相关的信息/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{VertexTypevexs[MAX_VERTEX_NUM];/顶点向量/
AdjMatrixarcs;/邻接矩阵/
intvexnum,arcnum;/图中当前顶点数和边数/
}MGraph;
/顶点在顶点向量中的定位/
intLocateVex(MGraphG,VertexTypev)
{inti;
for(i=0;i
if(strcmp(v,G.vexs[i])==0)break;
returni;
}
/建立无向图的邻接矩阵/
voidCreateGraph(MGraphG)
{inti,j,k;VertexTypev1,v2;
printf("\nInputMGvexnum,arcnum:");
scanf("%d,%d",&(G).vexnum,&(G).arcnum);
printf("Input%dvexs:",(G).vexnum);
for(i=0;i<(G).vexnum;i++)/输入顶点向量/
{scanf("%s",(G).vexs[i]);}
printf("vexslist\n");
for(i=0;ivexnum;i++)/输出顶点向量/
puts(G->vexs[i]);
for(i=0;i<(G).vexnum;i++)/邻接矩阵初始化/
for(j=0;j<(G).vexnum;j++)
(G).arcs[i][j].adj=0;
printf("\nInput%darcs(vivj):\n",(G).arcnum);
for(k=0;k<(G).arcnum;k++)/输入无权图的边/
{scanf("%s%s",v1,v2);
i=LocateVex(G,v1);j=LocateVex(G,v2);
(G).arcs[i][j].adj=1;
(G).arcs[j][i]=(G).arcs[i][j];
}
}
/按邻接矩阵方式输出无向图/
voidPrintGraph(MGraphG)
{inti,j;
printf("\nMGraph:\n");
for(i=0;i
{printf("%10s",G.vexs[i]);
for(j=0;j
printf("%4d",G.arcs[i][j].adj);
printf("\n");
}
}
/查找第1个邻接点/
intFirstAdjVex(MGraphG,intv)
{intj,p=-1;
for(j=0;j
if(G.arcs[v][j].adj==1){p=j;break;}
returnp;
}
/查找下一个邻接点/
intNextAdjVex(MGraphG,intv,intw)
{intj,p=-1;
for(j=w+1;j
if(G.arcs[v][j].adj==1){p=j;break;}
returnp;
}
/深度遍历/
Booleanvisited[MAX_VERTEX_NUM];/设置全局的访问标志数组/
voidDfs(MGraphG,intv)
{intw;
visited[v]=TRUE;
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w])Dfs(G,w);
}
voidDfsTraverse(MGraphG)
{intv;
for(v=0;v
visited[v]=FALSE;
for(v=0;v
if(!visited[v])Dfs(G,v);
}
/广度遍历/
voidBfsTraverse(MGraphG)
{intv,u,w;LinkQueueQ;
for(v=0;v
InitQueue(&Q);
for(v=0;v
if(!visited[v])
{visited[v]=TRUE;
printf("%s",G.vexs[v]);
EnQueue(&Q,v);
while(!QueueEmpty(Q))
{DeQueue(&Q,&u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
if(!visited[w])
{visited[w]=TRUE;
printf("%s",G.vexs[w]);
EnQueue(&Q,w);
}
}
}
}
/主函数/
main()
{intw;
MGraphG;
CreateGraph(&G);
PrintGraph(G);
printf("\nDfs:");DfsTraverse(G);/深度遍历/
printf("\nBfs:");BfsTraverse(G);/广度遍历/
}
二：基于邻接表的图的深度、广度遍历
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#defineMAXVER21
#defineN100
typedefcharTElemType[10];
/循环队列的操作/
/队列的类型定义/
typedefintElemType;
typedefstruct
{
ElemTypebase;
intfront,rear;
}SqQueue;
/初始化队列/
voidInitQueue(SqQueueQ)
{Q->base=(ElemType)malloc(Nsizeof(ElemType));
Q->front=Q->rear=0;}
/判断队列是否为空/
intQueueEmpty(SqQueueQ)
{if(Q.front==Q.rear)
return1;
else
return0;}
/入队列/
intEnQueue(SqQueueQ,ElemTypee)
{if((Q->rear+1)%N==Q->front)
return0;
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%N;
return1;}
/出队列/
intDeQueue(SqQueueQ,ElemTypee)
{if(Q->rear==Q->front)
return0;
e=Q->base[Q->front];
Q->front=(Q->front+1)%N;
return1;}
/图的操作/
/图的类型定义/
typedefstructArcNode
{
intadjvex;
structArcNodenextarc;
}ArcNode;
typedefstruct
{
TElemTypedata;
ArcNodefirstarc;
}VNode,AdjList[MAXVER];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
/建立无向图的邻接矩阵/
voidcreateALGraph(ALGraphG)
{
inti,s,d;
ArcNodep,q;
printf("\nInputMGvexnum,arcnum:");
scanf("%d,%d",&(G).vexnum,&(G).arcnum);
for(i=1;i<=G->vexnum;i++)
{
printf("\n输入第%d个顶点信息：",i);
scanf("%s",G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}//输入第i个结点值并初始化第i个单链表为空
for(i=1;i<=G->arcnum;i++)
{
printf("\n输入第%d条边的始点和终点：",i);
scanf("%d,%d",&s,&d);
p=(ArcNode)malloc(sizeof(ArcNode));
p->adjvex=d;
p->nextarc=G->vertices[s].firstarc;
G->vertices[s].firstarc=p;
//将新建的以d为信息的表结点p插入s单链表的头结点后
q=(ArcNode)malloc(sizeof(ArcNode));
q->adjvex=s;
q->nextarc=G->vertices[d].firstarc;
G->vertices[d].firstarc=q;
//将新建的以s为信息的表结点q插入d单链表的头结点后
}
}
/深度遍历/
intvisited[MAXVER];//定义全局数组遍历visited
voiddfs(ALGraphG,intv)//被遍历的图G采用邻接表作为存储结构，v为出发顶点编号
{
ArcNodep;
printf("%s",G.vertices[v].data);
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)dfs(G,p->adjvex);
//若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs
p=p->nextarc;
}
}
voiddfsTraverse(ALGraphG)
{
intv;
//遍历图之前初始化各未访问的顶点
for(v=1;v<=G.vexnum;v++)
visited[v]=0;
//从各个未被访问过的顶点开始进行深度遍历
for(v=1;v<=G.vexnum;v++)
if(visited[v]==0)dfs(G,v);
}
/广度遍历/
voidBFS(ALGraphG,intv)
//从顶点编号v出发，广度遍历邻接表存储的图G
{
SqQueueQ;ArcNodep;
InitQueue(&Q);
printf("%s",G.vertices[v].data);
visited[v]=1;
EnQueue(&Q,v);
while(!QueueEmpty(Q))
{
v=DeQueue(&Q,&v);
p=G.vertices[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
v=p->adjvex;
printf("%s",G.vertices[v].data);
visited[v]=1;
EnQueue(&Q,v);
}
p=p->nextarc;
}
}
}
voidBFSTraverse(ALGraphG)
{
intv;
//遍历G以前，初始化visited数组为0
for(v=1;v<=G.vexnum;v++)
visited[v]=0;
for(v=1;v<=G.vexnum;v++)
if(visited[v]==0)
BFS(G,v);
}
voidmain()
{
ALGraphG;
createALGraph(&G);
printf("深度遍历结果为：\n");
dfsTraverse(G);
printf("\n广度遍历结果为：\n");
BFSTraverse(G);
system("pause");
}
八、测试情况
程序的测试结果如下：
1、基于邻接矩阵的图的深度、广度遍历
结果正确
2、基于邻接表的图的深度、广度遍历
结果正确
九、参考文献
1、严蔚敏，《数据结构C语言》，清华大学出版社。
2、谭浩强，《c语言程序设计》，清华大学出版社。
小结
图的遍历是有关于图的算法中最常见、最典型的算法。与树的遍历相类似，图的遍历是从图中任意一个顶点出发，访问遍图中所有的顶点，且使每个顶点仅被访问一次。图的遍历算法是求解图的连通性、拓扑排序、和求关键路径等算法的基础。由于图本身结构的复杂性，因而使得图的遍历要比树的遍历复杂得多。首先，图中所有顶点没有主次之分，因此也就没有一个“自然”的起始点；其次，图中任意顶点均有可能与其它顶点相邻，在沿着某一路径依次搜索访问顶点时完全有可能又回到该顶点上；此外，图中某一顶点可能与多个顶点相邻，当访问过该结点后，如何选择下一个要访问的顶点，就成为一个决策问题。鉴于图的遍历的复杂性，遍历算法的设计就必须考虑图的结构特征。图的遍历算法通常有两条遍历路径：深度优先遍历和广度优先遍历
通过学习了图的深度遍历和广度遍历，我们对邻接表和邻接矩阵进行深度遍历和广度遍历。图的深度遍历类似于树的先根遍历，广度遍历类似于树的层次遍历。在实际中，由于在图中各个结点的度数各个不同，最大度数和最小度数可能相差很多，如果按度数最大的顶点设计结点结构，就会浪费很多存储单元，反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。在实际应用中不宜采用这种结构，而应该根据具体的图和需要进行的操作，设计恰当的结点结构和表结构，这时我们就用邻接表来处理，邻接表是图的一种链式存储结构。在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。图遍历的过程实质上是对每个顶点查找其邻接点的过程，是通过边或弧找邻接点的过程在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。邻接表中每一个表结点有两个域，其一为邻接点域adjvex，用以存放与顶点vi相邻接的顶点vj的序号j，其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertex，另一个则是指针域(指向邻接表)link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个一维数组存储起来，其中第i个分量存储vi邻接表的表头指针，一个图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。
广度遍历图的时间复杂度和深度遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。这两种遍历既适用于无向图，也适用于有向图。但无论何种算法都是建立在邻接表存储结构之上所展开的。
经过这次的程序设计让我们对邻接表和邻接矩阵有了更深度的了解，更对深度遍历和广度遍历的应用有了确切的明白，在以后的编程中也知道如何正确的运用。
wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802
|
|
