必威体育Betway必威体育官网
当前位置:首页 > IT技术

图的遍历之DSF深度优先算法6.2.1(网络整理)

时间:2019-07-02 05:42:15来源:IT技术作者:seo实验室小编阅读:57次「手机版」
 

dsf

图的遍历之深度优先算法代码描述(和树的前序遍历相似,实际上树可以看成特殊的图:N个顶点有N-1条边,不曾在回路!即树是图连通中最少边的情况)

图片来自网络

如上图:

深度优先遍历:

先选取一个顶点访问它,然后深度优先遍历它的每个未访问的邻接点

#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
#define MaxVertexNum 100    /* 最大顶点数设为100 */  
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */  
typedef int WeightType;        /* 边的权值设为整型 */  
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */  
  
bool Visited[MaxVertexNum];


/* 边的定义 */  
typedef struct ENode *PtrToENode;  
struct ENode{  
    Vertex V1, V2;      /* 有向边<V1, V2> */  
    WeightType Weight;  /* 权重 */  
};  
typedef PtrToENode Edge;  
   
/* 邻接点的定义 */  
typedef struct AdjVNode *PtrToAdjVNode;   
struct AdjVNode{  
    Vertex AdjV;        /* 邻接点下标 */  
    WeightType Weight;  /* 边权重 */  
    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */  
};  
   
/* 顶点表头结点的定义 */  
typedef struct Vnode{  
    PtrToAdjVNode FirstEdge;/* 边表头指针 */  
    DataType Data;            /* 存顶点的数据 */  
    /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */  
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */  
   
/* 图结点的定义 */  
typedef struct GNode *PtrToGNode;  
struct GNode{    
    int Nv;     /* 顶点数 */  
    int Ne;     /* 边数   */  
    AdjList G;  /* 邻接表 */  
};  
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */  

LGraph CreateGraph( int VertexNum )  
{ Vertex V;
/* 初始化一个有VertexNum个顶点但没有边的图 */  
LGraph Graph=(LGraph)malloc(sizeof(struct GNode));
Graph->Nv=VertexNum;
Graph->Ne=0;
 /* 初始化邻接表头指针 */  
    /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */  
       for (V=0; V<Graph->Nv; V++)  
        Graph->G[V].FirstEdge = NULL;  
               
    return Graph;   
} 

void InsertEdge( LGraph Graph, Edge E )  {

PtrToAdjVNode NewNode;  
       
    /* 插入边 <V1, V2> */  
    /* 为V2建立新的邻接点 */  
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));  
    NewNode->AdjV = E->V2;  
    NewNode->Weight = E->Weight;  
    /* 将V2插入V1的表头 */  
    NewNode->Next = Graph->G[E->V1].FirstEdge;  
    Graph->G[E->V1].FirstEdge = NewNode;  
           
    /* 若是无向图,还要插入边 <V2, V1> */  
    /* 为V1建立新的邻接点 */  
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));  
    NewNode->AdjV = E->V1;  
    NewNode->Weight = E->Weight;  
    /* 将V1插入V2的表头 */  
    NewNode->Next = Graph->G[E->V2].FirstEdge;  
    Graph->G[E->V2].FirstEdge = NewNode;  

}


    LGraph buildGraph()  
    {  
        LGraph 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 %d", &E->V1, &E->V2, &E->Weight);   
                /* 注意:如果权重不是整型,Weight的读入格式要改 */  
                InsertEdge( Graph, E );  
            }  
          free(E);
        }   
       
        /* 如果顶点有数据的话,读入数据 */  
        for (V=0; V<Graph->Nv; V++)   
            scanf(" %c", &(Graph->G[V].Data));  
       
        return Graph;  
    }  

        /* 邻接表存储的图 - DFS */
     
    void Visit( Vertex V )
    {
        printf("正在访问顶点%d\n", V);
    }
     
    /* Visited[]为全局变量,已经初始化为false */
    void DFS( LGraph Graph, Vertex V, void (*PVisit)(Vertex) )
    {   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
        PtrToAdjVNode W;
         
        (*PVisit)( V ); /* 访问第V个顶点 */
        Visited[V] = true; /* 标记V已访问 */
     
        for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
                DFS( Graph, W->AdjV, PVisit );    /* 则递归访问之 */
    }



    int main(){
     for(int i=0;i<MaxVertexNum;i++)
      Visited[i]=false;//初始化为false
      LGraph Graph=BuildGraph();
      DFS(Graph,0,Visit);

    return 0;
    }
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
#define MaxVertexNum 100    /* 最大顶点数设为100 */  
#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/  
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */  
typedef int WeightType;        /* 边的权值设为整型 */  
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */  
bool Visited[MaxVertexNum];  
/* 边的定义 */  
typedef struct ENode *PtrToENode;  
struct ENode{  
    Vertex V1, V2;      /* 有向边<V1, V2> */  
    WeightType Weight;  /* 权重 */  
};  
typedef PtrToENode Edge;  
          
/* 图结点的定义 */  
typedef struct GNode *PtrToGNode;  
struct GNode{  
    int Nv;  /* 顶点数 */  
    int Ne;  /* 边数   */  
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */  
    DataType Data[MaxVertexNum];      /* 存顶点的数据 */  
    /* 注意:很多情况下,顶点无数据,此时Data[]可以不用出现 */  
};  
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */  

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++) 
        if(V==W) 
        	Graph->G[V][W]=0;
        else  
            Graph->G[V][W] = INFINITY;  
               
    return Graph;   
}  

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

    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 %d", &E->V1, &E->V2, &E->Weight);   
                /* 注意:如果权重不是整型,Weight的读入格式要改 */  
                InsertEdge( Graph, E );  
            }  
            free(E);
        }   
       
        /* 如果顶点有数据的话,读入数据 */  
        for (V=0; V<Graph->Nv; V++)   
            scanf(" %c", &(Graph->Data[V]));  
       
        return Graph;  
    }  


    void Visit( Vertex V )
    {
        printf("正在访问顶点%d\n", V);
    }



     /* Visited[]为全局变量,已经初始化为false */
    void DFS( MGraph Graph, Vertex V, void (*PVisit)(Vertex) ){
    /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    	(*PVisit)( V ); /* 访问第V个顶点 */
        Visited[V] = true; /* 标记V已访问 */
        for(Vertex W=0;W<Graph->Nv;W++)              
        	if(!Visited[W]&&Graph->G[V][W]!=INFINITY&&V!=W) /* 对V的每个未被访问de邻接点*/
        	DFS(Graph,W,PVisit);

    }

    int main(){
     for(int i=0;i<MaxVertexNum;i++)
      Visited[i]=false;//初始化为false
      MGraph Graph=BuildGraph();
      DFS(Graph,0,Visit);

    return 0;
    }
用栈模拟

相关阅读

adsf

public SystemSensorManager(Context context, Looper mainLooper) { mMainLooper = mainLooper; mTargetSdkLevel = context.get

分享到:

栏目导航

推荐阅读

热门阅读