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程序算法设计的有一定的借鉴价值。