圖的存儲結構及周遊操作

圖的順序存儲結構–鄰接矩陣

• 圖的鄰接矩陣的結構定義

#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;
	}
}