图的创建、深度优先遍历以及判断两点间路径是否存在

最新推荐文章于 2025-03-17 17:58:34 发布

FoggyProgrammer

最新推荐文章于 2025-03-17 17:58:34 发布

阅读量3.6k

点赞数 10

分类专栏：数据结构文章标签：数据结构

本文链接：https://blog.csdn.net/FoggyProgrammer/article/details/103647807

版权

数据结构专栏收录该内容

7 篇文章

订阅专栏

本文详细介绍了图数据结构的两种存储方式：邻接矩阵和邻接表，并通过C语言实现有向图的创建、显示以及深度优先搜索算法，判断两点间路径的存在性，适合数据结构学习者深入理解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接矩阵和邻接表存储结构并输出显示。

数据结构习题集（C语言版）清华大学出版社 P150-5.3

2．试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

数据结构习题集（C语言版）清华大学出版社 P49 7.27

程序代码

第一题程序代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define INFINITY    999    //定义最大值为999，即两个点之间无连接的情况
#define MAX_VERTEX_NUM  20  //最大顶点个数20
#define ERROR  -1
#define OK 1
typedef  enum {DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网 }(枚举类型)
typedef int VRType;//对带权图，则为权值类型。
typedef int Status;
typedef int InfoType;
typedef char VertexType;
typedef struct ArcCell {
      VRType    adj;   //VRType是顶点关系类型。
                                   //对无权图，用1或0表示相邻否；
                                   //对带权图，则为权值类型。
      InfoType  *info;   //该弧相关信息的指针
}ArcCell,AdjMatrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];


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

Status LocateVex(MGraph G,VertexType v)//定位函数，参数为MGraph型变量G与VertexType型变量v，功能是找出顶点在数组G.vexs[i]中的位置
{
    int i;
    //printf("%c ",v);
    for(i=0;i<G.vexnum;i++)//从0开始到G.vexnum结束，若v的值等于G.vexs中第i个元素的值，那么v所处的位置就是G.vexs[i]在数组中所处的位置
    {
        if(v==G.vexs[i])
        {
            return i;
        }
	}
if(i==G.vexnum)//若没有找到符合条件的值，返回错误
	return ERROR;

}

Status  PrintGraph(MGraph G)//输出函数，参数为MGraph型变量G，功能是打印邻接矩阵
{
    int i,j,k;
    for(i=0;i<G.vexnum;i++)
    {
        for(j=0;j<G.vexnum;j++)
        printf("%5d ",G.arcs[i][j].adj);//对带权图，从0开始到G.vexnum结束输出的为则为权值。
        printf("\n");
    }
}

Status  CreateDG(MGraph &G)//采用数组(邻接矩阵)表示法，构造有向网G，参数为MGraph 型变量G的引用。
{
    int i,j,k,IncInfo,w;
    char v1,v2;
    printf("Please input the num of vex and arc,as well as the IncInfo:\n");
    scanf("%d %d",&G.vexnum,&G.arcnum);//输入顶点个数以及边的个数
	//IncInfo为0则各弧不含其它信息
	 printf("Please enter %d vertices:",G.vexnum);
    for(i=0;i<G.vexnum;i++)
        scanf(" %c",&G.vexs[i]); //输入顶点信息，构造顶点向量
    for(i=0;i<G.vexnum;i++)    //初始化邻接矩阵
        for(j=0;j<G.vexnum;j++)
            //G.arcs[i][j]={INFINITY,NULL}; //{adj,info}
            G.arcs[i][j].adj= INFINITY;//初始化，设邻接矩阵中每行每列的初值都为INFINITY（999），表示初始时所有顶点都相互独立没有连接
            //PrintGraph(G);
    for(k=0;k<G.arcnum;k++)//构造邻接矩阵
    {
        printf("Please input the both point of an arc and its weight:\n");
        scanf(" %c %c %d",&v1,&v2,&w); //输入一条边依附的顶点及权值
        i=LocateVex(G,v1); //确定v1在G中位置
        j=LocateVex(G,v2);//确定v2在G中位置
        G.arcs[i][j].adj=w;//弧<v1，v2>的权值
   }
   return OK;
}//


Status  CreateGraph (MGraph &G)//选择图的种类，参数为MGraph 型变量G的引用。
{
      //采用数组(邻接矩阵)表示法，构造图G。
    printf("Please input the TYPE of the graph:\n");
     scanf("%d",&G.kind);
     switch (G.kind)  
     {
           case    DG:return CreateDG(G);  //构造有向图G
           //case    DN:return CreateDN(G);  //构造有向网G
           //case UDG:return CreateUDG(G);//构造无向图G
           //case UDN:return CreateUDN(G);//构造无向网G
           default:      return ERROR;
     }
//利用了枚举类型选择图的种类，{DG,DN,UDG,UDN}分别对应{有向图，有向网，无向图，无向网 }，键盘输入分别为{0，1，2，3}，此处题目要求为有向图，因此输入时应当选择0
}// CreateGraph
//"顶点数目"、
//"弧的数目"、
//"各顶点的信息"
//"各条弧的信息"
/*Status  CreateUDN(MGraph  &G)
{}
Status  CreateDN(MGraph  &G)
{}
Status  CreateUDG(MGraph  &G)
{}*/
//其余（有向网，无向图，无向网）的create函数为空函数

int main()
{
    MGraph Graph;
    CreateGraph(Graph);
    PrintGraph(Graph);
}

第二题程序代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAX_VERTEX_NUM  20
#define ERROR  -1
#define TRUE 1
#define FALSE  -1
#define MAX  1000
typedef  enum {DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网 }
typedef int Status;
typedef char VertexType;
typedef int InfoType;
typedef int VRType;//对带权图，则为权值类型。
bool visited[MAX];  //访问标志数组



 typedef struct ArcNode{表结点
    int    adjvex;  //该弧所指向的顶点的位置
    struct ArcNode   *nextarc ;//指向下一条弧的指针
    InfoType     info;      //该弧相关信息的指针
}ArcNode;
typedef struct  VNode {/头结点
     VertexType     data;  //顶点信息
     ArcNode    *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
       AdjList    vertices;
       int    vexnum,arcnum;   //图的当前顶点数和弧数
       int    kind;                          //图的种类标志
}ALGraph;
Status  PrintGraph(ALGraph &G)
{
    int i,j,k;
    ArcNode *p;

    for(i=0;i<G.vexnum;i++)
    {
        printf("%d  %c->",i,G.vertices[i].data);
        p=G.vertices[i].firstarc;
        while(p!=NULL)
        {
            printf("(%d)%d->",p->info,p->adjvex);
            p=p->nextarc;
        }
        if(p==NULL)
            printf("^");
        printf("\n");
    }
}

int LocateVex(ALGraph &G,VertexType v)
{
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        if(G.vertices[i].data==v)return i;
        }
    //if(i==G.vexnum)
    return -1;//未找到
}
Status  CreateDG(ALGraph &G)//采用数组(邻接矩阵)表示法，构造无向网G。
{
    int i,j,k,IncInfo,w;
    VertexType v1,v2;
    ArcNode *s;
    printf("Please input the num of vex and arc,as well as the IncInfo:\n");
    scanf("%d%d",&G.vexnum,&G.arcnum);//输入顶点个数、边个数以及其他信息
	//IncInfo为0则各弧不含其它信息
	 printf("Please enter %d vertices:\n",G.vexnum);//输入顶点的名称信息
	 getchar();
    for(i=0;i<G.vexnum;i++)//初始化邻接表
    {
        getchar();
        printf("%d:",i);
        scanf("%c",&(G.vertices[i].data)); //构造顶点向量
        G.vertices[i].firstarc=NULL;
    }
    for(i=0;i<G.vexnum;i++)//初始化邻接表
    {
        printf("%c ",(G.vertices[i].data)); //构造顶点向量
        printf("\n");
    }
    //PrintGraph(G);
    for(k=0;k<G.arcnum;k++)
    {
        getchar();
        printf("Please enter an arc(v1-w-v2):\n");
        scanf(" %c%d%c",&v1,&w,&v2);
        //scanf("%c%c",&v1,&v2);
        printf("%c %c\n",v1,v2);
        i=LocateVex(G,v1);//LocateVex(G,v1);
        j=LocateVex(G,v2);//LocateVex(G,v2);
        printf("%d %d\n",i,j);
        if((i==-1)||(j==-1))
        printf("\nThe vertex is ERROR");
        else{
            s=(ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex=j;
            s->nextarc=G.vertices[i].firstarc;
            G.vertices[i].firstarc=s;
            }
        s->info=w;
    }
}
Status  CreateGraph (ALGraph &G)
{
      //采用数组(邻接矩阵)表示法，构造图G。
    printf("Please input the TYPE of the graph:\n");
     scanf("%d",&G.kind);
     switch (G.kind)  {
           case    DG:return CreateDG(G);  //构造有向图G
           //case    DN:return CreateDN(G);  //构造有向网G
           //case UDG:return CreateUDG(G);//构造无向图G
           //case UDN:return CreateUDN(G);//构造无向网G
           default:      return ERROR;
       }
}



int FirstAdjVex(ALGraph &G,int v)
{
    int w;
    if(G.vertices[v].firstarc!=NULL)
    w=G.vertices[v].firstarc->adjvex;
    else w=-1;
    //printf("---%d\n",w);
    return w;
}
int NextAdjVex(ALGraph &G,int v,int w)
{
    ArcNode *p,*q;
    p=G.vertices[v].firstarc;
    while(p!=NULL && p->adjvex!=w) p=p->nextarc;
    if(p->adjvex==w){
        q=p->nextarc;
        if(q!=NULL)
            w=q->adjvex;
        else w=-1;
        //printf("---%d  %d\n",v,w);
        return w;
        }

//    if(p!=NULL)
//        w=p->adjvex;
//    else w=-1;
    return -1;

}

void DFS(ALGraph &G,int v)
{
    int w;
  //从第v个顶点出发递归地深度优先遍历图G。
   visited[v]=true;
   printf("%c   ",G.vertices[v].data);//访问第v个顶点
  for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
      if(!visited[w])
      DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS
} // 算法  7.5

void DFSTraverse(ALGraph &G){
   //对图G作深度优先遍历。
   int v;
   //VisitFunc=Visit; //使用全局变量VisitFunc，使DFS不必设函数指针参数
   for(v=0;v<G.vexnum;++v)
         visited[v]=false; //访问标志数组初始化
   for(v=0;v<G.vexnum;++v)
         if( !visited[v] ) { DFS(G,v);//对尚未访问的顶点调用DFS
   }
  } //算法  7.4
bool path(ALGraph &G,int start,int end)
{
    int w;
  //从第v个顶点出发递归地深度优先遍历图G。
   visited[start]=true;
   printf("%c   ",G.vertices[start].data);//访问第v个顶点
   if(start==end)      return true;
  for(w=FirstAdjVex(G,start);w>=0;w=NextAdjVex(G,start,w))
      if(!visited[w])
        return(path(G,w,end));//对v的尚未访问的邻接顶点w递归调用DFS

}
bool pathExist(ALGraph &G,int start,int end){
   //对图G作深度优先遍历。
   int v;
   //VisitFunc=Visit; //使用全局变量VisitFunc，使DFS不必设函数指针参数
   for(v=0;v<G.vexnum;++v)
         visited[v]=false; //访问标志数组初始化
   bool existp=path(G,start,end);//对尚未访问的顶点调用DFS
   return existp;
  }
  
int main()
{
    int vi,vj;
    ALGraph Graph;
    CreateGraph(Graph);
    PrintGraph(Graph);
    printf("The result of DFS:\n");
    DFSTraverse(Graph);
    printf("\n");
    //printf("%d\n",pathExist(Graph,0,3));
    printf("Please enter 2 vertices(vi,vj):");
    scanf("%d %d",&vi,&vj);
    if(pathExist(Graph,vi,vj)==1)
    printf("Path exists!\n");
    else
    printf("Path DOES NOT exist!\n");
    //pathExist(Graph,0,3);
}