인접 표 비 재 귀적 깊이 검색 (방향 도 있 음)

2489 단어
이 코드 는 데이터 구조의 원시 템 플 릿 으로 처음 접 하거나 연구 할 때 참고 할 수 있 으 며 문 제 를 푸 는 데 적합 하지 않다.
#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; }

좋은 웹페이지 즐겨찾기