图的遍历是指从某个顶点出发，沿着某条搜索路径对图中所有的顶点进行访问且仅访问一次的过程。
1． 深度优先搜索（DFS）
深度优先搜索类似于树的前序遍历，也是一遇到顶点就进行访问。其特点是尽可能先对纵深方向进行搜索，因此很容易用递归算法实现。如果将遍历过程中走过的边连接起来，即可得到深度优先遍历生成树。
深度优先搜索遍历图的算法：首先访问指定的起始顶点v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3。依次类推，直到一个所有邻接顶点都被访问过为止。
2． 广度优先搜索（BFS）
广度优先搜索类似于树的按层次遍历。首先访问指定的起始点v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，… wk，然后再依次从w1，w2，… wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。
广度优先遍历的特点是尽可能进行横向搜索，即最先访问的顶点其邻接点也被先访问。因此，借助一个队列来保存已被访问过的顶点序列。访问一个顶点vi时（出队），同时将vi相邻的其余结点入队。每个顶点只能入队一次。
图采用邻接链表结构存储。参考程序：
#define maxnode 40
#define null 0
#define m 20
#include <stdio.h>
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
int queue[maxnode];
void dfs(adjlist g,int k,int visited[]) //从顶点k出发，深度优先搜索
{arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}
void bfs(adjlist g,int k,int visited[]) //从顶点k出发，广度优先搜索
{int front=0,rear=1,w;
arcnode *p;
visited[k]=1; //访问初始顶点
printf("%d",k);
queue[rear]=k; //初始顶点入队列
while(front!=rear) //队列不为空
{front=(front+1)%m;
w=queue[front]; //按访问次序依次出队列
p=g[w].firstarc;
while(p!=null)
{if(visited[p->adjvex]==0)
{visited[p->adjvex]=1;
printf("%d",p->adjvex);
rear=(rear=1)%m;
queue[rear]=p->adjvex;;
}
p=p->nextarc;
}
}
}
void trave_bfs(adjlist g,int n)
{int i,visited[maxnode]; //数组visited标志图中的顶点是否已被访问
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
bfs(g,i,visited);
}
void trave_dfs(adjlist g,int n)
{int i,visited[maxnode]; //数组visited标志图中的顶点是否已被访问
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
void print(adjlist g,int n)
{arcnode *q;
int i;
printf("输出无向图的邻接链表示：\n");
for(i=1;i<=n;i++)
{printf("\t%d\t",i);
printf("%d->",g[i].vertex);
q=g[i].firstarc;
while(q!=null)
{printf("%d",q->adjvex);
printf("%d->",q->weight);
q=q->nextarc;
}
printf("\n");
}
}
main()
{arcnode *p,*q;
adjlist g;
int i,j,n,k,w,e;
printf("输入图中顶点的个数,边数：");
scanf("%d,%d",&n,&e);
for(k=1;k<=n;k++)
{getchar();
printf("\t第%d个顶点信息:",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null; //对顺序存储部分初始化
}
for(k=1;k<=e;k++)
{printf("第%d条边的起点，终点，权值：",k);
scanf("%d,%d,%d",&i,&j,&w);
q=(arcnode *)malloc(sizeof(arcnode));
q->adjvex=j;
q->weight=w;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=i;
p->weight=w;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
print(g,n);
printf("\n");
printf("图的深度优先搜索:");
trave_dfs(g,n);
printf("\n");
printf("图的广度优先搜索:");
trave_bfs(g,n);
printf("\n");
}
