图的基本操作

雨点打透心脏的1/2处 2023-06-19 05:25 2阅读 0赞

*  **图的邻接矩阵存储**

#define MaxVertexNum 100;//顶点数目的最大值
    typedef char VettexType;//顶点的数据类型
    typedef int EdgeType;//权值的数据类型（表示边）
    typedef struct{
        
    	VextexType vex[MaxVertexNum];顶点表
    	EdgeType edge[MaxVertexNum][MaxVertexNum];边表
    	int vexum,arcnum;//顶点数量、边的数量
    }MGraph

*  **图的邻接表存储**

#define MaxVertexNum 100;
    //边表结点
    typedef struct ArcNode{
        
    	int adjvex;
    	struct ArcNode* next;
    };
    //顶点表结点
    typedef struct VNode{
        
    	VertexType data;
    	ArcNode *firstarc;
    }Adjlist[MaxVertexNum];
    //邻接表
    typedef struct{
        
    	Adjlist adjlist[MaxvertexNum];
    	int vexnum,arcnum;
    }ALGraph

*  **图的广度优先遍历BFS**
 *  从任意顶点v出发，然后访问与其邻接的所有顶点（w1,w2…wn),最后再对(w1,w2…wn)的邻接顶点进行访问

void BFSTraverse(ALGraph G){
        
    	for(int i=0;i<G.vexnum;i++){
        //对visited[]数组进行初始化
    		visited[i]=false;
    	}
    	InitQueue(Q);
    	for(int i=0;i<G.vexnum;i++){
        
    		if(visited[i]==fasle)//对每一个连通分量调用一次BFS函数
    			BFS(G,i);
    	}
    }
    //从任意顶点v出发，然后访问与其邻接的所有顶点（w1,w2...wn),最后再对(w1,w2...wn)的邻接顶点进行访问
    void BFS(ALGraph G,int v){
        
    	//借助队列
    	visit(v);//先访问该顶点v
    	visited[v]=true;
    	EnQueue(Q,v);
    	ArcNode *p;
    	while(Queue(Q)!=NULL){
        
    		DeQueue(Q,v);
    		p=G.adjlist[v].firstarc;//访问与顶点v邻接的顶点
    		while(p!=NULL){
        
    			if(visited[p->dajvex]==false){
        //与顶点v邻接的顶点未被访问，则对其进行访问
    				visit(p->dajvex);
    				visited[p->dajvex]=true;
    				EnQueue(Q,p->adjvex);
    			}
    			p=p->next;
    		}//当p为NULL，与顶点v邻接的顶点都被访问完
    	}
    }

*  **图的深度优先遍历DFS**
 *  先访问顶点v,然后再访问与顶点v邻接的顶点w,再访问与顶点w邻接的顶点p

void DFSTraverse(ALGraph G){
        
    	for(v=0;v<vexnum;v++){
        
    		visited[v]=false;
    	}
    	for(v=0;v<G.vexnum;v++){
        
    		if(visited[v]==false)
    			DFS(G,v);
    	}
    }
    //递归思想
    void DFS(ALGraph G,int v){
        
    	ArcNode *p;
    	visit(v);
    	visited[v]=true;
    	p=G.adjlist[v].firstarc;
    	while(p!=NULL){
        
    		if(visited[p->adjvex]==false){
        //未被访问
    			DFS(G,P->adjvex)
    		}
    		//如果已被访问
    		p=p->next;//回退到最近被访问的一个结点
    	}
    }

*  **拓扑排序**

bool TopoLogicalSort(ALGraph G){
        
    	//利用栈
    	InitStack(S);
    	ArcNode *p;
    	for(int i=0;i<G.vexnum;i++){
        //初始将所有入度为0的结点入栈
    		if(indegree[i]==0) push(S,i);
    	}
    	int count=0;//记录当前已经输出的结点数
    	while(StackEmpty(s)!=NULL){
        
    		pop(S,i);
    		print(G.adjlist[i].data);
    		count++;
    		for(p=G.adjlist[i].firstarc;p;p=p->next){
        //将所有i指向的顶点的入度减1，并将入度减为0的顶点压入栈
    		v=p->adjvex;
    		indegree[v]--;
    		if(indegree[v]==0) push(s,v);	
    		}
    	}
    	if(count<G.vexnum) return false;//该图中存在回路
    	else return true;
    }

*  **设计一个算法，求不带权无向连通图G中距顶点v最远的顶点**

//不带权的无向连通图，距离顶点v最远的顶点的距离即为顶点v距离该顶点边数最多的顶点
    //利用BFS
    void GetMaxDistance(AlGraph G,int v){
        
    	ArcNode *p;
    	VertexType temp;
    	InitQueue(Q);
    	visited[v]=true;
    	EnQueue(Q,v);
    	while(QueueEmpty(Q)!=NULL){
        
    		DeQueue(Q,v);
    		temp=v->data;
    		p=G.adjlist[v].firstarc;
    		while(p!=NULL){
        
    			if(visited[p->dajvex]==false){
        
    				visited[p->adjvex]=true;
    				EnQueue(Q,p->adjvex);
    			}
    			p=p->next;
    		}//while p==NULL;
    	}//while Q==NULL
    	print(temp);//打印出距离顶点v最远的顶点的信息
    }

*  **在有向图G中，从顶点r到图G的每个顶点的路径都可达，则称顶点r为G的根结点。求存于邻接表G中的图的所有顶点**

int sum=0;
    void DFS(AlGraph G,int v){
        
    	ArcNode *p;
    	sum++;
    	visited[v]=true;
    	p=G.adjlist[v].firstarc;
    	while(p!=NULL){
        
    		if(visited[p->adjvex]==false){
        
    			DFS(G,P->adjvex);
    		}
    		p=p->next;
    	}
    }
    void GetVertex(AlGraph G){
        
    	for(int i=0;i<G.vexnum;i++){
        
    		DFS(G,i);
    		if(sum==G.vexnum) print(G.adjlist[i].data);//将根结点的信息打印出来
    	}
    }

*  **将邻接表转化为邻接矩阵**

void Convert(AlGraph &G,int edge[m][n]){
        
    	//邻接矩阵初始化
    	for(int j=0;j<G.vexnum;j++){
        
    		for(int k=0;k<G.vexnum;k++)
    			edge[j][k]=0;
    	}
    	for(int i=0;i<G.vexnum;i++){
        
    		p=G.adjlist[i].firstarc;
    		while(p!=NULL){
        
    			adjlist[i][p->adjvex]=1;
    			p=p->next;
    		}
    	}
    }

*  **邻接矩阵转化为邻接表**

void Convert(AlGraph &G,int edge[n][n]){
        
    	//邻接表顶点表初始化
    	for(int i=0;i<G.vexnum;i++){
        
    		G.adglist[i].firstarc=NULL;
    	}
    	for(int j=0;j<G.vexnum;j++){
        
    		for(k=0;k<G.vexnum;k++){
        
    			if(edge[j][k]==1){
        
    				ArcNode *p=(ArcNode *)malloc(sizeof(LNode));
    				p->adjvex=k;
    				p->next=G.adjlist[i].firstarc;
    				G->adjlist[i].firstarc=p;//头插法
    			}
    		}
    	}
    }

*  **写一个算法对有n个顶点邻接表存储的有向图，求顶点k的入度**

int count(AlGraph G,int k){
        
    	ArcNode *p;
    	int sum=0;
    	for(int i=0;i<G.vexnum;i++){
        
    		p=G.adjlist[i].firstarc;
    		while(p!=NULL){
        
    			if(p->adjvex==k){
        
    				sum++;
    				break;
    			}
    			p=p->next;
    		}
    	}//for循环
    	return sum;
    }