原理博主就不讲了，毕竟其他人写的很好了，这里写一个实现样例。 无向图+邻接链表+深度优先搜索 如下
#include <iostream> #include <bits/stdc++.h> using namespace std; #define MAX 105 typedef struct ARCNode //边节点 { int adjvex; //这条边指向的顶点的位置 struct ARCNode * nextarc; //下一个边节点 }ARCNode; typedef struct Vnode //顶点信息 { char data; //存放着数据 ARCNode *first; //与它连接的第一条边的信息 }Vnode,Adjlist[MAX]; //一个顶点 很多个顶点 typedef struct { Adjlist vertices; //这是一个顶点数组 int vexnum,arcnum; //顶点的数目，边的数目 }ALGraph; int LocateVex(ALGraph T,char data) { for(int i=0;i<T.vexnum;i++) { if(T.vertices[i].data==data) return i; //找到了就返回这个顶点数据的索引 } return -1; //-1表示没有找到 } void CreateUDG(ALGraph &G) { cin>>G.vexnum>>G.arcnum; //输入总顶点数目，总边数目 for(int i=0;i<G.vexnum;i++) { cin>>G.vertices[i].data; G.vertices[i].first=NULL; //一开始指向空地方 } for(int k=0;k<G.arcnum;k++) { char a,b; int i,j; cin>>a>>b; //输入顶点 i=LocateVex(G,a); j=LocateVex(G,b); ARCNode * p1=new ARCNode; ARCNode * p2=new ARCNode; p1->adjvex=j; p1->nextarc=G.vertices[i].first; //头插法 G.vertices[i].first=p1; //图是无向的，因此是相互的 p2->adjvex=i; p2->nextarc=G.vertices[j].first; G.vertices[j].first=p2; } } //这个函数的作用是返回第一个邻接边顶点在数组中的索引 int FirstAdjvex(ALGraph &T,int v) { return T.vertices[v].first->adjvex; } //返回邻接边w的下一个邻接边的索引，不存在的话则返回-1，作为标志 int NextAdjVex(ALGraph &T,int v,int w) { ARCNode *p; p=T.vertices[v].first; while(p->adjvex!=w){p=p->nextarc;} p=p->nextarc; if(p!=NULL) return p->adjvex; else return -1; } //接下来是一个重点，是图的变量，有两种，一种是深度优先搜索，另一种是广度优先搜索，这两种方法是比较常用的 //无论是哪一种方法，都避免不了设置访问标志，即需要一个数组来存储访问记录 bool visited[MAX]; //顶点遍历标记 void DFS(ALGraph &T,int v) //从第v个顶点出发递归地深度优先遍历图 连通图 { cout<<T.vertices[v].data<<" "; visited[v]=true; for(int w=FirstAdjvex(T,v);w>=0;w=NextAdjVex(T,v,w)) //FirstAdjvex检查所有的邻节点 { if(!visited[w]) DFS(T,w); } } void DFSTraverse(ALGraph &T) //深度优先遍历非连通图 { for(int i=0;i<T.vexnum;i++) visited[i]=false; for(int i=0;i<T.vexnum;i++) if(!visited[i]) DFS(T,i); } int main() { ALGraph T; CreateUDG(T); DFS(T,0); //遍历连通图结果，需要指出从哪个顶点开始遍历，这里注意，是顶点的索引 //DFSTraverse(T); //遍历非连通图连通图 return 0; }测试结果如下： 建立的图的关系如下 a-----b-----e | | | d c 然后再数组链表中大概是这么链接的 顶点数组 0 a 1 b 2 c 3 d 4 e 里面深层的关系图 ,有点抽象- - dbq 0 a first=> 3 c next=>1 b next=>NULL; 1 b first=>3 d next=>4 e next=>NULL; 2 c first=>NULL; 3 d first=>NULL; 4 e first=>NULL;
