首页 > 代码库 > 图的邻接表法深度优先搜索

图的邻接表法深度优先搜索

2024-08-05 04:16:48   227人阅读

# include <stdio.h>
# include <stdlib.h>
# define True 1
# define False 0
# define Error -1
# define OK 1
# define MAX_VERTEX_NUM 20
int visited[MAX_VERTEX_NUM];                       //定义标志数组
typedef char VertexData;


typedef enum{DG,DN,UDG,UDN} GraphKind;


typedef struct ArcNode{         //弧节点结构
int adjvex;
struct ArcNode *nextarc;
// OtherInfo info;
}ArcNode;


typedef struct VertexNode{       //表头节点结构
VertexData data;
ArcNode *firstarc;
}VertexNode;


typedef struct {
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum;
GraphKind kind;
}AdjList;


int LocateVertex(AdjList *g, VertexData v)         //求顶点位置函数
{
int j = Error,k;
for (k = 0; k < g->vexnum ; k++)
if (g->vertex[k].data  == v)
{
j = k;break;
}
return j;
}


void Crtadjlist(AdjList *g)            //创建邻接链表
{
int n,e,i,j,k;
char vt,vh;
ArcNode *p;
printf("请输入图的顶点个数和弧的个数\n");
scanf("%d%d", &n, &e);
g->vexnum  = n;
g->arcnum  = e;
printf("请输入顶点信息\n");
getchar();
for (i = 0; i < n; i++)
{
scanf("%c", &(g->vertex[i].data));
g->vertex[i].firstarc = NULL;
}
printf("请输入弧的两个顶点\n");
for (k = 0; k < e; k++)
{
getchar();
scanf("%c%c",&vt,&vh);
i = LocateVertex(g,vt);
j = LocateVertex(g,vh);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = g->vertex[i].firstarc;
g->vertex[i].firstarc = p;
}
}


void DepthFirstSearch(AdjList *g, int v0)  //深度优先搜索
{
ArcNode *p;
printf("%c ", g->vertex[v0].data );
visited[v0] = True;
p = g->vertex[v0].firstarc;
while (p != NULL)
{
if (!visited[p->adjvex])
DepthFirstSearch(g, p->adjvex);
p = p->nextarc;


}
}
TraverseGraph(AdjList *g)      //深搜
{
int vi;
for (vi = 0; vi < g->vexnum ; vi++)
visited[vi] = False;               //初始化标志数组
for (vi = 0; vi < g->vexnum; vi++)
if (!visited[vi])
DepthFirstSearch(g,vi);
}
int main(void)
{
AdjList g;
Crtadjlist (&g);
TraverseGraph(&g);
printf("\n");
return 0;
}

图的邻接表法深度优先搜索


联系
我们