#include <stdio.h>
#include<malloc.h>
#define maxvertexnum 100
#define queuesize 100
#define null 0
typedef struct{
int front,rear,count,data[queuesize];
}cirqueue;
typedef int vertextype;
typedef struct node{
int adjvex;
struct node *next;
}edgenode;
typedef struct vnode{
vertextype vertex;
edgenode *firstedge;
}vertexnode;
typedef vertexnode adjlist[maxvertexnum];
typedef struct{
adjlist adjlist;
int n;
int e;
}algraph;
typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];
void createalgraph(algraph *g)
{
int i,j,k;
int flag;
edgenode *s;
printf("\ncreat:\n");
printf("digraph--0\n");
printf("undigraph--1\n");
scanf("%d",&flag);
printf("input n,e\n");
scanf("%d%d",&g->n,&g->e);
printf("input nodes:\n");
for(i=0;i<g->n;i++){
scanf("%d",&(g->adjlist[i].vertex));
g->adjlist[i].firstedge=null;
}
for(k=0;k<g->e;k++){
printf("input i,j(0~n-1):\n");
scanf("%d%d",&i,&j);
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j;
s->next=g->adjlist[i].firstedge;
g->adjlist[i].firstedge=s;
if (flag){
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i;
s->next=g->adjlist[j].firstedge;
g->adjlist[j].firstedge=s;
}
}
}
void dfs(algraph *g,int i)
{
edgenode *p;
printf("visit vertex:%d",g->adjlist[i].vertex);
visited[i]=TRUE;
p=g->adjlist[i].firstedge;
while(p){
if (!visited[p->adjvex])
dfs(g,p->adjvex);
p=p->next;
}
}
void dfstraverse(algraph *g)
{
int i;
for(i=0;i<g->n;i++)
visited[i]=FALSE;
for(i=0;i<g->n;i++)
if(!visited[i])
dfs(g,i);
printf("\n");
}//end of dfstraverse
void bfs(algraph *g,int k)
{
int i,j;
cirqueue *q;
edgenode *p;
q=(cirqueue *)malloc(sizeof(cirqueue));
q->rear=q->front=q->count=0;
printf("visit vertex:%d",g->adjlist[k].vertex);
visited[k]=TRUE;
q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;
while(q->count){
i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;
p=g->adjlist[i].firstedge;
while (p){
if(!visited[p->adjvex]){
printf("visit vertex:%d",g->adjlist[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
q->data[q->rear]=p->adjvex;q->rear=(q->rear+1)%queuesize;q->count++;
}//end of if
p=p->next;
}
}
}
void bfstraverse(algraph *g)
{
int i;
for(i=0;i<g->n;i++)
visited[i]=FALSE;
for(i=0;i<g->n;i++)
if(!visited[i])
bfs(g,i);
printf("\n");
}
void main()
{
algraph *g;
g=(algraph*)malloc(sizeof(algraph));
createalgraph(g);
printf("the dfs is:");
dfstraverse(g);
printf("the bfs is:");
bfstraverse(g);
}
- 1
- 2
- 3
- 4
- 5
- 6
前往页