可以用【深度优先遍历法】回到起始点,深度遍历其实是一种递归方法定义的,所以(单次)从哪个顶点开始就会在哪个定点结束,直到遍历结束。以下是我写的一个从文件创建图并深度优先遍历输出的例子,但运行之前你要先在工程里创建一个图的.txt文本文件,这里即“data.txt”(因为不用文件的话每次运行都要从新输入一遍图,好麻烦)
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define max_vertex_num 50
typedef char vertextype[10];
typedef struct arcnode{
int adjvex;
struct arcnode *next;
}arcnode;
typedef struct vexnode{
vertextype data;
arcnode *firstarc;
}vexnode,adjlist[max_vertex_num];
typedef struct{
adjlist vertices;
int vertexnum,edgenum;
}adjlistgraph;
int visited[max_vertex_num];
int locatevertex(adjlistgraph G,vertextype v);//找到顶点名称所对应的序号
void creatgraph(adjlistgraph &G);//创建一个图
void show_vertex(adjlistgraph G);//显示图中所有顶点的信息
void visit(adjlistgraph G);//遍历图
void DFS(adjlistgraph G,int v);//深度优先遍历
int main()
{
adjlistgraph G;
creatgraph(G);
show_vertex(G);//显示图中顶点信息
printf("\n");
printf("\n");
printf("深度优先遍历图得:\n");
visit(G);
return 0;
}
int locatevertex(adjlistgraph G,vertextype v)
{
int i;
for(i=0;i<=G.vertexnum;i++)
if(strcmp(v,G.vertices[i].data)==0)
return i;
return -1;
}
void creatgraph(adjlistgraph &G)
{
FILE *fp;
int i,j;
vertextype va,vb;
fp=fopen("data.txt","r");
fscanf(fp,"%d",&G.vertexnum);//从文件中输入顶点个数
for(i=0;i<G.vertexnum;i++)//从文件中初始化顶点信息
{
fscanf(fp,"%s",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
fscanf(fp,"%d",&G.edgenum);//从文件中输入边数
for(j=0;j<G.edgenum;j++)//从文件中初始化边
{
fscanf(fp,"%s%s",&va,&vb);
int n=locatevertex(G,va);
int m=locatevertex(G,vb);
arcnode *p=(arcnode*)malloc(sizeof(arcnode));//n--->m
p->adjvex=m;
p->next=G.vertices[n].firstarc;
G.vertices[n].firstarc=p;
arcnode *q=(arcnode*)malloc(sizeof(arcnode));//m--->n
q->adjvex=n;
q->next=G.vertices[m].firstarc;
G.vertices[m].firstarc=q;
}
fclose(fp);
}
void show_vertex(adjlistgraph G)
{
int k;
printf("图中的顶点为:\n");
for(k=0;k<G.vertexnum;k++)
{
printf("%-15s",G.vertices[k].data);
if((k+1)%5==0)
printf("\n");
}
}
void visit(adjlistgraph G)
{
for(int i=0;i<G.vertexnum;i++)
visited[i]=0;
for(int v=0;v<G.vertexnum;v++)
if(visited[v]==0)
{
DFS(G,v);
}
printf("\n");
}
void DFS(adjlistgraph G,int v)
{
visited[v]=1;
printf("%s->",G.vertices[v].data);
for(arcnode *p=G.vertices[v].firstarc;p;p=p->next)
if(visited[p->adjvex]==0)
DFS(G,p->adjvex);
}
随便敲几个点几条边进去,就可以运行了:
例如在data.txt中敲入:
4
北京
上海
杭州
昆明
5
北京 上海
上海 杭州
杭州 昆明
北京 昆明
上海 昆明
运行后结果为: