实验五 - 图的邻接矩阵表示法 + DFS

/* 图的邻接矩阵表示法 + DFS*/
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 10    /* 最大顶点数设为100 */
#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;      /* 有向边<V1, V2> */
};
typedef PtrToENode Edge;

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    int G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    DataType Data[MaxVertexNum];      /* 顶点表 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
int visited[MaxVertexNum];

MGraph CreateGraph( int VertexNum );
void InsertEdge( MGraph Graph, Edge E );
MGraph BuildGraph();
void InitVisited();
void DFS(MGraph G, int v);
void Debug(MGraph G);
int main(){
    MGraph Graph;
    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph = BuildGraph();
    InitVisited(Graph);
    DFS(Graph, 0);
    //Debug(Graph);

    return 0;
}


MGraph CreateGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图 */
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    /* 初始化邻接矩阵 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for (V=0; V<Graph->Nv; V++)
        for (W=0; W<Graph->Nv; W++)
            Graph->G[V][W] = 0;

    return Graph;
}

void InsertEdge( MGraph Graph, Edge E )
{
     /* 插入边 <V1, V2> */
     Graph->G[E->V1][E->V2] = 1;
     /* 若是无向图，还要插入边<V2, V1> */
     Graph->G[E->V2][E->V1] = 1;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    scanf(\"%d\", &Nv);   /* 读入顶点个数 */
    Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */

    scanf(\"%d\", &(Graph->Ne));   /* 读入边数 */
    if ( Graph->Ne != 0 ) { /* 如果有边 */
        E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
        /* 读入边，格式为\"起点 终点\"，插入邻接矩阵 */
        for (i=0; i<Graph->Ne; i++) {
            scanf(\"%d %d\", &E->V1, &E->V2);
            InsertEdge( Graph, E );
        }
    }
    for (V=0; V<Graph->Nv; V++){
        scanf(\" %c\", &(Graph->Data[V]));
    }
    return Graph;
}
void InitVisited(MGraph Graph){
    for(int i = 0; i < MaxVertexNum; i++){
        visited[i] = 0;
    }
}
void DFS(MGraph Graph, int v){
    int w;
    printf(\" %c\\n\", Graph->Data[v]);
    visited[v] = 1;
    for(w = 0; w < MaxVertexNum; w++){
        printf(\"Graph->G[%d][%d] = %d\\n\" , v, w, Graph->G[v][w]);
        if((Graph->G[v][w] != 0) && (!visited[w])){
            DFS(Graph,w);
        }
    }
}
void Debug(MGraph Graph){
    /*for(int i = 0; i < 6; i++){
        printf(\" %d%c\", i,Graph->Data[i]);
    }*/
    printf(\"\\n\");
    for(int i = 0 ; i < 6; i++){
        for(int j = 0; j < 6; j++){
            printf(\" %d\", Graph->G[i][j]);
        }
        printf(\"\\n\");
    }
    /*for(int i = 0; i < MaxVertexNum; i++){
        printf(\" %d\", visited[i]);
    }*/
    printf(\"\\n\");
}
/* 测试
5 6
0 1
1 2
1 4
2 3
2 4
A B C D E

*/