我是参照《严蔚敏数据结构ppt》http://wenku.baidu.com/view/3ff16fc20242a8956aece41d.html以及《大话数据结构》来写的，因为ppt上有些错，而视频上的代码不全，自己另写了。ppt上错哪，我就不指出了，大家可以对照着看，就能发现不同之处。
struct 有3个，层层套用 ，学习struct的灵活运用。
#include<iostream> using namespace std; typedef char VertexType; //顶点类型 typedef int EdgeType; //边上的权值类型 #define MAXVEX 100 typedef struct EdgeNode //边表结点 { int adjvex; //邻接点域，存储该顶点的下标。怎么做到呢？是因为包含关系，被包含VertexNode里面 EdgeType weight; //权值 struct EdgeNode *next; //链域，指向下一个邻接点 }EdgeNode; typedef struct VertexNode //顶点表结点 { VertexType data; //这是顶点的名称（字母表示），这个和AdjList[MAXVEX] 中下标相对应 EdgeNode *firstedge; }VertexNode,AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; }GraphAdjList; //建立图的邻接表结构 void CreateALGraph(GraphAdjList *G) { int i,j,k; EdgeNode *e; cout<<"输入顶点数和边数"<<endl; cin>>G->numVertexes >>G->numEdges ; for(i=0;i<G->numVertexes ;i++) { cout<<"输入顶点变量："<<endl; cin>>G->adjList[i].data ; //建立顶点表 G->adjList [i].firstedge =NULL; //初始化,还没有内存，在下面出现 } for(k=0;k<G->numEdges ;k++) //建立边表 { cout<<"输入边（vi,vj）上的顶点序号："<<endl;//对于这里的编号应该与上面的一致，不然的话就用一个函数去求Location() cin>>i>>j; //向内存申请空间，指针初始化 e=(EdgeNode *)malloc(sizeof(EdgeNode)); e->adjvex =j; //邻接序号为j; e->next =G->adjList [i].firstedge ; G->adjList [i].firstedge=e; //相当于头结点一直在动，链表里的头插法 //因为是无向图，所以需要下面的 e=(EdgeNode *)malloc(sizeof(EdgeNode)); e->adjvex =i; //邻接序号为j; e->next =G->adjList [j].firstedge ; G->adjList [j].firstedge=e; } } //邻接表深度优先 typedef int Boolean; Boolean visited[MAXVEX]; void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i]=true; cout<<GL.adjList [i].data <<endl; p=GL.adjList [i].firstedge ; while(p) //为空就结束了 { if(!visited[p->adjvex ]) { DFS(GL,p->adjvex); } p=p->next; } } void DFSTraverse(GraphAdjList GL) { for(int i=0;i<MAXVEX;i++) { visited[i]=false; } for(int i=0;i<GL.numVertexes ;i++) { if(!visited[i]) { DFS(GL,i); } } } int main() { GraphAdjList p; CreateALGraph(&p); DFSTraverse(p); return 0; }随便画的一个图，遍历如下 无向图
遍历结果：
