邻接表的相关操作（类C语言）-创新互联

目录

1.内容

2.分析

3.代码

1）头文件（Head.H)

2）功能函数(function.cpp)

3）主函数(main.cpp)

4.运行结果（DEV）

5.总结

针对于有向图和无向图的邻接表的建立，求顶点的度以及广度和深度遍历图。（由于有向网和无向网与有向图和无向图大致一致，只是多了权值，这里不再赘述）

结构：图的所有顶点存储在一个数组当中，然后数组中的每一个元素又是一个链表的头节点。

求顶点的度：对于有向图来说，出度就是顶点所在行所链接的元素的个数（使用链表的遍历即可）

 入度就是指指向这个顶点的个数，需要遍历每一行的链表，找到有多少结点链接了这   个顶点。（比如求D点的入度，也就是看有哪些行链接了D点）

深度遍历：采用了递归的思想（类比二叉树）

广度遍历：类似于二叉树的层序遍历。

在广度和深度遍历的时候，都需要考虑到图不连通的情况，故我在下面的代码中每个遍历都由两个函数构成。

我在这儿是建立了一个项目，包括了头文件、功能函数以及主函数

#ifndef _FUNC_H 
#define _FUNC_H   

#define MVNum 100   //大顶点数
#define OK 1;
#define ERROR 0;

typedef char VerTexType;  //顶点数据类型 
typedef int Status; 
typedef int QElemType;

 
typedef struct ArcNode{  //边结点 
	int adjvex;    //邻接点的下标
	struct ArcNode *nextarc;  //指向下一个邻接点 
}ArcNode;

typedef struct VNode{  //顶点信息 
	VerTexType data;   //存放结点的内容
	ArcNode *firstarc;  //指向第一个邻接点 
}VNode,AdjList[MVNum];  //建立头结点和包含头结点的数组AdjList;  

typedef struct{
	AdjList vertices;   //包含头节点的数组 
	int vexnum,arcnum;  //边数和点数 
}ALGraph;

//队列的结构体
typedef struct QNode{
	QElemType data;  //数据
	struct QNode *next;  //指向下一个节点 
}QNode,*QueuePtr;
//链队列中又存在着头尾指针
typedef struct{
	QueuePtr front;  //队头指针
	QueuePtr rear;  //队尾指针 
}LinkQueue;

extern Status CreateUDG(ALGraph &G);
extern Status LocateVex(ALGraph &G,VerTexType v);
extern Status CreateDG(ALGraph &G);
extern Status CalculateUDGD(ALGraph &G,VerTexType v);
extern Status CalculateDGI(ALGraph &G,VerTexType v);
extern Status CalculateSum(ALGraph &G,VerTexType v);
extern void DFSTraverse(ALGraph G);
extern void DFS(ALGraph G,int v);
extern void BFSTraverse(ALGraph G);
extern void BFS(ALGraph G,int v);
extern Status Reverse(ALGraph G);
extern void print();

extern Status InitQueue(LinkQueue &Q);
extern Status EnQueue(LinkQueue &Q,int e);
extern Status DeQueue(LinkQueue &Q,QElemType &e);
extern Status  QueueEmpty(LinkQueue Q);
extern Status DestroyQueue(LinkQueue &Q);

#endif

#includeusing namespace std;
#include "Head.H"

bool visited[MVNum];  //查看点是否被遍历过 

//菜单栏
void print(){
	cout<<"==========================="<>G.vexnum>>G.arcnum;  //输入顶点数和边数
	cout<<"请输入各个顶点的内容：";
	for(i=0;i>G.vertices[i].data;   //建立数组的头节点 
		G.vertices[i].firstarc=NULL;  //使头节点指针的指向均为空 
	}
	for(k=0;k>v1>>v2;	
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		ArcNode* p1=new ArcNode;  //开辟一个结点
		p1->adjvex=j;   
		p1->nextarc=G.vertices[i].firstarc;  //头插法插入 
		G.vertices[i].firstarc=p1;
		ArcNode* p2=new ArcNode;  //开辟节点
		p2->adjvex=i;
		p2->nextarc=G.vertices[j].firstarc; 
		G.vertices[j].firstarc=p2;
	}
	return OK;	
}
//有向图
Status CreateDG(ALGraph &G){
	int i,j,k;
	VerTexType v1,v2;
	cout<<"请输入此有向图的顶点和边数：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"请输入每个顶点的内容："; 
	for(i=0;i>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	}
		
	for(k=0;k>v1>>v2; //输入相邻两点
		i=LocateVex(G,v1);  //定位
		j=LocateVex(G,v2);
		ArcNode *p=new ArcNode; //开辟一个空间
		p->adjvex=j;
		p->nextarc=G.vertices[i].firstarc;  //头插法插入 
		G.vertices[i].firstarc=p; 
	} 
	return OK; 
} 
Status LocateVex(ALGraph &G,VerTexType v){
	int i;
	for(i=0;inextarc;
		n++;
	} 
	return n;
} 
//有向图的入度
//需要把每个顶点遍历一次，找到到点i的情况，增加1 
Status CalculateDGI(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1)  return -1;  //输入的顶点错误的情况
	int i,j=LocateVex(G,v);  
	int n=0;  //计数
	ArcNode *p; //临时指针 
	for(i=0;iadjvex==j)
				n++;
			p=p->nextarc;	
		}	
	}
	return n; 
} 
//有向图的总度 
Status CalculateSum(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1) return  -1;
	return CalculateUDGD(G,v)+CalculateDGI(G,v); 
}
//遍历输出(深度优先搜索遍历） 
void DFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
		if(visited[p->adjvex]==false) DFS(G,p->adjvex);
	} 
}
//广度优先算法
void BFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
			if(visited[p->adjvex]==false){
				visited[p->adjvex]=true;
				EnQueue(Q,p->adjvex);
			}
		}
	} 
}
//存储结构的遍历
Status Reverse(ALGraph G){
	int i,j;
	ArcNode *p;
	for(i=0;i";
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			cout<adjvex].data<<"->";
		cout<<""<next=NULL;  //头指针的指针域置空
	return OK;
} 
//入队列
Status EnQueue(LinkQueue &Q,int e){
	QueuePtr p=new QNode;  //开辟一个空间
	p->data=e;    //内容存储
	Q.rear->next=p;
	p->next=NULL;
	Q.rear=p;
	return OK; 
} 
//出队列
//判断是否为空
//不为空，判断是否是只有一个元素 
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear)  return ERROR;
	QueuePtr p=Q.front->next; 
	e=p->data;  //得到元素值 
	Q.front->next=p->next;
	if(p==Q.rear){
		Q.rear=Q.front;
	} 
	delete p;
	return OK;
} 
//判空
Status  QueueEmpty(LinkQueue Q){
	return (Q.front==Q.rear); 
}
//销毁队列
Status DestroyQueue(LinkQueue &Q){
	QueuePtr p;
	while(Q.front){
		p=Q.front;
		Q.front=Q.front->next;
		delete p;
	}
	return OK;
} 

#includeusing namespace std; 
#include "head.H"

int main(int argc, char** argv) {
	VerTexType v;
	ALGraph G;
	char order1,order2;  //选择用char类型，使得当选择输入为字母时，不会出错。 
	cout<<"============================"<>order1;			
	}while(order1!='1'&&order1!='2'&&order1!='0');
	switch(order1){
		case '1':
			do{
				print();
				cout<<"请输入你的选择：";
				cin>>order2;
				switch(order2){
					case '1':
						CreateUDG(G);
						cout<<"此无向图的邻接表建立成功！！！"<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<>order2;
				switch(order2){
					case '1':
						CreateDG(G);
						cout<<"此有向图的邻接表建立成功！！！"<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<