以下图为例进行深搜:
我们以无向图为例
由于深度搜索的结果不唯一,我们以 1 为初始搜索顶点,得出的结果是
1 2 4 5 6 7 3 8
程序如下:
#include<stdio.h> #include<stdlib.h> #include<string.h> #define number 20 typedef struct node { int info; //图的节点存放的信息,可随时变动 }GraphNode; typedef struct { GraphNode matrix[number+1][number+1]; //构造邻接矩阵 int vexs[number+1]; //顶点向量 int vertex,edge; //顶点个数、弧个数 }Graph; int visited[number+1]; //创建图 void CreatGraph(Graph *G) { int i,k; int x,y,data; int vertex,edge; printf("输入图的顶点个数和边的个数.\n"); scanf("%d%d",&vertex,&edge); G->vertex = vertex;G->edge = edge; printf("输入图的每个顶点.\n"); for(i=1;i<=vertex;i++) scanf("%d",&G->vexs[i]); for(i=1;i<=vertex;i++) for(k=1;k<=vertex;k++) G->matrix[i][k].info = 0; printf("请输入 %d 条边的横坐标、纵坐标、数值.\n",edge); for(i=1;i<=edge;i++) { scanf("%d%d%d",&x,&y,&data); G->matrix[x][y].info=data; G->matrix[y][x].info=data; } } //找出给定顶点的位置 int LocateVex(Graph *G,int V) { int i; for(i=1;i<=G->vertex;i++) if(G->vexs[i] == V) return i; return -1; //失败返回-1 } //打印图 void DisplayGraph(Graph *G) { int i,k; for(i=1;i<=G->vertex;i++) { for(k=1;k<=G->vertex;k++) printf("%-4d ",G->matrix[i][k].info); printf("\n"); } printf("\n"); } void RecoverGraph(Graph *G) { int i,k; for(i=1;i<=G->vertex;i++) for(k=1;k<=G->vertex;k++) G->matrix[i][k].info=0; memset(G->vexs,0,sizeof(G->vexs)); G->vertex = G->edge = 0; } //找出指定顶点在图中的第一个邻接点 int FirstAdjVex(Graph *G,int V) { int temp,i; if((temp = LocateVex(G,V))==-1) return -1; //失败返回-1 else { for(i=1;i<=G->vertex;i++) if(G->matrix[temp][i].info != 0) return i; } return -1; } int NextAdjVertex(Graph *G,int v,int w) { int temp,i; if((temp=LocateVex(G,v)) == -1)return -1; for(i=w+1;i<=G->vertex;i++) if(G->matrix[temp][i].info)return i; return -1; } void DFS(Graph *G,int v) { int w; visited[v]=1;printf("%d ",G->vexs[v]); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVertex(G,v,w)) if(!visited[w])DFS(G,w); } void DFSTraverse(Graph *G) { int i; for(i=1;i<=G->vertex;i++) visited[i]=0; for(i=1;i<=G->vertex;i++) if(!visited[i])DFS(G,i); } int main() { Graph G; CreatGraph(&G); DFSTraverse(&G); printf("\n"); RecoverGraph(&G); return 0; }
测试结果如下: