데이터 구조 (그림): 그림 인접 표 저장, DFS, BFS, 연결 분량 없 음

신학 기 첫 번 째 데이터 구조 작업 은 그림 이 없 는 인접 행렬 과 인접 표 저장 을 배 워 인접 표 로 저 장 된 DFS 와 BFS 를 실현 했다.
#include 
#include 

//       
typedef struct Arcnode{
	int flag;
	struct Arcnode *next;
}node,*Arclist; 

typedef struct Vnode{
	char data;
	Arclist firstarc;
}Vnode,Adjlist[100];

typedef struct Gra{
	Adjlist vertices;
	int vexnum;
	int arcnum;
}*Graph,gnode; 

//            
int locate(Graph &G,char ch){
	int i;int t;
	for(i=0;ivexnum;i++){
		if(ch==G->vertices[i].data){
			t=i;
			break;
		}
	}
	if(i>=G->vexnum)
		return -1;
	else
		return t;
}

//      
void createGraph(Graph &G){
	int i;
	char head,tail;
	
	printf("input the vexnum and the arcnum:
"); scanf("%d%d",&G->vexnum,&G->arcnum); for(i=0;ivexnum;i++){ G->vertices[i].firstarc=new node; } getchar(); printf("input the data of the vertices:
"); for(i=0;ivexnum;i++){ scanf("%c",&G->vertices[i].data); G->vertices[i].firstarc->next=NULL; } getchar(); printf("input the arc:
"); scanf("%c%c",&head,&tail); getchar(); while(head!=' '){ int t1,t2; t1=locate(G,head); t2=locate(G,tail); // printf("%d%d
",t1,t2); Arclist L; L=(Arclist)malloc(sizeof(node)); L->flag=t2;L->next=NULL; Arclist T=G->vertices[t1].firstarc; while(T->next!=NULL) { T=T->next; } T->next=L; T=L; L=(Arclist)malloc(sizeof(node)); L->flag=t1;L->next=NULL; T=G->vertices[t2].firstarc; while(T->next!=NULL) { T=T->next; } T->next=L; T=L; printf("input the arc:
"); scanf("%c%c",&head,&tail); getchar(); } } //dfs int visited[10]={0}; void dfs(Graph &G,int v){ printf("%c ",G->vertices[v].data); visited[v]=1; Arclist T; T=G->vertices[v].firstarc->next; while(T){ int w; w=T->flag; if(visited[w]==0) dfs(G,w); T=T->next; } } void df_traver(Graph &G){ for(int i=0;ivexnum;i++){ visited[i]=0; } for(int i=0;ivexnum;i++){ if(visited[i]==0){ dfs(G,i); } } } //bfs typedef struct qnode{ int data[10]; int first,rear; int queuesize; }Queue; int initqueue(Queue *Q){ Q->first=Q->rear=0; Q->queuesize=10; return 1; } int enqueue(Queue *Q,int v){ Q->data[Q->rear%Q->queuesize]=v; Q->rear=(Q->rear+1)%Q->queuesize; return 1; } int dequeue(Queue *Q){ int t; t=Q->data[Q->first]; Q->first=(Q->first+1)%Q->queuesize; return t; } void bfs(Graph &G,int v){ for(int i=0;ivexnum;i++) visited[i]=0; Queue Q; initqueue(&Q); printf("%c ",G->vertices[v].data); visited[v]=1; enqueue(&Q,v); while (Q.first!=Q.rear) { int t=dequeue(&Q); Arclist p; p=G->vertices[t].firstarc->next; while(p){ int w; w=p->flag; if(visited[w]==0){ printf("%c ",G->vertices[w].data); visited[w]=1; enqueue(&Q,w); } p=p->next; } } } void bf_traver(Graph &G){ for(int i=0;ivexnum;i++){ visited[i]=0; } for(int i=0;ivexnum;i++){ if(visited[i]==0){ bfs(G,i); } } }

 
무방 향 비 연통 도의 연통 분량:
void df_s(Graph &G,int v){
	visited[v]=1;
	Arclist T;
	T=G->vertices[v].firstarc->next;
	while(T){
		int w;
		w=T->flag;
		if(visited[w]==0)
			df_s(G,w);
		T=T->next;
	}
}

void splited(Graph &G,int v){
	int flag=0;
	for(int i=0;ivexnum;i++)
		visited[i]=0;
	for(int i=0;ivexnum;i++){
		if(visited[i]==0){
			df_s(G,i);
			flag++;	
		}
	}
	printf("%d",flag);
	
}

좋은 웹페이지 즐겨찾기