7.4图的遍历
图的遍历是和树的遍历类似，我们希望从图中某一顶点出 发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍(Traversing Graph)。
7.4.1深度优先遍历
深度优先遍历（Deep_First_Search），称为简称DFS。
主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
实例如下，序号代表的是遍历的顺序
从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9
此时就从 9 回退到上一个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进行深度优先遍历
同理从 10 开始往上回溯到 6, 6 没有除 10 以外的子节点，再往上回溯，发现 3 有除 6 以外的子点 7，所以此时会遍历 7
从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进行遍历,这样就遍历完成了
这好像就是树的前序前序遍历啊实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。
7.4.2广度优先遍历
广度优先遍历(Breadth_ First Search)， 又称为广度优先搜索，简称BFS
指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点
它这个遍历类似图中的层序遍历
DFS 一般是解决连通性问题，而 BFS 一般是解决最短路径问题
#include<stdio.h> #include<stdlib.h> #define max 20 //边表节点 typedef struct node{ int adjvex; struct node *next; }eNode; //头节点 typedef struct headnode{ char vertex; eNode *firstedge; }hNode; //邻接表 typedef struct{ hNode adjlist[max]; int n,e; //顶点数，边数 }linkG;
#include<stdio.h> #include<stdlib.h> #define max 20 //边表节点 typedef struct node{ int adjvex; struct node *next; }eNode; //头节点 typedef struct headnode{ char vertex; eNode *firstedge; }hNode; //邻接表 typedef struct{ hNode adjlist[max]; int n,e; //顶点数，边数 }linkG; //创建（邻接表） linkG *creat(linkG *g,int c) //c为0表示无向图 { int i,j,k; eNode *s; int n1,e1; char ch; g=(linkG *)malloc(sizeof(linkG)); printf("请输入顶点数及边数: "); scanf("%d%d",&n1,&e1); g->n=n1;g->e=e1; printf("请输入顶点信息："); getchar(); for(i=0;i<n1;i++) { scanf("%c",&ch); g->adjlist[i].vertex=ch; g->adjlist[i].firstedge=NULL; } getchar(); int i1,j1; for(k=0;k<e1;k++) { printf("请输入对（i,j）: "); scanf("%d%d",&i1,&j1); s=(eNode *)malloc(sizeof(eNode)); s->adjvex=j1; s->next=g->adjlist[i1].firstedge; g->adjlist[i1].firstedge=s; if(c==0) { s=(eNode *)malloc(sizeof(eNode)); s->adjvex=i1; s->next=g->adjlist[j1].firstedge; g->adjlist[j1].firstedge=s; } } return g; } int visited[max]; //标记是否访问 //深度优先遍历DFS void dfs(linkG *g,int i) //顶点i { eNode *p; printf("%c ",g->adjlist[i].vertex); visited[i]=1; p=g->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) dfs(g,p->adjvex); p=p->next; } } void dfstravel(linkG *g) { int i; for(i=0;i<g->n;i++) visited[i]=0; for(i=0;i<g->n;i++) if(!visited[i]) dfs(g,i); } //广度优先遍历BFS void bfs(linkG *g,int i) { int j; eNode *p; int q[max],front,rear; front=rear=0; printf("%c ",g->adjlist[i].vertex); visited[i]=1; q[rear++]=i; while(rear>front) { j=q[front++]; p=g->adjlist[j].firstedge; while(p) { if(visited[p->adjvex]==0) { printf("%c ",g->adjlist[p->adjvex].vertex); q[rear++]=p->adjvex; visited[p->adjvex]=1; } p=p->next; } } } void bfstravel(linkG *g) { int i,count=0; for(i=0;i<g->n;i++) visited[i]=0; for(i=0;i<g->n;i++) if(!visited[i]) bfs(g,i); } //主函数 int main() { linkG *g; g=creat(g,0); printf("DFS："); dfstravel(g); printf("\n"); printf("BFS："); bfstravel(g); printf("\n"); }
