资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
图的邻接表存储和深度搜素最终图的邻接表存储和深度搜素最终#include #include #include #define MAX_NAME 5/ 顶点字符串的最大长度 #define MAX_VERTEX_NUM 20typedef int InfoType;/ 存放网的权值 typedef char VertexTypeMAX_NAME;/ 字符串类型 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 InfoType *info;/ 权值指针 ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 ALGraph;/ 若 G 中存在顶点 u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u)int i;for(i=0;iadjvex=j;p-info =NULL; / 图 p-nextarc=(*G).verticesi.firstarc; / 插在表头 (*G).verticesi.firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode); / 无向图,产生第二个表结点 p-adjvex=i;p-info=NULL; / 无向图 p-nextarc=(*G).verticesj.firstarc; / 插在表头 (*G).verticesj.firstarc=p;return 1;int visitedMAX_VERTEX_NUM;/ 访问标志数组(全局量) void(*VisitFunc)(char* v);/ 函数变量(全局量) / 返回 v 的第一个邻接顶点的序号。若顶点在 G 中没有邻接顶点,则返回-1。int FirstAdjVex(ALGraph G,VertexType v)ArcNode *p;int v1;v1=LocateVex(G,v); / v1 为顶点 v 在图 G 中的序号 p=G.verticesv1.firstarc;if(p)return p-adjvex;elsereturn -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.verticesv1.firstarc;while(pif(!p|!p-nextarc) / 没找到 w 或 w 是最后一个邻接点 return -1;else return p-nextarc-adjvex;/ 返回 v 的(相对于 w 的)下一个邻接顶点的序号 VertexType *GetVex(ALGraph G,int v)if(vG.vexnum|v=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)if(!visitedw)DFS(G,w);/ 对 v 的尚未访问的邻接点 w 递归调用DFS / 算法 7.4 P169/ 对图 G 作深度优先遍历。void DFSTraverse(ALGraph G,void(*Visit)(char*)int v;VisitFunc=Visit; / 使用全局变量 VisitFunc,使 DFS 不必设函数指针参数for(v=0; vadjvex)/ 无向(避免输出两次) printf(“%s%s “,G.verticesi.data,G.verticesp-adjvex.data);p=p-nextarc;printf(“n“);void print(char *i)printf(“%s “,i);int main()int i,j,k,n;ALGraph g;VertexType v1,v2;CreateGraph(Display(g);printf(“深度优先搜索的结果:n“);DFSTraverse(g,print);return 0;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号