《图的建立及基本运算的实现》由会员分享，可在线阅读，更多相关《图的建立及基本运算的实现（12页珍藏版）》请在金锄头文库上搜索。
1、图的建立及基本运算的实现图的建立及基本运算的实现实验目的：实验目的：掌握图形结构的特点、存储方式以及相应基本运算的编程实现。 实验内容：实验内容： (1)用邻接矩阵或者邻接表存储结构形式表示一个图，图中每个顶点代表一个字符 （自定义） ，打印出深度优先搜索和广度优先搜索的节点序列。 程序代码：程序代码： （1）用邻接矩阵方式存储）用邻接矩阵方式存储#include #define MaxVertexNum 50 #define QueueSize 50 typedef enumFALSE,TRUEdefine; define visitedMaxVertexNum; typedef char
2、VertexType; /顶点是字符型顶点是字符型 typedef int EdgeType; /边是整型边是整型 typedef struct VertexType vexsMaxVertexNum; /顶点向量顶点向量 EdgeType edgesMaxVertexNumMaxVertexNum; /邻接矩阵邻接矩阵 int vexnum,arcnum; /图中当前的顶点数和边数图中当前的顶点数和边数 Graph; /* 邻接矩阵的建立邻接矩阵的建立*/ void CreateGraph(Graph *G) int i,j,k; char ch1,ch2; printf(“请输入顶点数和边
3、数请输入顶点数和边数(输入格式为输入格式为:顶点数顶点数,边数边数):“); scanf(“%d,%d“, printf(“请输入顶点名称请输入顶点名称(输入格式为输入格式为:a,b,c.)：“); for(i=0;ivexnum;i+) getchar();scanf(“%c“, for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) G-edgesij=0; ABFEGDCprintf(“请输入每条边对应的两个顶点名称请输入每条边对应的两个顶点名称(输入格式为输入格式为:a,b):n“); for(k=0;karcnum;k+) getchar(); printf(
4、“请输入第请输入第%d 条边的两个顶点名称：条边的两个顶点名称：“,k+1); scanf(“%c,%c“, for(i=0;ch1!=G-vexsi;i+); for(j=0;ch2!=G-vexsj;j+); G-edgesij=1; /* 深度优先遍历深度优先遍历 */ void Depth(Graph *G,int i) int j; printf(“%cn“,G-vexsi); /访问顶点访问顶点 vi visitedi=TRUE; for(j=0;jvexnum;j+) /依次搜索依次搜索 vi 邻接点邻接点 if(G-edgesij=1 void Depthsearch(Grap
5、h *G) int i; for(i=0;ivexnum;i+) visitedi=FALSE; for(i=0;ivexnum;i+) if(!visitedi) Depth(G,i); /*广度优先遍历广度优先遍历*/ typedef struct int front; int rear; int count; int dataQueueSize; AQueue; void InitQueue(AQueue *Q) Q-front=Q-rear=0; Q-count=0; int QueueEmpty(AQueue *Q) return Q-count=QueueSize; int Que
6、ueFull(AQueue *Q) return Q-count=QueueSize; void EnQueue(AQueue *Q,int x) if (QueueFull(Q) printf(“Queue overflow“); else Q-count+; Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; int DeQueue(AQueue *Q) int temp; if(QueueEmpty(Q) printf(“Queue underflow“); return NULL; else temp=Q-dataQ-front; Q-count-
7、; Q-front=(Q-front+1)%QueueSize; return temp; void Breadth(Graph *G,int k) int i,j; AQueue Q; InitQueue( printf(“%cn“,G-vexsk); visitedk=TRUE; EnQueue( while (!QueueEmpty( for (j=0;jvexnum;j+) if(G-edgesij=1 visitedj=TRUE; EnQueue( void Breadthsearch(Graph *G) int i; for (i=0;ivexnum;i+) visitedi=FA
8、LSE; for (i=0;ivexnum;i+) if (!visitedi) Breadth(G,i); void main() Graph G; printf(“用邻接矩阵方式存储：用邻接矩阵方式存储：“ ) CreateGraph(printf(“深度优先搜索结果为：深度优先搜索结果为：“);printf(“n“); Depthsearch( printf(“广度优先搜索结果为：广度优先搜索结果为：“);printf(“n“); Breadthsearch( 结果：结果：（2）用邻接表的方式存储用邻接表的方式存储#include #include #include #include #
9、define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXVERTEX 50 typedef struct Node int elem;struct Node *next; Node,*QNode; typedef struct QNode front;/*对头指针对头指针*/QNode rear;/*队尾指针队尾指针*/ Queue; typedef struct ArcNode int adjvex; /*该边所指向的顶点的位置该边所指向的顶点的位置*/struct ArcNode *nextarc; /*指
10、向下一条边的指针指向下一条边的指针*/ ArcNode; typedef struct VNode int data; /*顶点信息顶点信息*/ ArcNode *firstarc; /*指向该顶点第一条弧的指针指向该顶点第一条弧的指针*/ VNode,AdjListMAXVERTEX; typedef struct AdjList vertices; int vexnum; /*节点的个数节点的个数*/int arcnum; /*边的条数边的条数*/ Graph; int VisitedMAXVERTEX; void InitQueue(Queue *Q)/*构造一个空队列构造一个空队列 Q
11、*/ Q-front=Q-rear=(QNode)malloc(sizeof(Node);if(!Q-front) exit(OVERFLOW);Q-front-next=NULL;BACDGFE void EnQueue(Queue *Q,int e)/*插入元素插入元素 e 为为 Q 新的队尾元素新的队尾元素*/ QNode p=(QNode)malloc(sizeof(Node);if(!p) exit(OVERFLOW);p-elem=e;p-next=NULL;Q-rear-next=p;Q-rear=p; void DeQueue(Queue *Q,int *e)/*若队列不为空，
12、则删除若队列不为空，则删除 Q 队头元素，用队头元素，用 e 返返 回回 其值，并返回其值，并返回 OK;否则返回否则返回 ERROR*/ QNode p;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;*e=p-elem;free(p); int QueueEmpty(Queue Q)/*若队列若队列 Q 为空队列，则返回为空队列，则返回 TURE，否则返回，否则返回 FALSE*/ if(Q.rear=Q.front) return TRUE;else return -1; int LocateVex(Graph
13、*G,int v) /*返回节点返回节点 v 在图中的位置在图中的位置*/ int i;for(i=0;ivexnum;+i)if(G-verticesi.data=v) break;else continue;if(ivexnum) return i;else return 0; /*创建创建*/ void CreateGraph(Graph *G) int m,n,i,j,k,v1,v2,flag=0;ArcNode *p1,*q1,*p,*q;printf(“请输入图的顶点数目请输入图的顶点数目: “);scanf(“%d“,printf(“请输入图的边的数目请输入图的边的数目: “);
14、scanf(“%d“,G-vexnum=m; /*顶点数目顶点数目*/G-arcnum=n; /*边的数目边的数目*/for(i=0;ivexnum;+i) G-verticesi.data=i+1; /*顶点信息顶点信息*/G-verticesi.firstarc=NULL;for(k=0;karcnum;+k) printf(“请输入第请输入第 %d 条边的起点和终点条边的起点和终点: “,k+1);scanf(“%d%d“,i=LocateVex(G,v1);j=LocateVex(G,v2);if(i=0p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=NULL;if(!G-verticesi.firstarc) G-verticesi.firstarc=p;elsefor(p1=G-ve
