#include<stdio.h> |
#include<stdlib.h> |
//表结点 |
typedef struct ArcNode{ |
int adjvex; |
struct ArcNode *nextarc; |
}ArcNode; |
//头结点 |
typedef struct Vnode |
{ |
char data; |
ArcNode *firstarc; |
}Vnode; |
bool visit[20]; |
//图结构 |
typedef struct Graph |
{ |
int point; |
int link; |
Vnode *VeArray; |
int flag; |
}AlGraph; |
//初始化图 |
void InitGraph(AlGraph *p, int ve, int arc) |
{ |
p->point=ve; |
p->link=arc; |
p->flag=0; |
p->VeArray=(Vnode *) malloc ( sizeof (Vnode)*ve); |
} |
//用邻接表存储图 |
void CreateGraph(AlGraph *p) |
{ |
int i,j; |
char index; |
ArcNode *Q,*S; |
printf ( "请依次输入各顶点:\n" ); |
for (i=0;i<p->point;i++) |
{ |
getchar (); |
scanf ( "%c" ,&index); |
p->VeArray[i].data=index; |
p->VeArray[i].firstarc=NULL; |
} |
for (i=0;i<p->point;i++) |
{ |
getchar (); |
S=(ArcNode *) malloc ( sizeof (ArcNode)); |
printf ( "依次输入与顶点 %c 相邻的顶点并以#结束:" ,p->VeArray[i].data); |
scanf ( "%c" ,&index); |
if (index) |
{ |
j=0; |
while (index!=p->VeArray[j].data) |
j++; |
S->adjvex=j; |
p->VeArray[i].firstarc=S; |
Q=S; |
} |
else |
continue ; |
scanf ( "%c" ,&index); |
while (index!= '#' ) |
{ |
S=(ArcNode *) malloc ( sizeof (ArcNode)); |
j=0; |
while (index!=p->VeArray[j].data) |
j++; |
S->adjvex=j; |
Q->nextarc=S; |
Q=S; |
scanf ( "%c" ,&index); |
} |
Q->nextarc=NULL; |
} |
} |
//输出邻接表 |
void showGraph(AlGraph *p) |
{ |
int i; |
ArcNode *temp; |
printf ( "顶点位置\t顶点名称\t邻接顶点的位置\n" ); |
for (i=0;i<p->point;i++) |
{ |
printf ( "%4d\t\t %c ->\t\t" ,i,p->VeArray[i].data); |
temp=p->VeArray[i].firstarc; |
while (temp) |
{ |
printf ( "%d->\t" ,temp->adjvex); |
temp=temp->nextarc; |
} |
printf ( "\n" ); |
} |
} |
void DFS(AlGraph &p, int i) |
{ |
visit[i]= true ; |
printf ( "%c->" ,p.VeArray[i].data); |
ArcNode *nextNode=p.VeArray[i].firstarc; |
while (nextNode) |
{ |
if (!visit[nextNode->adjvex]) |
DFS(p,nextNode->adjvex); |
nextNode=nextNode->nextarc; |
} |
} |
void DFStraverse(AlGraph &p) |
{ |
for ( int i=0;i<p.point;i++) |
visit[i]= false ; |
for ( int i=0;i<p.point;i++) |
{ |
if (!visit[i]) |
DFS(p,i); |
} |
} |
int main () |
{ |
int ve,arc; |
AlGraph p; |
printf ( "请输入无向图的顶点数和边数:\n" ); |
scanf ( "%d%d" ,&ve,&arc); |
InitGraph(&p,ve,arc); |
CreateGraph(&p); |
printf ( "\n无向图的邻接表存储结构如下:\n" ); |
showGraph(&p); |
printf ( "深度优先搜索无向图序列如下:\n" ); |
DFStraverse(p); |
} |