图的存储结构及遍历操作

朱雀 2023-06-11 03:24 14阅读 0赞

**图的顺序存储结构–邻接矩阵**

*  **图的邻接矩阵的结构定义**

#define MaxVertexNum 100;
    typedef char VertexType;//定义图顶点的数据类型
    typedef int EdgeType;//定义边权值的数据类型
    typedef struct{
        
    	VertexType vex[MaxVertexNum];//顶点表
    	EdgeType edge[MaxVertexType][MaxVertexType];
    }Mgraph;

**图的链式存储结构–邻接表**

*  **图的邻接表的结构定义**

#define MaxVertexType 100;
    typedef char VertexType;
    //边表的定义
    typedef struct ArcNode{
        
    	int adjvex;
    	struct ArcNode* next;
    }ArcNode;
    //顶点表定义
    typedef struct VNode{
        
    	VertexType data;
    	ArcNode *first;
    }VNode,Adjlist[MaxVertexType];
    //邻接表
    typedef struct{
        
    	Adjlist adjlist[MaxVertexType];
    	int vexnum,arcnum;
    }

**图的基本操作**

*  广度优先遍历-BFS  
    从任意顶点出发，然后访问与其相邻接的所有顶点，然后继续对其邻接顶点进行访问

void BFSTraverse(AlGraph G){
        
    	//初始化visited数组
    	for(int i=0;i<G.vexnum;i++){
        
    		visited[i]=false;
    	}
    	InitQueue(Q);
    	for(int i=0;i<G.vexnum;i++){
        
    		if(visited[i]==false){
        
    			BFS(G,i)
    		}
    	}
    }
    //BFS算法
    void BFS(AlGraph G,int v){
        
    	visit[v];
    	visited[v]==true;
    	EnQueue(Q,v);
    	ArcNode *p;
    	while(QueueEmpty(Q)!=NULL){
        
    		DeQueue(Q,v);
    		p=G.adjlist[v].first;
    		while(p!=NULL){
        
    			if(visited[p->adjvex]==false){
        
    				visit[p->adjvex];
    				visited[p->adjvex]=false;
    				EnQueue(Q,p->adjvex);
    			}
    			p=p->next;
    		}
    	}
    }

*  深度优先遍历-DFS  
    由某一个结点开始，一直向下遍历，直到不能继续深入时，回溯，找到最近的被访问结点–递归

void DFSTraverse(AlGrapg G){
        
    	for(int i=0;i<G.vexnum;i++){
        
    		visited[i]=false;
    	}
    	for(int i=0;i<G.vexnum;i++){
        
    		if(visited[i]==false)
    		DFS(G,i);
    	}
    }
    //DFS算法
    void DFS(AlGraph G,int v){
        
    	visit[v];
    	visited[v]=true;
    	ArcNode *p;
    	p=G.adjlist[v].first;
    	while(p!=NULL){
        
    		if(visited[p->adjvex]==false){
        
    			DFS(G,p->adjvex);
    		}
    		p=p->next;
    	}
    }