图的邻接矩阵表示及DFS

 首先，图(下面指的是有向网）的表示如下：

#ifndef GUARD_c7_1_h
#define GUARD_c7_1_h
 
#include<limits>
#define INFINITY   INT_MAX
#define MAX_NAME 5 //顶点字符串的最大长度
#define MAX_VERTEX_NUM   20 //最大顶点数
//enum GraphKind{ DG,DN,AG,AN }; //有向图，有向网 无向图
typedef char VertexType[MAX_NAME]; //不能写成typedef char* vertexType，会出现访问内存错误
typedef char InfoType;

typedef struct
{
    int adj; //顶点关系类型 ，对无权图，用1 0表示相邻否，对带权图，则为权值类型
    int *info; //该弧相关信息的指针（可无）
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct MGraph
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;// 邻接矩阵
    int vexnum,arcnum; //图的当前顶点数和弧数
    //GraphKind kind;图种类
};

#endif

  函数文件的头文件如下：

#ifndef GUARD_bo7_1_h
#define GUARD_bo7_1_h


#include"c7-1.h"


int locateVex(MGraph G,VertexType u);
int createDN(MGraph &G);

int firstAdjVex(MGraph G,VertexType v);

int nextAdjVex(MGraph G,VertexType v,VertexType w);


void DFS(MGraph G,int v);

void DFSTraverse(MGraph G,void(*visit)(VertexType));

#endif

#include"bo7-1.h"
#include<stdio.h>
#include<string.h>
/**
初始条件 ：图G存在，u和G中顶点有相同特征
操作结果：若G中存在顶点u，则返回该顶点在图中的位置，否则返回-1
*/

int locateVex(MGraph G,VertexType u)
{
    int i;
    for(i=0;i<G.vexnum;i++)
        if(strcmp(u,G.vexs[i])==0)
            return i;
    return -1;
}



int createDN(MGraph &G)
{
    int i,j,k,w,IncInfo;
    char s[20],*info;
    //VertexType va,vb; //这里有个问题，char *va,vb; vb不是指针类型
    VertexType va; VertexType vb;
    printf("请输入有向网G的顶点数，弧数，弧是否含其他信息（是1，否0）：");
    scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);

    printf("请输入%d个顶点的值:\n",G.vexnum);
    for(i=0;i<G.vexnum;i++) //构造顶点向量
      scanf("%s",G.vexs[i]);
    
    for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
        for(j=0;j<G.vexnum;j++)
        {
            G.arcs[i][j].adj=INFINITY; //网
            G.arcs[i][j].info=NULL;
        }

        printf("请输入%d条弧的弧尾 弧头 权值 （以空格作为间隔） ：\n",G.arcnum);
        for(k=0;k<G.arcnum;k++)
        {
            scanf("%s%s%d%*c",va,vb,&w); //%*c 吃掉回车符
            i=locateVex(G,va);
            j=locateVex(G,vb);
            G.arcs[i][j].adj=w; //有向网
            
        }
     
        return 1;
}



/*
初始条件：图G存在，v是G某个顶点
操作结果：返回v的第一个邻接顶点的序号，若没有，返回-1
*/
int firstAdjVex(MGraph G,VertexType v)
{
    int i,j=0,k;
    k=locateVex(G,v);
    j=INFINITY;
    for(i=0;i<G.vexnum;i++)
        if(G.arcs[k][i].adj!=j)
            return i;
    return -1;
}

/*
初始条件：v是图G的某个顶点，w是v的邻接顶点
操作结果：返回v的（相对于w的）下一个邻接顶点的序号，若w是v的最后一个邻接顶点，返回-1
*/
int nextAdjVex(MGraph G,VertexType v,VertexType w)
{
    int i,j=0,k1,k2;
    k1=locateVex(G,v);
    k2=locateVex(G,w);
    j=INFINITY;
    for(i=k2+1;i<G.vexnum;i++)
        if(G.arcs[k1][i].adj!=j)
            return i;
    return -1;

}

bool visited[MAX_VERTEX_NUM]; 
void (*visitFunc)(VertexType); 

void DFS(MGraph G,int v)
{
    VertexType w1,v1;
    int w;
    visited[v]=true;
    visitFunc(G.vexs[v]);
    strcpy(v1,G.vexs[v]);
    for(w=firstAdjVex(G,v1);w>=0;w=nextAdjVex(G,v1,strcpy(w1,G.vexs[w])))
     if(!visited[w])
         DFS(G,w);
}
void DFSTraverse(MGraph G,void(*visit)(VertexType))
{
    int v;
    visitFunc=visit;
    for(v=0;v<G.vexnum;v++)
        visited[v]=false;
    for(v=0;v<G.vexnum;v++)
        if(!visited[v])
            DFS(G,v);
    printf("\n");
}

 main函数如下：

#include<stdio.h>
#include"c7-1.h"
#include"bo7-1.h"

void visit(VertexType i)
{
    printf("%s  ",i);
}
int main()
{
    MGraph G;
    createDN(G);
    DFSTraverse(G,visit);
}
    

测试如下：