图的遍历设计.doc

#define MAX_VEX 100 / 最大顶点数为100#include #includetypedef struct node / 定义表结点 int adjvex; / 邻接顶点域 struct node *next; / 指向下一个邻接顶点的指针域 ARCNODE;typedef struct vexnode / 定义头结点 int vertex; / 顶点域 ARCNODE *firstarc; / 边表头指针 VEXNODE; / VEXNODE是以邻接表方式存储的图类型VEXNODE adjlist3MAX_VEX; /*定义头结点数组*/VEXNODE adjlist1MAX_VEX; /*定义表头向量adjlist*/int creatadjlist() /*建立邻接表*/ ARCNODE *ptr; int arcnum, vexnum, k, v1, v2; printf(请输入顶点数和边数(输入格式为:顶点数,边数):); scanf(%d,%d, &vexnum, &arcnum); /*输入图的顶点数和边数（弧数）*/ for (int o = 0; o 2; o+) for (k = 1; k = vexnum; k+) adjlistok.firstarc = 0; /*为邻接链表的adjlist数组各元素的链域赋初值*/ for (k = 0; k arcnum; k+) /*为adjlist数组的各元素分别建立各自的链表*/ printf(v1,v2=); scanf(%d,%d, &v1, &v2); for (int j = 0; j adjvex = v2; /*将顶点v2插入到链表中，使得结点插入后单链表仍然有序*/ ptr-next = adjlistjv1.firstarc; adjlistjv1.firstarc = ptr; /*将邻接点V2 插入表头结点V1 之后*/ return (vexnum);void dfs(int v) int w; ARCNODE *p; p = adjlist0v.firstarc; printf(%d , v); /*输出访问顶点*/ adjlist0v.vertex = 1; /*顶点标志域置1，表明已经访问过*/ while (p != NULL) w = p-adjvex; /*取出顶点V的某邻接点的序号*/ if (adjlist0w.vertex = 0) dfs(w); /*如果该定点未访问过则递归调用，从该顶点出发，沿着它的各邻接点向下搜索*/ p = p-next; void bfs(int v) /*从某顶点V出发按广度优先搜索进行图的遍历*/ int queueMAX_VEX; int front = 0, rear = 1; ARCNODE *p; p = adjlist1v.firstarc; printf(%d , v); /*访问初始顶点*/ adjlist1v.vertex = 1; queuerear = v; while (front != rear) front = (front + 1) % MAX_VEX; v = queuefront; /*按访问次序依次出队*/ p = adjlist1v.firstarc; /*查找V的邻接点*/ while (p != NULL) if (adjlist1p-adjvex.vertex = 0) adjlist1p-adjvex.vertex = 1; printf(%d , p-adjvex); /*访问该点并使之入队*/ rear = (rear + 1) % MAX_VEX; queuerear = p-adjvex; p = p-next; /*查找V的下一邻接点 */ int creatadjlist1() /*建立邻接表*/ ARCNODE *ptr; int arcnum, vexnum, k, v1, v2; printf(n请输入顶点数和边数(输入格式为:顶点数,边数):); scanf(%d,%d, &vexnum, &arcnum); /*输入图的顶点数和弧数(或边数)*/ for (k = 1; k = vexnum; k+) adjlist1k.firstarc = NULL; /*邻接链表的adjlist数组各元素的链域赋初值*/ adjlist1k.vertex = 0; /*各顶点的入度赋初值0*/ for (k = 1; k = arcnum; k+) /*为adjlist数组的各元素分别建立各自的链表*/ scanf(%d,%d, &v1, &v2); /*输入弧*/ ptr = (ARCNODE*) malloc(sizeof (ARCNODE); /*给结点V1 的相邻结点V2 分配内存空间*/ ptr-adjvex = v2; ptr-next = adjlist1v1.firstarc; adjlist1v1.firstarc = ptr; /*将相邻结点V2插入表头结点V1之后*/ adjlist1v2.vertex+; /*顶点V2的入度加1*/ return (vexnum);void toposort(int n) /*拓扑排序算法,n为图中顶点的个数*/ int queueMAX_VEX; int front = 0, rear = 0; int v, w, n1; ARCNODE *p; n1 = 0; for (v = 1; v adjvex; adjlist1w.vertex-; /*将邻接于顶点V的顶点的入度减1*/ if (adjlist1w.vertex = 0) /*将入度为0的顶点入队*/ rear = (rear + 1) % MAX_VEX; queuerear = w; p = p-next; /*p指向下一个邻接于顶点V的顶点*/ if (n1 n) /*输出的顶点个数小于图的顶点个数，则拓扑排序失败*/ printf(Not a set of partial order. n);main() /*主函数*/ int i, n, v, m; ARCNODE *p; n = creatadjlist(); /*建立邻接表并返回顶点个数*/ printf(输入深度优先搜索起始顶点v:); scanf(%d, &v); printf(图的深度优先搜索序列DFS :); dfs(v); print