提供了邻接表结构体的标准类型；
以及基于该类型结构体的深搜函数;
void CreateAdj(AdjGraph *&G) { //创建图的邻接表 int i,j; int n; int A[MAXN][MAXN]; printf("请输入矩阵的阶数:\n"); scanf("%d",&n); printf("请输入一个%d*%d的邻接矩阵\n",n,n); for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d",&A[i][j]); ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for (i=0; i<n; i++) //给邻接表中所有头结点的指针域置初值 G->adjlist[i].firstarc=NULL; for (i=0; i<n; i++) //检查邻接矩阵中每个元素 for (j=n-1; j>=0; j--) if (A[i][j]!=0 ) { //存在一条边 n++; p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p p->adjvex=j; //存放邻接点 p->weight=A[i][j]; //存放权 p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点p G->adjlist[i].firstarc=p; } G->n=n; } void DFS(AdjGraph *G,int v) { ArcNode *p; int w; visited[v]=1; //置已访问标记 printf("%d ",v); //输出被访问顶点的编号 p=G->adjlist[v].firstarc; //p指向顶点v的第一条边的边头结点 while (p!=NULL) { w=p->adjvex; if (visited[w]==0) DFS(G,w); //若w顶点未访问，递归访问它 p=p->nextarc;//p指向顶点v的下一条边的边头结点 } }
#include<iostream> #include<cstdio> #include<cmath> #include<malloc.h> using namespace std; const int MAXN=100; bool visited[MAXN]; typedef struct ANode { int adjvex; //该边的终点编号 struct ANode *nextarc; //指向下一条边的指针 int weight; //该边的权值等信息 } ArcNode;//边的结构体类型 typedef struct Vnode { int data; //顶点信息 ArcNode *firstarc; //指向第一条边 } VNode;//邻接表表头类型 typedef struct { VNode adjlist[MAXN]; //邻接表 int n,e; //图中顶点数n和边数e } AdjGraph;//图的邻接表结构体类型 void CreateAdj(AdjGraph *&G) ; void DFS(AdjGraph *G,int v) ; int main() { AdjGraph *G;//声明指针 CreateAdj(G); DFS(G,0); return 0; } //接下来尝试非递归的方法构造深搜函数 void CreateAdj(AdjGraph *&G) { //创建图的邻接表 int i,j; int n; int A[MAXN][MAXN]; printf("请输入矩阵的阶数:\n"); scanf("%d",&n); printf("请输入一个%d*%d的邻接矩阵\n",n,n); for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d",&A[i][j]); ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for (i=0; i<n; i++) //给邻接表中所有头结点的指针域置初值 G->adjlist[i].firstarc=NULL; for (i=0; i<n; i++) //检查邻接矩阵中每个元素 for (j=n-1; j>=0; j--) if (A[i][j]!=0 ) { //存在一条边 n++; p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p p->adjvex=j; //存放邻接点 p->weight=A[i][j]; //存放边权 p->nextarc=G->adjlist[i].firstarc; //采用头插法插入结点p G->adjlist[i].firstarc=p; } G->n=n; } void DFS(AdjGraph *G,int v) { ArcNode *p; int w; int Q[MAXN*10],top=0; Q[++top]=v; visited[v]=1; //置已访问标记 printf("%d ",v); //输出被访问顶点的编号 p=G->adjlist[v].firstarc;//p指向顶点v的第一条边的边头结点 bool flag=0; while(top>0) { //栈非空时 v=Q[top]; p=G->adjlist[v].firstarc; if(p) { w=p->adjvex; while(visited[w]&&p->nextarc!=NULL) { //该点被访问过，且下一个节点非空 p=p->nextarc; w=p->adjvex; } if(visited[w]) {//如果相邻接点都被访问过 top--; continue; }printf("%d ",w); //输出被访问顶点的编号 Q[++top]=w; visited[w]=1; }else//如果没有相邻节点 { top--; continue; } } return ; } /* 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 */