数据结构 C 图的存储结构和两种遍历

图的存储结构邻接矩阵

typedef struct graph{
int** connection;//邻接矩阵（实质是二维数组）
int numNodes;//矩阵阶数
}*graphPtr;

优点

便于判断两个顶点之间是否有边，即根据A[i][j]=0或1来判断。
便于计算各个顶点的度。对于无向图，邻接矩阵第i行元素之和就是顶点i的度；对于有向图，第i行元素之和就是顶点i的出度，第1列元素之和就是顶点i的入度。

缺点

不便于增加和删除顶点。
不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O(n^2)。
空间复杂度高。如果是有向图，n个顶点需要n^2个单元存储边。如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角(或上三角)的元素，这样需要n(n- 1)/2个单元即可。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为O(n^2)，这对于稀疏图而言尤其浪费空间。

邻接表

邻接表：实质上是邻接矩阵的压缩存储

typedef struct AdjacencyNode{//邻接结点边表
   int subscript;//邻接点域
   struct AdjacencyNode* next;//链域
}AdjacencyNode,*AdjacentNodePtr;
typedef struct AdjacencyList{//邻接表顶点表
   int numNodes;//结点数
   struct AdjacencyNode* header;//一维数组
}AdjacencyList,*AdjacencyListPtr;

优点

便于增加和删除顶点。
便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+ e)。
空间效率高。对于一个具有n个顶点e条边的图G,若G是无向图，则在其邻接表表示中有n个顶点表结点和2e个边表结点;若G是有向图，则在它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此，邻接表或逆邻接表表示的空间复杂度为O(n+e),适合表示稀疏图。对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法。

缺点

不便于判断顶点之间是否有边，要判定vi和yj之间是否有边，就需扫描第i个边表，最坏情况下要耗费O(n)时间。
不便于计算有向图各个顶点的度。对于无向图，在邻接表表示中顶点vi的度是第i个边表中的结点个数。在有向图的邻接表中，第i个边表上的结点个数是顶点vi的出度，但求vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点的出度较难。

图的遍历

图的两种遍历：深度优先搜索(DFS)和广度优先搜索(WFS)，两种遍历算法的实现都需要使用访问标志数组visitedPtr[i]来标记当前结点i是否已经被访问

深度优先搜索(DFS)

DFS:使用了访问标志数组和递归

void DFS(graphPtr paraGraphPtr, int paraNode){
   int i;
   visitedPtr[paraNode]=1;//将paraNode标记为1，表示该结点已经访问过
   printf("%dt",paraNode);
   for(i=0;inumNodes;i++){
       if(!visitedPtr[i]){//如果有未被访问的结点
           if(paraGraphPtr->connection[paraNode][i]){//如果有paraNode的邻接点i(即[paraNode][i]为1)
               DFS(paraGraphPtr,i);//对paraNode的尚未被访问的邻接点i递归调用DFS搜索
           }//of if
       }//of if
   }//of for
}//of DFS

广度优先搜索(WFS)

WFS: 使用了访问标志数组和队列

void WFS(graphPtr paraGraphPtr, int paraStart){
   //初始化辅助队列
   //printf("Begin to initialize queue.rn");
   QueuePtr tempQueue=initQueue();
   enqueue(tempQueue,paraStart);
   //printf("paraStart enqueued.rn");
   visitedPtr[paraStart]=1;
   printf("%dt",paraStart);

   int i,j,tempNode;
   i=0;//i计数
   while(!isQueueEmpty(tempQueue)){//队列不为空
       tempNode=dequeue(tempQueue);//tempNode接收出队元素
       //printf("tempNode=%drn",tempNode);
       visitedPtr[tempNode]=1;//标记tempNode已经被访问
       i++;//计数
       for(j=0;jnumNodes;j++){//遍历图寻找没有被访问且与tempNode有边的结点
           if( visitedPtr[j]==0 && paraGraphPtr->connection[tempNode][j]==1){
               printf("%dt",j);
               visitedPtr[j]=1;
               enqueue(tempQueue,j);
           }
       }
       //printf("i=%d",i);
   }
   //printf("i=%d",i);
}

使用邻接矩阵的两种图遍历算法的完整代码：

#include 
#include 
#include  
#define QUEUE_SIZE 10//队列空间大小 
int* visitedPtr;//记录结点是否已被访问 
typedef struct graphNodeQueue{
	int* node;
	int front;
	int rear; 
}graphNodeQueue,*QueuePtr;
 
QueuePtr initQueue(){
	QueuePtr resultPtr=(QueuePtr)malloc(sizeof(struct graphNodeQueue));
	resultPtr->node=(int*)malloc(QUEUE_SIZE*sizeof(int));
	resultPtr->front=0;
	resultPtr->rear=1;
	return resultPtr;
}

bool isQueueEmpty(QueuePtr paraQueue){
	if((paraQueue->front+1)%QUEUE_SIZE==paraQueue->rear){
		return true;
	}
	return false;
}

void enqueue(QueuePtr paraQueue,int paraNode){
	//判断队满
	if((paraQueue->rear+1)%QUEUE_SIZE==paraQueue->front%QUEUE_SIZE){//注意paraQueue->front也要%QUEUE_SIZE
		printf("Error,tring to enqueue %d,but queue full.rn");
		return;
	} 
	//让结点入队（入尾指针处） 
	paraQueue->node[paraQueue->rear]=paraNode;
	//更新队列尾指针 
	paraQueue->rear= (paraQueue->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueue){
	//判断队空 
	if(isQueueEmpty(paraQueue)){
		printf("Error,empty queue.rn");
		return -1;
	}
	paraQueue->front=(paraQueue->front+1)%QUEUE_SIZE;
	//printf("dequeue %d ends.rn", paraQueue->node[paraQueue->front]);
	return paraQueue->node[paraQueue->front];
}

typedef struct graph{
	int** connection;//邻接矩阵 
	int numNodes;//矩阵阶数 
}*graphPtr; 	

graphPtr initGraph(int paraSize,int** paraData){
	int i,j;
	graphPtr resultPtr=(graphPtr)malloc(sizeof(struct graph));
	resultPtr->connection=(int**)malloc(paraSize*sizeof(int*));
	resultPtr->numNodes=paraSize; 
	for(i=0;iconnection[i]=(int*)malloc(paraSize*sizeof(int));
		for(j=0;jconnection[i][j]=paraData[i][j];
			//printf("i=%d,j=%d,connection[i][j]=%d.rn",i,j,resultPtr->connection[i][j]);
		}
	}
	return resultPtr;
}

void initVisitedPtr(graphPtr paraGraphPtr){
	visitedPtr=(int*)malloc(paraGraphPtr->numNodes*sizeof(int));
	int i;
	for(i=0;inumNodes;i++){
		visitedPtr[i]=0;
		//printf("visitedPtr[%d]=%drn",i,visitedPtr[i]);
	}
}
 
void DFS(graphPtr paraGraphPtr, int paraNode){
	int i;
	visitedPtr[paraNode]=1;//将paraNode标记为1，表示该结点已经访问过 
	printf("%dt",paraNode);
	for(i=0;inumNodes;i++){
		if(!visitedPtr[i]){//如果有未被访问的结点 
			if(paraGraphPtr->connection[paraNode][i]){//如果有paraNode的邻接点i(即[paraNode][i]为1) 
				DFS(paraGraphPtr,i);//递归调用DFS搜索邻接点i 
			}
		}
	}
}

void WFS(graphPtr paraGraphPtr, int paraStart){
	//初始化辅助队列
	//printf("Begin to initialize queue.rn");
	QueuePtr tempQueue=initQueue();
	enqueue(tempQueue,paraStart);
	//printf("paraStart enqueued.rn");
	visitedPtr[paraStart]=1;
	printf("%dt",paraStart);
	
	int i,j,tempNode;
	i=0;//i计数 
	while(!isQueueEmpty(tempQueue)){//队列不为空 
		tempNode=dequeue(tempQueue);//tempNode接收出队元素 
		//printf("tempNode=%drn",tempNode);
		visitedPtr[tempNode]=1;//标记tempNode已经被访问 
		i++;//计数 
		for(j=0;jnumNodes;j++){//遍历图寻找没有被访问且与tempNode有边的结点 
			if( visitedPtr[j]==0 && paraGraphPtr->connection[tempNode][j]==1){
				printf("%dt",j);
				visitedPtr[j]=1;
				enqueue(tempQueue,j);
			}
		} 
		//printf("i=%d",i);
	}
	//printf("i=%d",i);
}
 
void graphTranverseTest(){
	//初始化邻接矩阵	
	int myGraph[5][5] = { 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 1, 1, 0, 0}};
	printf("Preparing datarn");
	int i, j;
	int** tempPtr= (int**)malloc(5*sizeof(int*));
	for(i=0;i<5;i++){
		tempPtr[i]=(int*)malloc(5*sizeof(int));
		for(j=0;j<5;j++){
			tempPtr[i][j]=myGraph[i][j];
		}
	}
	printf("Data ready.rn");
	//初始化图
	graphPtr tempGraph=initGraph(5,tempPtr);
	printf("Graph initialized.rn");
	//DFS
	printf("DFS:rn");
	initVisitedPtr(tempGraph);//先将VisitedPtr数组初始化为0 
	DFS(tempGraph,4);
	//WFS
	printf("rnWFS:rn");
	initVisitedPtr(tempGraph);//将VisitedPtr数组初始化为0 
	WFS(tempGraph,4);
}
int main(){
	graphTranverseTest();
	return 0;
}

运行结果：

使用邻接表的广度优先遍历算法：

#include 
#include 
#include  
#define QUEUE_SIZE 10//队列空间大小 
int* visitedPtr;//记录结点是否已被访问 
typedef struct graphNodeQueue{
	int* node;
	int front;
	int rear; 
}graphNodeQueue,*QueuePtr;
 
QueuePtr initQueue(){
	QueuePtr resultPtr=(QueuePtr)malloc(sizeof(struct graphNodeQueue));
	resultPtr->node=(int*)malloc(QUEUE_SIZE*sizeof(int));
	resultPtr->front=0;
	resultPtr->rear=1;
	return resultPtr;
}

bool isQueueEmpty(QueuePtr paraQueue){
	if((paraQueue->front+1)%QUEUE_SIZE==paraQueue->rear){
		return true;
	}
	return false;
}

void enqueue(QueuePtr paraQueue,int paraNode){
	//判断队满
	if((paraQueue->rear+1)%QUEUE_SIZE==paraQueue->front%QUEUE_SIZE){//注意paraQueue->front也要%QUEUE_SIZE
		printf("Error,tring to enqueue %d,but queue full.rn");
		return;
	} 
	//让结点入队（入尾指针处） 
	paraQueue->node[paraQueue->rear]=paraNode;
	//更新队列尾指针 
	paraQueue->rear= (paraQueue->rear+1)%QUEUE_SIZE;
}

int dequeue(QueuePtr paraQueue){
	//判断队空 
	if(isQueueEmpty(paraQueue)){
		printf("Error,empty queue.rn");
		return -1;
	}
	paraQueue->front=(paraQueue->front+1)%QUEUE_SIZE;
	//printf("dequeue %d ends.rn", paraQueue->node[paraQueue->front]);
	return paraQueue->node[paraQueue->front];
}

typedef struct graph{
	int** connection;//邻接矩阵 
	int numNodes;//矩阵阶数 
}*graphPtr; 	

graphPtr initGraph(int paraSize,int** paraData){
	int i,j;
	graphPtr resultPtr=(graphPtr)malloc(sizeof(struct graph));
	resultPtr->connection=(int**)malloc(paraSize*sizeof(int*));
	resultPtr->numNodes=paraSize; 
	for(i=0;iconnection[i]=(int*)malloc(paraSize*sizeof(int));
		for(j=0;jconnection[i][j]=paraData[i][j];
			//printf("i=%d,j=%d,connection[i][j]=%d.rn",i,j,resultPtr->connection[i][j]);
		}
	}
	return resultPtr;
}

typedef struct AdjacencyNode{//邻接结点边表 
	int subscript;//邻接点域
	struct AdjacencyNode* next;//链域 
}AdjacencyNode,*AdjacentNodePtr;
typedef struct AdjacencyList{//邻接表顶点表 
	int numNodes;//结点数 
	struct AdjacencyNode* header;//一维数组
}AdjacencyList,*AdjacencyListPtr;

AdjacencyListPtr graphToAdjacentList(graphPtr paraGraph){
	//为邻接表分配空间 
	AdjacencyListPtr tempAdjList=(AdjacencyListPtr)malloc(sizeof(struct AdjacencyList));
	tempAdjList->numNodes=paraGraph->numNodes;
	tempAdjList->header=(AdjacentNodePtr)malloc(tempAdjList->numNodes*sizeof(struct AdjacencyNode));
	//创建邻接表
	int i,j;
	AdjacentNodePtr p, q;//p用于指示结点，q用于创建结点 
	for(i=0;inumNodes;i++){
		//初始化边表 
		p=&(tempAdjList->header[i]);//p指向边表的头结点 
		p->subscript=-1;
		p->next=NULL;
		for(j=0;jnumNodes;j++){
			if(paraGraph->connection[i][j]==1){
				//创建新结点
				q=(AdjacentNodePtr)malloc(sizeof(struct AdjacencyNode));
				q->subscript=j;
				q->next=NULL;
				//链接
				p->next=q;
				p=q;//更新指针p,让它指向最后一个结点，便于下一次链接新结点 
			}//Of if 
		} //Of for
	} //Of for
	return tempAdjList;
}

void printAdjList(AdjacencyListPtr paraAdjList){
	printf("The graph is:rn");
	int i;
	AdjacentNodePtr p; 
	for(i=0;inumNodes;i++){
		p=paraAdjList->header[i].next;
		while(p!=NULL){
			printf("%dt",p->subscript);
			p=p->next;
		}//Of while
		printf("rn");
	}//Of for
} 

void WFS(AdjacencyListPtr paraAdjList,int paraStart){
	//初始化访问标志数组
	int i;
	visitedPtr=(int*)malloc(paraAdjList->numNodes*sizeof(int));
	for(i=0;inumNodes;i++){
		visitedPtr[i]=0;
	} 
	//队列
	QueuePtr tempQueue=initQueue();
	printf("%dt",paraStart);
	visitedPtr[paraStart]=1;
	enqueue(tempQueue,paraStart);//让已访问的元素入队 
	int tempNode;//接收出队元素 
	AdjacentNodePtr p;//指向每一个边表的头结点 ，遍历边表
	while(!isQueueEmpty(tempQueue)){//队列不为空 
		tempNode=dequeue(tempQueue);//出队元素 
		for(p=&(paraAdjList->header[tempNode]);p!=NULL;p=p->next){
			if(visitedPtr[p->subscript]==0){
				printf("%dt",p->subscript);
				visitedPtr[p->subscript]=1;
				enqueue(tempQueue,p->subscript); 
			}//Of if
		}//Of for
	}//Of while
} 
void WFSofAdjacencyListTest(){
	int i, j;
	int myGraph[5][5] = { 
		{0, 1, 0, 1, 0},
		{1, 0, 1, 0, 1}, 
		{0, 1, 0, 1, 1}, 
		{1, 0, 1, 0, 0}, 
		{0, 1, 1, 0, 0}};
	int** tempPtr;
	printf("Preparing datarn");
		
	tempPtr = (int**)malloc(5 * sizeof(int*));
	for (i = 0; i < 5; i ++) {
		tempPtr[i] = (int*)malloc(5 * sizeof(int));
		for (j = 0; j < 5; j ++) {
			tempPtr[i][j] = myGraph[i][j];
			//printf("i = %d, j = %d, %drn", i, j, tempPtr[i][j]);
		}//Of for j
	}//Of for i
 
	printf("Data readyrn");
	
	graphPtr tempGraphPtr = initGraph(5, tempPtr);
	AdjacencyListPtr tempListPtr = graphToAdjacentList(tempGraphPtr);

	printAdjList(tempListPtr);
	printf("The WFS:rn");
	WFS(tempListPtr, 4);
}
int main(){
	WFSofAdjacencyListTest();
	return 0;
}

运行结果：

数据结构 C 图的存储结构和两种遍历

C/C++/C#相关栏目本月热门文章