#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);
}