图的遍历方式有两种，分别是图的深度优先遍历和图的广度优先遍历

其中，深度优先遍历的应用更为广泛。

深度优先遍历同深度优先搜索，“不撞南墙不回头”

从一个点A出发再访问所有与之相连且未被访问过的点，如果全部被

访问过，就退回上一个点继续访问，我们可以用一个visited数组来

记录点是否被访问过，整个过程可以用递归实现。

 

比如上面这个图，它的深度优先遍历的顺序（从v1出发）

v1-v2-v5-v3-v4-v6(顺序可能不同）

 

再比如这个c图（树是特殊的图-有向无环图），它的深度优先遍历顺序是

v1-v2-v4-(没有与四相连未被访问过的点，退回V2)-v5-(退回V2,退回v1)-v3-v6-(退回v3)-v7

更加直观。

 

Code:

#include
     
      #include
      
       using namespace std;struct node{    int end;    int len;    int next;} ;node edge[2333];int n,m,first[2333],visited[2333],cnt;void add_edge(int s,int e,int d){    cnt++;    edge[cnt].end=e;    edge[cnt].len=d;    edge[cnt].next=first[s];    first[s]=cnt;    return;}void dfs(int s){    visited[s]=true;    printf("%d ",s);    for(int i=first[s];i!=0;i=edge[i].next)    {        if(!visited[i]) dfs(i);    }    return;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)    {        int s,e,d;        scanf("%d%d%d",&s,&e,&d);        add_edge(s,e,d);        add_edge(e,s,d);    }    for(int i=1;i<=n;i++)    {        if(!visited[i]) dfs(i);        printf("\n");    }    return 0;}
      
     

/使用边表存图./