ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 图的深度优先遍历

图的深度优先遍历

原创 Linux操作系统 作者:tyoodz 时间:2012-04-01 11:03:35 0 删除 编辑
#include

#define MAXVEX 100
#define INFINITY 65535
typedef int Boolean;
Boolean visited[MAXVEX];

typedef struct
{
char vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;

void CreateMGraph (MGraph *G)
{
int i, j, k,w;
printf ("êäè붥μãêyÄ¿oí±ßêy£o\n");
scanf ("%d,%d", &G->numVertexes, &G->numEdges);
getchar();
printf ("%d\n", G->numVertexes);
for (i = 0; i < G->numVertexes; i++)
{
scanf ("%c", &G->vexs[i]);
getchar();
   printf ("%d\n", i);
}
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[i][j] = INFINITY;
for (k = 0; k < G->numEdges; k++)
{
printf ("챐\n");
scanf ("%d,%d,%d", &i, &j, &w);
getchar();
G->arc[i][j] = w;  //è¨
G->arc[j][i] = G->arc[i][j];
}
}


void DFS (MGraph G, int i)
{
int j;
visited[i] = 1;
printf ("%d,%c\n", i, G.vexs[i]);
for (j = 0; j < G.numVertexes; j ++)
if (G.arc[i][j] != INFINITY && !visited[j])
DFS (G, j);
}

void DFSTraverse (MGraph G)
{
int i;
for (i = 0; i < G.numVertexes; i++)
visited[i] = 0;
for (i = 0; i < G.numVertexes; i++)
if (!visited[i])
DFS(G, i);
}

int main()
{
int i = 0, j;
MGraph m;
CreateMGraph(&m);

DFSTraverse(m);
return 0;
}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25361369/viewspace-720123/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 二叉树遍历
下一篇: 堆排序
请登录后发表评论 登录
全部评论

注册时间:2011-05-16

  • 博文量
    55
  • 访问量
    72557