fk.cpp

数据结构的作业 有关dfs算法程序源代码

// fk.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;

struct EdgeNode
{     
	int endvex;                    
    PEdgeNode nextedge;    
};
                                       
typedef struct
{     
	EdgeList edgelist;          
} VexNode;                          

typedef struct
{     
	VexNode vexs[MAXVEX];
    int n;                            
}GraphList;

void insert(GraphList* p,int a,int b)
{
	EdgeList pp;
    PEdgeNode temp;
    temp=(PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex=b;
    temp->nextedge=NULL;
    pp=p->vexs[a].edgelist;
    if(pp==NULL)p->vexs[a].edgelist=temp;
	else
	{
		while(pp->nextedge!=NULL)
			pp=pp->nextedge;
		pp->nextedge=temp;
	}
}

GraphList* makeList()
{
	GraphList* p;
	int i;
	p=(GraphList*)malloc(sizeof(GraphList));
	p->n=8;
	for(i=0;i<p->n;i++)
		p->vexs[i].edgelist=NULL;
	insert(p,0,1);
    insert(p,0,2);
	insert(p,1,3);
	insert(p,1,4);
    insert(p,2,5);
	insert(p,2,6);
    insert(p,3,7);
	insert(p,4,7);
    insert(p,5,6);
	return p;
}

#define  null  -1
int  firstVertex(GraphList* pgraph)
{    
	if(pgraph->n==0)
		return null;
	else return 0;
}

int  nextVertex(GraphList* pgraph,int n)
{    
	if(n==pgraph->n-1)
		return null;
	else return n+1;
}

int  firstAdjacent(GraphList* pgraph, int i)
{     
	if(pgraph->vexs[i].edgelist!=NULL)
		return pgraph->vexs[i].edgelist->endvex;
	else return null; 
} 
 
int  nextAdjacent(GraphList* pgraph, int i, int j)
{ 
	PEdgeNode p;
	for(p=pgraph->vexs[i].edgelist; p!=NULL; p=p->nextedge)
		if(p->endvex==j) 
		{
			if(p->nextedge!=NULL)
				return p->nextedge->endvex;
			else 
				return null;
		}
		return null; 
}



typedef int Vertex;
#define TRUE 1
#define FALSE 0

typedef struct
{
	Vertex v;
	Vertex k;
}DataType;

#define MAXNUM 20     
struct  SeqStack                
{     
	DataType  s[MAXNUM];
	int  t;                  
};

typedef  struct SeqStack  *PSeqStack;     
PSeqStack  createEmptyStack_seq( void )
{  
	PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
	if (pastack==NULL)
		printf("Out of space!! ");
	else
		pastack->t=-1;
	return  (pastack);
}

int  isEmptyStack_seq( PSeqStack pastack )
{
	return ( pastack->t == -1 );
}

void  push_seq( PSeqStack pastack, DataType x )
{  
	if( pastack->t >= MAXNUM - 1  )
		printf( "Overflow! " );
	else
	{  
		pastack->t = pastack->t + 1;
		pastack->s[pastack->t] = x;
	}
}

void  pop_seq( PSeqStack pastack )
{    
	if (pastack->t == -1 )
		printf( "Underflow!" );
	else
		pastack->t = pastack->t - 1;
}

DataType  top_seq( PSeqStack pastack )
{
	return (pastack->s[pastack->t]);
}

int visited[MAXVEX];
void dfs ( GraphList* g , Vertex v );
void dft ( GraphList* g )
{
	Vertex v ;
	for ( v =firstVertex ( g ) ; v != null ; v = nextVertex ( g , v ) )
		if ( visited[v] == FALSE ) dfs ( g , v ) ;
}

void dfs ( GraphList* g , Vertex v )
{
	DataType element;
	Vertex v1,v2;
	PSeqStack s ;       
	s = createEmptyStack_seq ( ) ;
	element.v=v;
	element.k=firstAdjacent(g,v);
	push_seq ( s ,element) ;
	printf("%d ",v);
	visited[v] = TRUE ;
	while ( !isEmptyStack_seq(s) ) 
	{
		element =top_seq ( s ) ;
		pop_seq ( s );
		v1 =element.v;
		v2 =element.k;
		while (v2!=null ) 
		{
			if ( visited[v2] == FALSE ) 
			{
				element.v=v1;
				element.k=v2;
				push_seq ( s,  element);
				visited[v2] = TRUE ;
				printf("%d ",v2);
				v1=v2;
				v2=firstAdjacent(g,v1);
			}
			else v2= nextAdjacent(g , v1 , v2 ) ;
		}
	}
}

int main()
{
	GraphList* p=makeList();
	dft(p);
	return 0;
}