인접 표 비 재 귀적 깊이 검색 (방향 도 있 음)
#include<stdio.h>
#include<malloc.h>
#include<stack>
#define MAX_VERTEX_NUM 20
using namespace std;
int visited[100];
typedef struct arcnode
{
int adjvex;
struct arcnode *nextarc;
int info;
}*arcnod,arcnode1;
typedef struct vertexnode
{
int data;
arcnode1 *firstarc;
}*vertexnod,vertex;
typedef struct
{
vertex ver[MAX_VERTEX_NUM];
int vexnum,arcnum;
}*adjlist,adjlist1;
int find(adjlist &g,int x)
{
int x1;
for(int i=0;i<g->vexnum;i++)
{
if(g->ver[i].data==x)
{
x1=i;
break;
}
}
return x1;
}
void create(adjlist &g)
{
int i,k=1,x1,x2;
arcnod s1;
printf(" : ");
scanf("%d%d",&g->vexnum,&g->arcnum);
printf(" : ");
for(i=0;i<g->vexnum;i++)
{
scanf("%d",&g->ver[i].data);
g->ver[i].firstarc=NULL;
}
for(i=0;i<g->arcnum;i++)
{
adjlist g1,g2;
g1=g;
g2=g;
printf(" %d , , : ",k++);
scanf("%d%d",&x1,&x2);
int t1=x1,t2=x2;
x1=find(g1,x1);
x2=find(g2,x2);
s1=(arcnod)malloc(sizeof(arcnode1));
s1->adjvex=x2;
s1->nextarc=g->ver[x1].firstarc;
g->ver[x1].firstarc=s1;
}
}
int firstadjvertex(adjlist &g,int k)
{
if(g->ver[k].firstarc!=NULL)
return g->ver[k].firstarc->adjvex;
else
return -1;
}
int nextadjvertex(arcnod &p,int k)
{
if(p->nextarc!=NULL)
return p->nextarc->adjvex;
else
return -1;
}
void depthfirstsearch(adjlist &g,int v0)
{
int k,w;
stack<int>dsta;
stack<int>dstb;
arcnod p;
dstb.push(v0);
while(dstb.empty()!=1)//
{
k=dstb.top();
dstb.pop();
if(visited[k]!=1)
{
printf("%d ",g->ver[k].data);
visited[k]=1;
w=firstadjvertex(g,k);
p=g->ver[k].firstarc;
while(w!=-1)
{
if(visited[w]!=1)
dsta.push(w);
w=nextadjvertex(p,w);
p=p->nextarc;
}
while(dsta.empty()!=1)
{
dstb.push(dsta.top());
dsta.pop();
}
}
}
}
void traversegraph(adjlist &g)
{
for(int i=0;i<g->vexnum;i++)
visited[i]=0;
for(i=0;i<g->vexnum;i++)
{
if(visited[i]==0)
{
depthfirstsearch(g,i);
}
}
}
int main()
{
adjlist g;
g=(adjlist)malloc(sizeof(adjlist1));
create(g);
traversegraph(g);
printf("
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.