图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。

图比树复杂，为了避免同一顶点被访问多次，可以设置一个辅助数组，初始值置为False或者0。当访问到后，设置值为真或被访问的次序ID。

图遍历主要有两种：深度优先搜索、广度优先搜索。

深度优先遍历

是树的先根遍历的推广。

从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v相连通的路径都被访问到。然后再另选一个未被访问的结点做为起始点。

代码如下：

void graph_dfs(struct Graph* g, int* visit, int i)
{
    struct Arc* ptr = g->vexs[i].first_arc; 
    // Visit
    printf("Visit %d\n", g->vexs[i].data);
    visit[i] = 1;
    // Visit neighor
    while(ptr!=NULL)    
    {   
        if(!visit[ptr->ivex])
        {   
            graph_dfs(g, visit, ptr->ivex);
        }   
        ptr = ptr->next;    
    }   
}

void graph_dfs_traverse(struct Graph* g)
{
    int i;
    int visit[MAX_VEXS];
    memset(visit, 0, sizeof(int)*MAX_VEXS);
    for(i=0; i<g->nvexs; i++)
    {   
        if(!visit[i])
        {   
            graph_dfs(g, visit, i); 
        }   
    }   
}

当用邻接矩阵(二维数组表示时)，查找顶点邻接点的复杂度为O(n^2)。

用邻接表时，实践复杂度为O(n+e)。

广度优先遍历

类似树的层次遍历。

使得“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。此时再选取图中另一个未曾被访问的顶点做为起始点。

实际是依次访问和v有路径、相连通且路径长度为1,2,3。。。的顶点。

和层次遍历一样，也要借助队列，代码如下：

void graph_bfs(struct Graph* g)
{
	int i, data;
	int flags[MAX_VEXS];
	struct Queue q;
	struct Arc* ptr;
	memset(flags, 0, sizeof(int)*MAX_VEXS);
	queue_init(&q);
	for(i=0; i<g->nvexs; i++)
	{
		if(!flags[i])
		{
			flags[i] = 1;
			graph_visit(g, i);
			queue_enqueue(&q, i);
			while(!queue_is_empty(&q))
			{
				queue_dequeue(&q, &data);
				ptr = g->vexs[data].first_arc;
				while(ptr!=NULL)
				{
					if(!flags[ptr->ivex])
					{
						flags[ptr->ivex] = 1;
						graph_visit(g, ptr->ivex);
						queue_enqueue(&q, ptr->ivex);
					}
					ptr = ptr->next;
				}
			}
		}	
	}
}