图的遍历源代码

#include <stdio.h>#include <stdlib.h>#define TElemType inttypedef struct BiTNode {TElemType data;struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;typedef BiTree DataType;typedef struct queuenode{DataType data;struct queuenode *next;} QueueNode;//LINKQUEUE//HEAD POINTER, AND REAR POINTER ARE A V ALIBALE typedef struct {QueueNode *front;QueueNode *rear;} LinkQueue;int InitQueue(LinkQueue *Q);int DestroyQueue(LinkQueue *Q);int QueueEmpty(LinkQueue Q);int EnQueue(LinkQueue *Q, DataType e);DataType DeQueue(LinkQueue *Q);int CreateBiTree(BiTree *T);int PreOrderTraverse(BiTree T, int (*visit)(TElemType e));int PreOrderTraverse2(BiTree T, int (*visit)(TElemType e));int InOrderTraverse(BiTree T, int (*visit)(TElemType e));int InOrderTraverse2(BiTree T, int (*visit)(TElemType e));int PostOrderTraverse(BiTree T, int (*visit)(TElemType e));int PostOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int LevelOrderTraverse(BiTree T, int (*visit)(TElemType e)); int printElem(TElemType e);int InitBiTree(BiTree *T);int DestroyBiTree(BiTree *T);int ClearBiTree(BiTree *T);int BiTreeEmpty(BiTree T);int BiTreeDepth(BiTree T);BiTNode *Parent(BiTree T, BiTNode *e);BiTNode *LeftChild(BiTree T, BiTNode *e);BiTNode *RightChild(BiTree T, BiTNode *e);BiTNode *LeftSibling(BiTree T, BiTNode *e);BiTNode *RightSibling(BiTree T, BiTNode *e);int InsertChild(BiTree T, BiTNode *p, int LR, BiTree C);int DeleteChild(BiTree T, BiTNode *p, int LR);int CountLeaf(BiTree T);int CreateBiTreeByPreInOrder(BiTree *T, int preorder[], int *idx,int inorder[], int low, int high,int length);int main(){BiTree bitree,bitree2;InitBiTree(&bitree);InitBiTree(&bitree2);printf("input tree 1:\n");CreateBiTree2(&bitree);printf("PreOrderTraverse:\n");PreOrderTraverse(bitree, printElem);printf("\n");printf("InOrderTraverse:\n");InOrderTraverse(bitree, printElem);printf("\n");printf("PostOrderTraverse:\n");PostOrderTraverse(bitree, printElem);printf("\n");printf("LevelOrderTraverse:\n");LevelOrderTraverse(bitree, printElem);printf("\n");printf("Depth is %d.\n", BiTreeDepth(bitree));printf("Count leaf is %d.\n", CountLeaf(bitree));DestroyBiTree(&bitree);DestroyBiTree(&bitree2);}int CreateBiTree(BiTree *T){int num;scanf("%d", &num);if (num == 0)*T = NULL;else {*T = malloc(sizeof(BiTNode));if (*T == NULL)return 0;(*T)->data = num;if (!CreateBiTree(&(*T)->lchild)) return 0;if (!CreateBiTree(&(*T)->rchild)) return 0;}return 1;}int PreOrderTraverse(BiTree T, int (*visit)(TElemType e)) {if (T) {//visit rootif (!(*visit)(T->data)) return 0;//visit left treeif (!PreOrderTraverse(T->lchild, visit)) return 0;//visit right treeif (!PreOrderTraverse(T->rchild, visit)) return 0;}return 1;}int PreOrderTraverse2(BiTree T, int (*visit)(TElemType e)) {//visit rootif (!(*visit)(T->data)) return 0;if (T->lchild)//visit left treeif (!PreOrderTraverse(T->lchild, visit)) return 0;if (T->rchild)//visit right treeif (!PreOrderTraverse(T->rchild, visit)) return 0;return 1;int InOrderTraverse(BiTree T, int (*visit)(TElemType e)) {if (T) {//visit left treeif (!InOrderTraverse(T->lchild, visit)) return 0;//visit rootif (!(*visit)(T->data)) return 0;//visit right treeif (!InOrderTraverse(T->rchild, visit)) return 0;}return 1;}int PostOrderTraverse(BiTree T, int (*visit)(TElemType e)) {if (T) {//visit left treeif (!PostOrderTraverse(T->lchild, visit)) return 0;//visit right treeif (!PostOrderTraverse(T->rchild, visit)) return 0;//visit rootif (!(*visit)(T->data)) return 0;}return 1;}int LevelOrderTraverse(BiTree T, int (*visit)(TElemType e)) {//defineLinkQueue queue;//initInitQueue(&queue);//root enqueueEnQueue(&queue, T);while(!QueueEmpty(queue)) {//dequeueBiTree node = DeQueue(&queue);if (node) {//visitif (!(*visit)(node->data)) return 0;//left child enqueueEnQueue(&queue, node->lchild);//right child enqueueEnQueue(&queue, node->rchild);}}DestroyQueue(&queue);return 1;}int printElem(TElemType e){printf("%d ", e);return 1;}int InitBiTree(BiTree *T){*T = NULL;return 1;}int DestroyBiTree(BiTree *T){if (*T) {//destroy left treeDestroyBiTree(&(*T)->lchild);//destroy right treeDestroyBiTree(&(*T)->rchild);//destroy rootfree(*T); *T = NULL;}return 1;}int ClearBiTree(BiTree *T){return DestroyBiTree(T);}int BiTreeEmpty(BiTree T){if (T)return 0;elsereturn 1;}int BiTreeDepth(BiTree T){if (!T)return 0;int ldepth = BiTreeDepth(T->lchild);int rdepth = BiTreeDepth(T->rchild);return (ldepth > rdepth ? ldepth : rdepth) + 1;}BiTNode *Parent(BiTree T, BiTNode *e){if (e == T) return NULL;//defineLinkQueue queue;//initInitQueue(&queue);//root enqueueEnQueue(&queue, T);BiTNode *node = NULL;while(!QueueEmpty(queue)) {//dequeuenode = DeQueue(&queue);if (node) {//compareif (e == node->lchild || e == node->rchild)break;//left child enqueueEnQueue(&queue, node->lchild);//right child enqueueEnQueue(&queue, node->rchild);}}DestroyQueue(&queue);return node;}BiTNode *LeftChild(BiTree T, BiTNode *e) {/* //defineLinkQueue queue;//initInitQueue(&queue);//root enqueueEnQueue(&queue, T);BiTNode *node = NULL;while(!QueueEmpty(queue)) {//dequeuenode = DeQueue(&queue);if (node) {//compareif (e == node)break;//left child enqueueEnQueue(&queue, node->lchild);//right child enqueueEnQueue(&queue, node->rchild);}}DestroyQueue(&queue);*/return e->lchild;}BiTNode *RightChild(BiTree T, BiTNode *e) {/* //defineLinkQueue queue;//initInitQueue(&queue);//root enqueueEnQueue(&queue, T);BiTNode *node = NULL;while(!QueueEmpty(queue)) {//dequeuenode = DeQueue(&queue);if (node) {//compareif (e == node)break;//left child enqueueEnQueue(&queue, node->lchild);//right child enqueueEnQueue(&queue, node->rchild);}}DestroyQueue(&queue);*/return e->rchild;}BiTNode *LeftSibling(BiTree T, BiTNode *e){BiTNode *parent, *lchild;if ((parent = Parent(T, e)) == NULL) return NULL;lchild = LeftChild(T, parent);if (lchild == e) return NULL;else return lchild;}BiTNode *RightSibling(BiTree T, BiTNode *e){BiTNode *parent, *rchild;if ((parent = Parent(T, e)) == NULL) return NULL;rchild = RightChild(T, parent);if (rchild == e) return NULL;else return rchild;}int InsertChild(BiTree T, BiTNode *p, int LR, BiTree C) {if (LR == 0) {C->rchild = p->lchild;p->lchild = C;} else {C->rchild = p->rchild;p->rchild = C;}return 1;}int DeleteChild(BiTree T, BiTNode *p, int LR){if (LR == 0)if (!DestroyBiTree(&p->lchild)) return 0;elseif (!DestroyBiTree(&p->rchild)) return 0;return 1;}int InitQueue(LinkQueue *Q){Q->front = Q->rear = malloc(sizeof(QueueNode));Q->front->next = NULL;}int DestroyQueue(LinkQueue *Q){QueueNode *p = Q->front, *q;do {q = p->next;free(p);p = q;} while (p!=NULL);Q->front = NULL;Q->rear = NULL;}int QueueEmpty(LinkQueue Q){return Q.front == Q.rear;}int EnQueue(LinkQueue *Q, DataType e){QueueNode *temp = malloc(sizeof(QueueNode));if (!temp) {printf("Memory is out! Cannot malloc.\n");return 0;}temp->data = e;temp->next = NULL;Q->rear->next = temp;Q->rear = temp;return 1;}DataType DeQueue(LinkQueue *Q){DataType ret = Q->front->next->data;QueueNode *p = Q->front->next;Q->front->next = Q->front->next->next;free(p);if (Q->front->next == NULL) Q->rear = Q->front;return ret;}int CountLeaf(BiTree T){if (T == NULL) return 0;if (T->lchild == NULL && T->rchild == NULL) return 1;return CountLeaf(T->lchild) + CountLeaf(T->rchild);}int CreateBiTree2(BiTree *T){int num, inorder[100], preorder[100], i = 0;printf("please input preorder:\n");while(scanf("%d", &num) != EOF) {preorder[i++] = num;}i = 0;printf("please input inorder:\n");while(scanf("%d", &num) != EOF) {inorder[i++] = num;}int index = -1;CreateBiTreeByPreInOrder(T, preorder, &index, inorder, 0, i-1, i);return 1;}int CreateBiTreeByPreInOrder(BiTree *T, int preorder[], int *idx,int inorder[], int low, int high, int length){(*idx)++;if (*idx >= length) {*T = NULL; return 1;}int i;for(i=low;i<=high;i++)if (inorder[i] == preorder[*idx]) break;if (i > high) {(*idx)--; *T = NULL; return 1;}*T = malloc(sizeof(BiTNode));if (*T == NULL)return 0;(*T)->data = preorder[*idx];if (!CreateBiTreeByPreInOrder(&(*T)->lchild, preorder, idx, inorder, low, i-1, length)) return 0;if (!CreateBiTreeByPreInOrder(&(*T)->rchild, preorder, idx, inorder, i+1, high, length)) return 0;return 1;}。

实验6.1实现图的存储和遍历一，实验目的掌握图的邻接矩阵和邻接表存储以及图的邻接矩阵存储的递归遍历。

二，实验内容6.1实现图的邻接矩阵和邻接表存储编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：（1）建立如教材图7.9所示的有向图G的邻接矩阵，并输出。

（2）由有向图G的邻接矩阵产生邻接表，并输出。

（3）再由（2）的邻接表产生对应的邻接矩阵，并输出。

6.2 实现图的遍历算法（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。

（5）利用非递归算法重解任务（4）。

（6）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。

三，源代码及结果截图#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<malloc.h>#define MAX_VERTEX_NUM 20typedef char VRType;typedef int InfoType; // 存放网的权值typedef char VertexType; // 字符串类型typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}/*建立有向图的邻接矩阵*/typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻;对带权图则为权值类型InfoType *info; //该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum,arcnum;;//图的当前顶点数和弧数GraphKind kind;//图的种类标志}MGraph;/* 顶点在顶点向量中的定位*/int LocateVex(MGraph &M,VRType v1){int i;for(i=0;i<M.vexnum;i++)if(v1==M.vexs[i])return i;return -1;}void CreateGraph(MGraph &M)//建立有向图的邻接矩阵{int i,j,k,w;VRType v1,v2;M.kind=DN;printf("构造有向网:\n");printf("\n输入图的顶点数和边数(以空格作为间隔):");scanf("%d%d",&M.vexnum,&M.arcnum);printf("输入%d个顶点的值(字符):",M.vexnum);getchar();for(i=0;i<M.vexnum;i++) //输入顶点向量{scanf("%c",&M.vexs[i]);}printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++){M.arcs[i][j].adj=0;M.arcs[i][j].info=NULL;}printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");for(k=0;k<M.arcnum;++k)// 构造表结点链表{cin>>w>>v1>>v2;i=LocateVex(M,v1);j=LocateVex(M,v2);M.arcs[i][j].adj=w;}}//按邻接矩阵方式输出有向图void PrintGraph(MGraph M){int i,j;printf("\n输出邻接矩阵:\n");for(i=0; i<M.vexnum; i++){printf("%10c",M.vexs[i]);for(j=0; j<M.vexnum; j++)printf("%2d",M.arcs[i][j].adj);printf("\n");}}// 图的邻接表存储表示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;void CreateMGtoDN(ALGraph &G,MGraph &M){//由有向图M的邻接矩阵产生邻接表int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph &G){ //由邻接表产生对应的邻接矩阵int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}//输出邻接表void PrintDN(ALGraph G){int i;ArcNode *p;printf("\n输出邻接表：\n");printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2c",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%c→%c(%d)\t",G.vertices[i].data,G.vertices[p->adjvex].data,p->info);p=p->nextarc;}printf("\n");}//for}int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)// 从第v个顶点出发递归地深度优先遍历图G。

遍历性源和混合源总结
遍历性和混合源(什么是遍历性，如何证明遍历性，什么是混合源)上面提到的离散源，就是离散马尔科夫过程。

这些马尔科夫过程的一个子集在通信理论中非常重要。

这个子集叫做遍历的马尔科夫过程，我们叫对应的源叫遍历源（ergodic source）。

遍历过程的正式定义有点复杂，想法还是比较简单的，就是过程产生的每个序列有相同的统计特性。

也可以把遍历性叫做统计同质性。

所有4中的过程都是ergodic的。

证明一个马尔科夫过程是ergodic的充分条件是它的图表示满足两个特性（1）不存在两个孤立的子图。

（2）所有闭序列长度的最大公约数是1。

混合源就是不满足（1）的源，但是它的孤立子图是ergodic的。

散信息源（怎样用数学形式表示信源，给定信息源的生成信息的速度是多少呢，为什么要研究信息源）我们可以看到上文中求解信道的C的时候只用到了信号的持续时间，而没有过分关注信源。

所以信道相对独立，我们可以通过研究信号源的特性，然后通过适当的编码来降低对信道capacity的要求（研究信源的原因）。

信源传输的序列往往是有规律的，这个规律的数学模型就是随机过程，离散信息源是一个随机过程，任何从有限符号集合中选择符号产生符号序列的随机过程就是离散信源。

常见的离散源有（A）比如英语、德语、汉语等自然语言。

（B）通过量化过程的连续源，比如经过了PCM发送器的量化语音等。

（C）数学定义的随机过程，它能够生成一个符号序列。

最general的case就是n-gram模型，它的统计结构由p(i1,i2,...,in)
或者pi1,i2,...,in−1(in)确定。

深度优先遍历算法实现及复杂度分析深度优先遍历算法（Depth First Search, DFS）是一种常用的图遍历算法，用于查找或遍历图的节点。

本文将介绍深度优先遍历算法的实现方法，并进行对应的复杂度分析。

一、算法实现深度优先遍历算法的基本思想是从图的某个节点出发，沿着深度方向依次访问其相邻节点，直到无法继续下去，然后返回上一层节点继续遍历。

下面是深度优先遍历算法的伪代码：```1. 初始化访问标记数组visited[]，将所有节点的访问标记置为false。

2. 从某个节点v开始遍历：- 标记节点v为已访问（visited[v] = true）。

- 访问节点v的相邻节点：- 若相邻节点w未被访问，则递归调用深度优先遍历算法（DFS(w)）。

3. 遍历结束，所有节点都已访问。

```二、复杂度分析1. 时间复杂度深度优先遍历算法的时间复杂度取决于图的存储方式和规模。

假设图的节点数为V，边数为E。

- 邻接表存储方式：对于每个节点，需要访问其相邻节点。

因此，算法的时间复杂度为O(V+E)。

- 邻接矩阵存储方式：需要检查每个节点与其他节点的连通关系，即需要遍历整个邻接矩阵。

因此，算法的时间复杂度为O(V^2)。

2. 空间复杂度深度优先遍历算法使用了一个辅助的访问标记数组visited[]来记录每个节点的访问状态。

假设图的节点数为V。

- 邻接表存储方式：访问标记数组visited[]的空间复杂度为O(V)。

- 邻接矩阵存储方式：访问标记数组visited[]的空间复杂度同样为O(V)。

综上所述，深度优先遍历算法的时间复杂度为O(V+E)，空间复杂度为O(V)。

三、应用场景深度优先遍历算法在图的遍历和搜索问题中广泛应用。

以下是一些典型的应用场景：1. 连通性问题：判断图中两个节点之间是否存在路径。

2. 非连通图遍历：对于非连通图，深度优先遍历算法可以用于遍历所有连通分量。

3. 寻找路径：在图中寻找从起始节点到目标节点的路径。

-实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储构造；掌握DFS及BFS对图的遍历操作；了解图构造在人工智能、工程等领域的广泛应用。

二、要求采用邻接矩阵和邻接链表作为图的存储构造，完成有向图和无向图的DFS 和BFS操作。

三、DFS和BFS 的根本思想深度优先搜索法DFS的根本思想：从图G中*个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。

如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。

直到图中所有的顶点都被访问。

广度优先算法BFS的根本思想：从图G中*个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。

如此继续，直到访问完图中的所有顶点。

四、例如程序1．邻接矩阵作为存储构造的程序例如#include"stdio.h"#include"stdlib.h"#define Ma*Verte*Num 100 //定义最大顶点数typedef struct{char ve*s[Ma*Verte*Num]; //顶点表int edges[Ma*Verte*Num][Ma*Verte*Num]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e}MGraph; //用邻接矩阵表示的图的类型//=========建立邻接矩阵=======void CreatMGraph(MGraph *G){int i,j,k;char a;printf("Input Verte*Num(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数scanf("%c",&a);printf("Input Verte* string:");for(i=0;i<G->n;i++){scanf("%c",&a);G->ve*s[i]=a; //读入顶点信息，建立顶点表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0; //初始化邻接矩阵printf("Input edges,Creat Adjacency Matri*\n");for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵 scanf("%d%d",&i,&j); //输入边〔Vi，Vj〕的顶点序号G->edges[i][j]=1;G->edges[j][i]=1; //假设为无向图，矩阵为对称矩阵；假设建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedef enum{FALSE,TRUE} Boolean;Boolean visited[Ma*Verte*Num];//========DFS：深度优先遍历的递归算法======void DFSM(MGraph *G,int i){ //以Vi为出发点对邻接矩阵表示的图G进展DFS搜索，邻接矩阵是0，1矩阵 int j;printf("%c",G->ve*s[i]); //访问顶点Vivisited[i]=TRUE; //置已访问标志for(j=0;j<G->n;j++) //依次搜索Vi的邻接点if(G->edges[i][j]==1 && ! visited[j])DFSM(G,j); //〔Vi，Vj〕∈E，且Vj未访问过，故Vj为新出发点}void DFS(MGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE; //标志向量初始化for(i=0;i<G->n;i++)if(!visited[i]) //Vi未访问过DFSM(G,i); //以Vi为源点开场DFS搜索}//===========BFS：广度优先遍历=======void BFS(MGraph *G,int k){ //以Vk为源点对用邻接矩阵表示的图G进展广度优先搜索 int i,j,f=0,r=0;int cq[Ma*Verte*Num]; //定义队列for(i=0;i<G->n;i++)visited[i]=FALSE; //标志向量初始化for(i=0;i<G->n;i++)cq[i]=-1; //队列初始化printf("%c",G->ve*s[k]); //访问源点Vkvisited[k]=TRUE;cq[r]=k; //Vk已访问，将其入队。

HUNAN UNIVERSITY数据结构实验报告题目：图的遍历问题学生姓名梁天学生学号************专业班级计科1403指导老师夏艳日期2016.05.14背景网络蜘蛛即Web Spider，是一个很形象的名字。

把互联网比喻成一个蜘蛛网，那么Spider 就是在网上爬来爬去的蜘蛛。

网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。

如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。

这样看来，网络蜘蛛就是一个爬行程序，一个抓取网页的程序。

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下面这张简单化的网页连接模型图所示，其中A为起点也就是蜘蛛索引的起点）。

深度优先顾名思义就是让网络蜘蛛尽量的在抓取网页时往网页更深层次的挖掘进去讲究的是深度!也泛指: 网络蜘蛛将会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接! 则访问的节点顺序为==> A --> B --> E --> H --> I --> C --> D --> F --> K --> L --> G。

深度爬行的优点是:网络蜘蛛程序在设计的时候相对比较容易些；缺点是每次爬行一层总要向"蜘蛛老家" 数据库访问一下。

问问老总有必要还要爬下一层吗! 爬一层问一次.... 如果一个蜘蛛不管3721不断往下爬很可能迷路更有可能爬到国外的网站去，不仅增加了系统数据的复杂度更是增加的服务器的负担。

广度优先在这里的定义就是层爬行，即一层一层的爬行，按照层的分布与布局去索引处理与抓取网页。

则访问的节点顺序为==> A --> B --> C --> D --> E --> F --> G --> H --> I--> K --> L。

实现图的遍历算法实验报告实现图的遍历算法实验报告⼀实验题⽬: 实现图的遍历算法⼆实验要求:2.1:（1）建⽴如图（p126 8.1）所⽰的有向图 G 的邻接矩阵，并输出之（2）由有向图G的邻接矩阵产⽣邻接表，并输出之（3）再由（2）的邻接表产⽣对应的邻接矩阵，并输出之2.2 （1）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（递归算法）（2）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（⾮递归算法）（3）输出如图8.1所⽰的有向图G从顶点0开始的⼴度优先遍历序列三实验内容:3.1 图的抽象数据类型:ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={|v,w∈V且P(v,w)，表⽰从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph( &G )初始条件：图G存在。

操作结果：销毁图G。

LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。

GetVex( G, v )初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的值。

PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。

初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的第⼀个邻接顶点。

若顶点在G中没有邻接顶点，则返回“空”。

NextAdjVex( G, v, w )初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：返回v的（相对于w的）下⼀个邻接顶点。

若w是v 的最后⼀个邻接点，则返回“空”。

InsertVex( &G, v )初始条件：图G存在，v和图中顶点有相同特征。