数据结构-图的相关代码

#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_NAME 10 #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR -1 #define TRUE 1 #define FALSE 0 typedef int InfoType; // 存放网的权值 typedef int Status; typedef int Boolean; typedef char VertexType[MAX_NAME]; // 字符串类型 typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网} Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针） }ArcNode; // 表结点 typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct { AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 }ALGraph; typedef int QElemType; // 队列类型 // 单链队列－－队列的链式存储结构 typedef struct QNode { QElemType data; //数据域 struct QNode *next; //指针域 }QNode,*QueuePtr; typedef struct { QueuePtr front, //队头指针，指针域指向队头元素 rear; //队尾指针，指向队尾元素 }LinkQueue; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 Status LocateVex(ALGraph G,VertexType u) { int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } // 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。 Status CreateGraph(ALGraph &G) { int i,j,k; int w; // 权值 VertexType va,vb; ArcNode *p; printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): "); scanf("%d",&G.kind); printf("请输入图的顶点数和边数:（空格）\n"); scanf("%d%d", &G.vexnum, &G.arcnum); printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME); for(i = 0; i < G.vexnum; ++i) // 构造顶点向量 { scanf("%s", G.vertices[i].data); G.vertices[i].firstarc = NULL; } if(G.kind == 1 || G.kind == 3) // 网 printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n"); else // 图 printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n"); for(k = 0;k < G.arcnum; ++k) // 构造表结点链表 { if(G.kind==1||G.kind==3) // 网 scanf("%d%s%s",&w,va,vb); else // 图 scanf("%s%s",va,vb); i = LocateVex(G,va); // 弧尾 j = LocateVex(G,vb); // 弧头 p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = j; if(G.kind == 1 || G.kind == 3) // 网 { p->info = (int *)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 图 p->nextarc = G.vertices[i].firstarc; // 插在表头 G.vertices[i].firstarc = p; if(G.kind >= 2) // 无向图或网,产生第二个表结点 { p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = i; if(G.kind == 3) // 无向网 { p->info = (int*)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 无向图 p->nextarc = G.vertices[j].firstarc; // 插在表头 G.vertices[j].firstarc = p; } } return OK; } // 输出图的邻接表G。 void Display(ALGraph G) { int i; ArcNode *p; switch(G.kind) { case DG: printf("该图的类型为：有向图\n"); break; case DN: printf("该图的类型为：有向网\n"); break; case AG: printf("该图的类型为：无向图\n"); break; case AN: printf("该图的类型为：无向网\n"); } printf("该图有 %d 个顶点：\n",G.vexnum); printf("该图的顶点信息如下：\n"); for(i = 0; i < G.vexnum; ++i) printf("%s ",G.vertices[i].data); printf("\n该图有 %d 条弧(边):\n", G.arcnum); for(i = 0; i < G.vexnum; i++) { p = G.vertices[i].firstarc; while(p) { if(G.kind <= 1) // 有向 { printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data); if(G.kind == DN) // 网 printf(":%d ", *(p->info)); } else // 无向(避免输出两次) { if(i < p->adjvex) { printf("%s－%s ",G.vertices[i].data,G.vertices[p->adjvex].data); if(G.kind == AN) // 网 printf(":%d ",*(p->info)); } } p=p->nextarc; } printf("\n"); } } Status pnt(VertexType e) //输出函数 { printf(" %s",e); return OK; } // 返回v的值。 VertexType* GetVex(ALGraph G,int v) { if(v>=G.vexnum||v<0) exit(0); return &G.vertices[v].data; } // 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。 int FirstAdjVex(ALGraph G,VertexType v) { ArcNode *p; int v1; v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 p = G.vertices[v1].firstarc; if(p) return p->adjvex; else return -1; } // 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个 // 邻接点, 则返回-1。 int NextAdjVex(ALGraph G,VertexType v,VertexType w) { ArcNode *p; int v1,w1; v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 w1 = LocateVex(G,w); // w1为顶点w在图G中的序号 p = G.vertices[v1].firstarc; while(p&&p->adjvex != w1) // 指针p不空且所指表结点不是w p = p->nextarc; if(!p||!p->nextarc) // 没找到w或w是最后一个邻接点 return -1; else // p->adjvex==w // 返回v的(相对于w的)下一个邻接顶点的序号 return p->nextarc->adjvex; } // 构造一个空队列Q。 int InitQueue(LinkQueue *Q) { (*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode)); //动态分配一个空间 if(!(*Q).front) exit(0); (*Q).front->next = NULL; //队头指针指向空，无数据域，这样构成了一个空队列 return 1; } // 插入元素e为Q的新的队尾元素。 int EnQueue(LinkQueue *Q, QElemType e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if( !p ) // 存储分配失败 exit(0); // 生成一个以为e为数据域的队列元素 p->data = e; p->next = NULL; //将该新队列元素接在队尾的后面 (*Q).rear->next = p; (*Q).rear = p; return 1; } // 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0。 int DeQueue(LinkQueue *Q,QElemType *e) { QueuePtr p; if((*Q).front==(*Q).rear) return 0; p=(*Q).front->next; //队头元素 *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return 1; } // 若Q为空队列,则返回1,否则返回0。 int QueueEmpty(LinkQueue Q) { if(Q.front == Q.rear) return 1; else return 0; } // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 void BFSTraverse(ALGraph G,Status(*Visit)(VertexType)) { int v,u,w; VertexType u1,w1; LinkQueue Q; for(v = 0; v < G.vexnum; ++v) visited[v]=0; // 置初值 InitQueue(&Q); // 置空的辅助队列Q for(v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图 if(!visited[v]) // v尚未访问 { visited[v]=1; Visit(G.vertices[v].data); EnQueue(&Q,v); // v入队列 while(!QueueEmpty(Q)) // 队列不空 { DeQueue(&Q,&u); // 队头元素出队并置为u strcpy(u1,*GetVex(G,u)); for(w = FirstAdjVex(G,u1); w >= 0; w = NextAdjVex(G, u1, strcpy(w1, *GetVex(G,w)))) if(!visited[w]) // w为u的尚未访问的邻接顶点 { visited[w] = 1; Visit(G.vertices[w].data); EnQueue(&Q,w); // w入队 } } } printf("\n"); } void main() { ALGraph G; printf("请选择有向图\n"); CreateGraph(G); Display(G); // printf("按照广度优先遍历，遍历过程如下：\n"); //BFSTraverse(G,pnt); //广度优先遍历图 }