数据结构图的基本操作及遍历
图的邻接矩阵遍历请看http://www.omegaxyz.com/2017/05/17/graphofds2/
实验目的：
编写程序，建立该图的邻接表存储。基于上面所建立的存储结构，
编程实现深度优先和广度优先搜索算法。
具体函数及其操作
头文件
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #define OK 1 #define ERROR -1 #define Maxsize 20 typedef int InfoType; typedef int VertexType; typedef struct ArcNode ///表节点 { int adjvex; ///存放结点的下标 struct ArcNode *nextarc;///指向下一条边或弧的指针域 InfoType *info;///其他信息 } ArcNode; typedef struct VNode ///头结点 { VertexType data; ArcNode *firstarc; } VNode,AdjList[Maxsize]; typedef struct ///图结构 { AdjList vertices; int vexnum,arcnum;///图中顶点个数和边的个数 int kind; ///kind==0表示无向图，kind==1表示有向图 } ALGraph; int visited[Maxsize]; void CreateALDG(ALGraph &G); void DFSTraverse(ALGraph G,VertexType x); void BFSTraverse(ALGraph G,VertexType x); int LocateX(ALGraph G,VertexType x); |
主要函数
①图的初始化函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
void CreateALDG(ALGraph &G) { int ch1,ch2; int k1,k2;//临时定义四个变量 printf("分别输入节点和弧的数量:");//输入节点和图的数量 scanf("%d%d",&G.vexnum,&G.arcnum); printf("输入顶点的信息:\n"); for(int i=1;i<=G.vexnum;i++) { printf("%d:",i); scanf("%d",&G.vertices[i].data);//输入顶点的信息 G.vertices[i].firstarc=NULL;//指向第一条依附该顶点的弧的指针 } printf("输入弧的信息:\n");//输入弧的信息 for(int i=1;i<=G.arcnum;i++) { printf("%d:",i); getchar(); scanf("%d %d",&ch1,&ch2); for(int p=1;p<=G.arcnum;p++) { if(G.vertices[p].data==ch1) { k1=p;break; } } for(int p=1;p<=G.arcnum;p++) { if(G.vertices[p].data==ch2) { k2=p;break; } } ArcNode *temp; temp=(ArcNode*)malloc(sizeof(ArcNode)); temp->adjvex=k2; temp->nextarc=G.vertices[k1].firstarc; G.vertices[k1].firstarc=temp; } } |
②节点位置的定位
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int LocateX(ALGraph G,VertexType x) { int i,k=0; VertexType t; for(i=1;i<=G.vexnum;i++) { if(G.vertices[i].data==t) { k=i;break; } } return k; } |
③DFS深度优先搜索函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void DFSTraverse(ALGraph G,VertexType x) { int k,i; k=LocateX(G,x); printf("%d/",G.vertices[k].data); visited[k]=1; ArcNode *p; p=G.vertices[k].firstarc; while(p) { if(visited[p->adjvex]==0) DFSTraverse(G,G.vertices[p->adjvex].data); p=p->nextarc; } } |
④广度优先搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
void BFSTraverse(ALGraph G,VertexType x) { struct { ArcNode *Q[Maxsize]; int front,rear; }Que; Que.front=Que.rear; int k,i; k=LocateX(G,x); visited[k]=1; printf("%d /",G.vertices[k].data); Que.rear=(Que.rear+1)%Maxsize; Que.Q[Que.rear]=G.vertices[k].firstarc; ArcNode *p; while(Que.rear!=Que.front) { Que.front=(Que.front+1)%Maxsize; p=Que.Q[Que.front]; while(p) { if(visited[p->adjvex]==0) { visited[p->adjvex]=1; printf("%d /",G.vertices[p->adjvex].data); Que.rear=(Que.rear+1)%Maxsize; Que.Q[Que.rear]=G.vertices[p->adjvex].firstarc; } p=p->nextarc; } } } //此处使用了循环队列 |
MAIN函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
int main() { int visited[Maxsize]; int i; printf("----------------------------------------\n"); printf("图的初始化：\n"); ALGraph G; CreateALDG(G); printf("----------------------------------------\n"); printf("图的DFS遍历：\n"); for(i=0;i<=Maxsize;i++) visited[i]=0; VertexType x; printf("输入开始遍历的节点名称：\n"); getchar(); scanf("%d",&x); printf("DFS遍历输出：\n"); DFSTraverse(G,x); printf("\n----------------------------------------\n"); printf("图的BFS遍历：\n"); for(i=0;i<=Maxsize;i++) visited[i]=0; printf("输入开始遍历的节点名称：\n"); getchar(); scanf("%d",&x); printf("BFS遍历输出：\n"); BFSTraverse(G,x); printf("\n----------------------------------------\n"); return 0; } |
