《图的邻接表存储和深度搜素最终》由会员分享，可在线阅读，更多相关《图的邻接表存储和深度搜素最终（7页珍藏版）》请在金锄头文库上搜索。
1、图的邻接表存储和深度搜素最终图的邻接表存储和深度搜素最终#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;/ 表结点
2、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;iadj
3、vex=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(*Visi
4、tFunc)(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
5、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
6、)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;
