如题，以邻接表存储图，并对图进行深度优先遍历

Question

编写一个程序以邻接表存储图，并对图进行深度优先遍历，并画出流程图

Answer 1

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXVEX 100
typedef char VertexType[3];/*定义VertexType为char数组类型*/
typedef struct vertex
{int adjvex; /*顶点编号*/VertexType data; /*顶点的信息*/ } VType;/*顶点类型*/
typedef struct graph
{int n,e;/*n为实际顶点数,e为实际边数*/
VType vexs[MAXVEX];/*顶点集合*/
int edges[MAXVEX][MAXVEX];/*边的集合*/
} AdjMatix;/*图的邻接矩阵类型*/
typedef struct edgenode
{int adjvex; /*邻接点序号*/ int value;/*边的权值*/struct edgenode *next;/*下一顶点*/
} ArcNode;/*每个顶点建立的单链表中结点的类型*/
typedef struct vexnode
{VertexType data; /*结点信息*/ArcNode *firstarc;/*指向第一条边结点*/
} VHeadNode;/*单链表的头结点类型*/
typedef struct
{int n,e;/*n为实际顶点数,e为实际边数*/
VHeadNode adjlist[MAXVEX];/*单链表头结点数组*/
} AdjList; /*图的邻接表类型*/
void DispAdjList(AdjList *G)
{int i;
ArcNode *p;
printf("图的邻接表表示如下:\n");
for (i=0;i<G->n;i++)
{printf(" [%d,%3s]=>",i,G->adjlist[i].data);
p=G->adjlist[i].firstarc;
while (p!=NULL)
{printf("(%d,%d)->",p->adjvex,p->value);p=p->next;}printf("∧\n");
}
}
void MatToList(AdjMatix g,AdjList *&G) /*将邻接矩阵g转换成邻接表G*/
{int i,j;ArcNode *p;
G=(AdjList *)malloc(sizeof(AdjList));
for (i=0;i<g.n;i++)/*给邻接表中所有头结点的指针域置初值*/
{G->adjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);}
for (i=0;i<g.n;i++)/*检查邻接矩阵中每个元素*/
for (j=g.n-1;j>=0;j--)
if (g.edges[i][j]!=0)/*邻接矩阵的当前元素不为0*/
{p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
p->value=g.edges[i][j];p->adjvex=j;
p->next=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p;}
G->n=g.n;G->e=g.e;
}
int visited[MAXVEX];
void DFS(AdjList *g,int vi)/*对邻接表G从顶点vi开始进行深度优先遍历*/
{ArcNode *p;printf("%d ",vi);/*访问vi顶点*/ visited[vi]=1;/*置已访问标识*/
p=g->adjlist[vi].firstarc;/*找vi的第一个邻接点*/
while (p!=NULL)/*找vi的所有邻接点*/
{if (visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next; }
}
void main()
{int i,j,k,a[9][9];AdjMatix g;AdjList *G;
char *vname[MAXVEX]={"a","b","c","d","e","f","g","h","i"};
printf("输入定点数(<10)，边数");
scanf("%d,%d",&i,&k);
g.n=i;g.e=2*k;
for (i=0;i<g.n;i++)strcpy(g.vexs[i].data,vname[i]);
for (i=0;i<g.n;i++)
for (j=0;j<g.e;j++)g.edges[i][j]=0; /*a[i][j];*/
for(k=0;k<g.e/2;k++)
{printf("请输入第%d条边的起点和终点序号(逗点分隔)",k);scanf("%d,%d",&i,&j);
g.edges[i][j]=g.edges[j][i]=1;}
MatToList(g,G);/*生成邻接表*/ DispAdjList(G);/*输出邻接表*/
for (i=0;i<g.n;i++)visited[i]=0; /*顶点标识置初值*/
printf("从顶点0的深度优先遍历序列:\n");printf(" 递归算法:");DFS(G,0);printf("\n");
}本回答被提问者和网友采纳