데이터 구조 (그림): 그림 인접 표 저장, DFS, BFS, 연결 분량 없 음
3805 단어 데이터 구조 작업
#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);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 과정 설계 작업 하프만 인코딩/디코더텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.