★ 第五十九讲 图的遍历 | 【深度优先遍历】 ★

圣狄雅哥

[ 本帖最后由 圣狄雅哥 于 2018-4-21 11:29 编辑 ]\n\n#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX 100
#define MAXVER 100

typedef int Boolean;
Boolean visited[MAX];
typedef struct
{
    char vexs[MAXVER];
    int arc[MAXVER][MAXVER];
    int numVertexes,numEdges;
}MGraph;

void CreateMGraph(MGraph*G)
{
    int i,j,k;
    printf("请输入顶点数和边数:\n");
    scanf("%d %d",&G->numVertexes,&G->numEdges);
    printf("输入各顶点:\n");
    for(i=0;i<G->numVertexes;i++)
    {
        scanf("%c",&G->vexs[i]);
    }
    for(i=0;i<G->numVertexes;i++)
    {
        for(j=0;j<G->numVertexes;j++)
        {
            G->arc[i][j]=0;
        }
    }
    for(k=0;k<G->numEdges;k++)
    {
        printf("请输入边(Vi,Vj)上的下标i、j，并将权标为1表示连通:\n");
        fflush(stdin);
        scanf("%d %d",&i,&j);
        G->arc[i][j]=1;
        G->arc[j][i]=G->arc[i][j];
    }
}
void PrintVexs(MGraph*G)
{
    int i,j;
    printf("当前无向图的邻接矩阵为:\n");
    for(i=0;i<G->numVertexes;i++)
    {
        for(j=0;j<G->numVertexes;j++)
        {
            printf("%2d ",G->arc[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void DFS(MGraph *G,int i)
{
    int j;
    visited[i]=TRUE;
    printf("%c ",G->vexs[i]);
    for(j=0;j<G->numVertexes;j++)
    {
        if(G->arc[i][j]==1&&!visited[j])
        {
            DFS(G,j);
        }
    }
    printf("\n");
}
void DFSTraverse(MGraph* G)
{
    int i;
    for(i=0;i<G->numVertexes;i++)
    {
        visited[i]=FALSE;
    }
    for(i=0;i<G->numVertexes;i++)
    {
        if(!visited[i])
        {
            DFS(G,i);
        }
    }
}

int main()
{
    MGraph *G;
    G=(MGraph*)malloc(sizeof(MGraph));
    CreateMGraph(G);
    PrintVexs(G);
    printf("深度优先遍历结果为:\n");
    DFSTraverse(G);
    printf("\n");
    return 0;
}

小菜鸟516

didi

雪月圣雕

邻接矩阵的代码在第16行有误：vistited[j] = TRUE; 应该改为哦vistied[i] = TRUE