C语言实现图的遍历之深度优先搜索实例
DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下：
#include<iostream>
#include<algorithm>
#include<iterator>
usingnamespacestd;
#defineMAX_VERTEX_NUM10
structNode
{
intadjvex;
structNode*next;
intinfo;
};
typedefstructVNode
{
chardata;
Node*first;
}VNode,AdjList[MAX_VERTEX_NUM];
structGraph
{
AdjListvertices;
intvexnum,arcnum;
};
intvisited[MAX_VERTEX_NUM];
intlocateVex(GraphG,charu)
{
inti;
for(i=0;i<G.vexnum;i++)
{
if(u==G.vertices[i].data)
returni;
}
if(i==G.vexnum)
{
printf("Erroru!\n");
exit(1);
}
return0;
}
voidcreateGraph(Graph&G)
{
inti,j,k,w;
charv1,v2,enter;
Node*p;
printf("inputvexnum&arcnum:\n");
scanf("%d",&G.vexnum);
scanf("%d",&G.arcnum);
printf("inputvertices:\n");
for(i=0;i<G.vexnum;i++)
{
scanf("%c%c",&enter,&G.vertices[i].data);
G.vertices[i].first=NULL;
}
printf("inputArcs(v1,v2,w):\n");
for(k=0;k<G.arcnum;k++)
{
scanf("%c%c",&enter,&v1);
scanf("%c%c",&enter,&v2);
scanf("%d",&w);
i=locateVex(G,v1);
j=locateVex(G,v2);
p=(Node*)malloc(sizeof(Node));
p->adjvex=j;
p->info=w;
p->next=G.vertices[i].first;
G.vertices[i].first=p;
}
}
voidDFS(Graph&G,intv)
{
Node*p;
printf("%c",G.vertices[v].data);
visited[v]=1;
p=G.vertices[v].first;
while(p)
{
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
voidDFSTranverse(Graph&G)
{
for(intv=0;v<G.vexnum;v++)
visited[v]=0;
for(intv=0;v<G.vexnum;v++)
{
if(!visited[v])
DFS(G,v);
}
}
intmain()
{
GraphG;
createGraph(G);
DFSTranverse(G);
}
再换一种方式来写DFS。具体代码如下：
#include<iostream>
#include<string>
usingnamespacestd;
#defineMAXLEN10
structNode
{
intdata;
Node*next;
};
structLink
{
intcount;
stringname;
Node*head;
};
structGraph
{
Linklink[MAXLEN];
intvexnum;
intarcnum;
};
intfindIndex(Graph&G,stringname)
{
intindex=-1;
for(inti=0;i<G.vexnum;i++)
{
if(G.link[i].name==name)
{
index=i;
break;
}
}
if(index==-1)
cout<<"error"<<endl;
returnindex;
}
voidconstructGraph(Graph&G)
{
cout<<"constructgraphyooo"<<endl;
cout<<"entervexnum"<<endl;
cin>>G.vexnum;
stringarray[]={"v1","v2","v3","v4","v5","v6","v7","v8"};
constintsize=sizeofarray/sizeof*array;
for(inti=0;i<G.vexnum;i++)
{
G.link[i].name=array[i];
G.link[i].head=NULL;
}
stringleftName;
stringrightName;
cout<<"enterapair"<<endl;
cin>>leftName>>rightName;
while(leftName!="end"&&rightName!="end")
{
intleftIndex=findIndex(G,leftName);
intrightIndex=findIndex(G,rightName);
Node*node=newNode;
node->data=rightIndex;
node->next=NULL;
node->next=G.link[leftIndex].head;
G.link[leftIndex].head=node;
cout<<"enterapair"<<endl;
cin>>leftName>>rightName;
}
}
boolflag[MAXLEN];
voidDFSTranverse(Graph&G,intnum)
{
cout<<G.link[num].name<<"";
flag[num]=true;
Node*head=G.link[num].head;
while(head!=NULL)
{
intindex=head->data;
if(!flag[index])
DFSTranverse(G,index);
head=head->next;
}
}
voidmain()
{
GraphG;
constructGraph(G);
for(inti=0;i<MAXLEN;i++)
flag[i]=false;
DFSTranverse(G,0);
}
DFS的迭代遍历算法如下：
voidDFS(Graph&G)
{
stack<int>istack;
istack.push(0);
cout<<G.link[0].name<<"";
flag[0]=true;
while(!istack.empty())
{
intindex=istack.top();
Node*head=G.link[index].head;
while(head!=NULL&&flag[head->data]==true)
head=head->next;
if(head!=NULL)
{
index=head->data;
if(!flag[index])
{
cout<<G.link[index].name<<"";
flag[index]=true;
istack.push(index);
}
}
else
istack.pop();
}
}
感性的朋友可以测试运行一下本文实例代码以加深印象，相信本文所述对大家C程序算法设计的有一定的借鉴价值。