设计图的相关函数库c++

问题描述：完成在连通无向图上访问图中全部顶点及相关级别操作。

基本要求：

以图的邻接表为存储结构实现下列功能：

1.自选存储结构， 输入含n个顶点（用字符表示顶点）和e条边的图G;

2.求每个顶点的度，输出结果；

3.指定任意顶点x为初始顶点，对图G作DFS遍历，输出DFS顶点序列（提示：使用一个栈实现DFS）；

4.指定任意顶点x为初始顶点，对图G做BFS遍历，输出BFS顶点序列（提示：使用一个队列实现BFS）;

5.输入顶点x，查找图G；若存在含x的顶点，则删除该节点及其相关的边，并作DFS遍历（执行操作3）；否则输出信息“无x”；

/**
测试数据：

6

8

a
b
c
d
e
f

a b
a e
a f
b c
c e
c d
e d
d f

*/


# include<stdio.h>
# include<string.h>
# include<stdlib.h>
# include<malloc.h>

# define maxNode 100			/**定义图的最大顶点数*/

/**无向图边结点结构体*/
typedef struct edge{
	//int weight;					/**边权重值*/
	struct edge *nextEdge;		/**邻接边*/
	char no;					/**邻接顶点*/
}edge;

/**无向图顶点结点结构体*/
typedef struct verTex{
	char name;					/**顶点字符*/
	int index;					/**顶点代号*/
	edge *firstEdge;			/**顶点的第一条相邻边*/
	//bool flag;					/**判定该结点是否被访问*/
}verTex;

/**无向图结构*/
typedef struct ugraph{
	verTex nodes[maxNode];		/**顶点数组*/
	int vexNum;					/**无向图边的数目*/
	int edgeNum;				/**无向图顶点数目*/
}ugraph;

struct etemp{
	char start;
	char end;
	int weight;
}et[50];

void creatGraph(ugraph *g);			/**从文件中读取图的相关信息并创建图*/
void getDegree(ugraph *g);			/**打印输出图中每个顶点的度*/
void traverseDFS(ugraph *g,char data);			/**DFS遍历算法*/
void traverseBFS(ugraph g,char data);		/**BFS遍历算法*/
void deleteNode(ugraph *g,char node);			/**删除指定边*/
void insertNode(ugraph *g, char start, char end);			/** 将元素插入图中*/
char isReason(ugraph* g,char ch);

// 主函数
int main(){

	ugraph *g;
	g = (ugraph*)malloc(sizeof(ugraph));
	int i, j, weight, lo, flag;
	char data;
	int *degree;
	flag = 1;
	creatGraph(g);
	printf("n顶点度的计算：n");
	getDegree(g);
	printf("请输入您想开始遍历的数据：");
	fflush(stdin);
	scanf("%c", &data);
	data = isReason(g,data);
	printf("DFS非递归遍历：n");
	traverseDFS(g, data);
	printf("nBFS非递归遍历：n");
	traverseBFS(*g, data);

	printf("请输入您想删除的结点数据：");
	fflush(stdin);
	scanf("%c",&data);
	data = isReason(g, data);
	deleteNode(g, data);
	printf("请输入您想开始遍历的数据：");
	fflush(stdin);
	scanf("%c", &data);
	data = isReason(g, data);
	printf("nDFS非递归遍历：n");
	traverseDFS(g, data);
	system("pause");
	return 0;
}

int vexLocate(ugraph *g, char c){
	int i;
	i = 0;
	while(i<g->vexNum && g->nodes[i].name!=c) i++;
	if (i >= g->vexNum) {
		printf("不存在该结点！！");
		return -1;
	}
	else
		return i;
}

char isReason(ugraph *g, char ch) {

	int i, flag;
	char data;
	i = vexLocate(g, ch);
	flag = 1;
	if (!(i + 1)) {
		while (flag) {
			printf("重新输入数据：");
			fflush(stdin);
			scanf("%c", &data);
			i = vexLocate(g, data);
			if (i + 1)
				flag = 0;
		}
	}
	else
		data = ch;
	return data;
}

/** 将元素插入图中*/
void insertNode(ugraph *g, char start, char end){

	int i, j;
	edge *e, *p, *q;
	verTex n;

	// 查找待插元素的位置
	i = vexLocate(g, start);
	j = vexLocate(g, end);

	if(g->nodes[i].firstEdge!=NULL){
		//n = g->nodes[i];

		// 采用头插法将相邻边插入
		p = (edge*)malloc(sizeof(edge));
		//p ->weight = weight;
		p ->no = end;
		p->nextEdge = g->nodes[i].firstEdge;
		g->nodes[i].firstEdge = p;

	}else{
		p = (edge*)malloc(sizeof(edge));
		p->nextEdge = NULL;
		//p->weight = weight;
		p->no = end;
		g->nodes[i].firstEdge = p;
	}


	if (g->nodes[j].firstEdge != NULL) {
		//n = g->nodes[j];

		// 采用头插法将相邻边插入
		q = (edge*)malloc(sizeof(edge));
		//q->weight = weight;
		q->no = start;
		q->nextEdge = g->nodes[j].firstEdge;
		g->nodes[j].firstEdge = q;

	}
	else {
		q = (edge*)malloc(sizeof(edge));
		q->nextEdge = NULL;
		//q->weight = weight;
		q->no = start;
		g->nodes[j].firstEdge = q;
	}
}

/** 创建无向图 */
void creatGraph(ugraph *g){
	
	int i, j, weight;
	char start, end;
	i = 0;
	j = 0;
	weight = 0;
	printf("n输入顶点数：");
	scanf_s("%d", &g->vexNum,1);
	printf("n输入无向图边的数目：");
	scanf_s("%d", &g->edgeNum,1);
	//j = 
	fflush(stdin);
	printf("n请依次输入n个顶点(以字符表示)：n");
	while( i<g->vexNum){
		scanf_s("%c", &g->nodes[i].name,1);
		g->nodes[i].index = i;
		g->nodes[i].firstEdge = NULL;
		i++;
		fflush(stdin);
	};
	//i = j = weight =  0;
	printf("请依次输入e条边(以空格间隔)：起点 终点n");

	for(j=0; j<g->edgeNum; j++){
		setbuf(stdin, NULL);
		//scanf("%c %c %d", &start, &end, &weight);
		scanf("%c %c", &start, &end);
		insertNode(g, start, end);
	}
}

/** 获取图中每个结点的度数 */
void getDegree(ugraph *g){
	int k = 0,c = 0;
	int dgree = 0;
	edge* e;
	while (k < g->vexNum) {
		e = g->nodes[k].firstEdge;
		while (e != NULL)
		{
			e = e->nextEdge;
			dgree++;
		}
		printf("结点%c的度数为：%dn", g->nodes[k].name, dgree);
		dgree = 0;
		k++;
	}
}

/** DFS遍历算法 */
typedef struct stack{
	char elem[maxNode];
	int point;
	int number;
} stack;

// 元素出栈
char pop(stack *st){
	char data;
	if(!st->number)
		return NULL;
	data = st->elem[(st->point)--];
	st->number--;
	return data;
};

// 元素入栈
void push(stack *st, char data){
	st->elem[++(st->point)]=data;
	st->number++;
};

// 栈是否为空
int sisEmpty(stack *st){
	return st->number;
}

void traverseDFS(ugraph *g, char data){

	// 初始化栈
	int count;
	int eNum;
	stack *st;
	st = (stack*)malloc(sizeof(stack));
	st->point=-1;
	st->number=0;

	// 记录元素的访问情况
	bool visited[maxNode] = {0};

	int loc;
	loc = vexLocate(g, data);
	if(!visited[loc]){
		printf("%c ", g->nodes[loc].name);
		visited[loc] = 1;
	}
	count = eNum = 0;
	edge *e;
	//verTex *no;
	char no;
	int j, k;
	k = 0;
	e = g->nodes[loc].firstEdge;
	push(st, g->nodes[loc].name);
	// 当栈非空时不断循环
	while(count <g->vexNum && sisEmpty(st)){
			while(e!=NULL){
				if (!visited[vexLocate(g, e->no)]) {
					push(st, e->no);
				}
				e = e->nextEdge;
			}
		//}
		no = pop(st);
		j = vexLocate(g,no);
		if(!visited[j]){
			printf("%c ",no);
			visited[j] = 1;
			k = 1;
			count++;
		}
		e = g->nodes[j].firstEdge;
	}
}

/** BFS遍历算法 */
typedef struct queue {

	char data[100];
	int head;
	int tail;
	int number;
}Queue;

void enQueue(Queue* q, char data) {

	q->data[q->head] = data;
	q->head++;
	q->number++;
}

char deQueue(Queue* q) {
	char N;
	N = q->data[q->tail];
	q->tail++;
	q->number--;
	return N;
}

int isEmpty(Queue* q) {
	return q->number;
}

void traverseBFS(ugraph g, char start){

	edge* arc, * temp;
	char a;
	int num, loc;

	// 存储结点是否已被访问
	bool visited[maxNode] = {0};

	Queue* qu;
	qu = (Queue*)malloc(sizeof(Queue));
	qu->head = qu->tail = 0;
	qu->number = 0;

	num = vexLocate(&g, start);
	//while (start!=g.nodes[num].name)
		//num++;
	printf("%c ", g.nodes[num].name);
	visited[num] = 1;
	enQueue(qu, g.nodes[num].name);

	while (isEmpty(qu)) {
		a = deQueue(qu);
		num = 0;
		//while (a!=g.nodes[num].name)
			//num++;
		num = vexLocate(&g, a);
		arc = g.nodes[num].firstEdge;
		while (arc != NULL) {
			loc = vexLocate(&g,arc->no);
			if (!visited[loc]) {
				printf("%c ", arc->no);
				enQueue(qu, arc->no);
				visited[loc] = 1;
			}
			arc = arc->nextEdge;
		}
	}
	printf("nn");
}

/** 删除图中指定顶点 */
void deleteNode(ugraph *g,char node){
	verTex* n;
	edge* e, *temp, *pre;
	int loc,count;
	char data;
	loc = vexLocate(g,node);
	count = 0;
	// 将所有与之相关联的边进行删除
	if (loc == -1)
		printf("无此结点！！");
	else {
		e = g->nodes[loc].firstEdge;
		while (loc != -1 && e != NULL) {
			loc = vexLocate(g, e->no);
			temp = g->nodes[loc].firstEdge;
			if (temp->no == node) {
				g->nodes[loc].firstEdge = temp->nextEdge;
				count++;
			}
			else {
				pre = temp;
				temp = temp->nextEdge;
				while (temp != NULL && temp->no != node) {
					pre = temp;
					temp = temp->nextEdge;
				}
				pre->nextEdge = temp->nextEdge;
				count++;
			}
			e = e->nextEdge;
		}
	}
	loc = vexLocate(g, node);
	while (loc<g->edgeNum-1)
	{
		g->nodes[loc] = g->nodes[loc+1];
		loc++;
	}
	g->vexNum--;
	g->edgeNum -= count;
}

最后

以上就是沉默蜻蜓为你收集整理的设计图的相关函数库c++的全部内容，希望文章能够帮你解决设计图的相关函数库c++所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。