精华内容
下载资源
问答
  • 要求建立图的存储结构(邻接表或邻接矩阵),输入任意的一个图,显示图的广度优先搜索遍历路径。
  • 图的广度优先搜索遍历,以我的理解是:先以一个顶点做起点,一层一层的进行输出打印。 这里引用书上的一个例子。 完整代码如下(邻接表的形式): #include <stdio.h> #include <stdlib.h> #include &...

    图的广度优先搜索遍历,以我的理解是:先以一个顶点做起点,一层一层的进行输出打印。
    这里引用书上的一个例子。
    在这里插入图片描述
    完整代码如下(邻接表的形式):

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MVNum 100 //最大顶点数 
    //创建一个中断函数 
    void Interrupt(void)//创建一个中断函数 
    {
    	while(1)//用于检测换行符,使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    //引入队列,这里是顺序队列 
    typedef struct
    {
    	int data[MVNum];//分配给队列一个数组空间 
    	int front;//队列头 
    	int rear;//队列尾 
    }SqQueue;
    
    void InitQueue(SqQueue &Q)//初始化队列 
    {
    	Q.front = Q.rear = 0;//使队列头和队列尾都为0 
    }
    
    void EnQueue(SqQueue &Q,int e)//入队 ,由于是循环队列,故少用一个元素空间,该函数在有MAXSIZE-1个元素时便已判断为满 
    {
    	if((Q.rear+1)%MVNum == Q.front)//判断队列是否为满 ,这里是循环队列队列满的条件是 (Q.rear+1)%MAXSIZE == Q.front
    	{
    		printf("队列已满!\n");
    	}
    	else
    	{
    		if(Q.rear == MVNum)//如果队尾超出最大值但队列又不满,便使其对最大值求余运算 
    			Q.rear = Q.rear%MVNum;
    		Q.data[Q.rear] = e;//使变量e的值入队 
    		Q.rear++;//并使队尾加一 
    	}
    }
    
    bool QueueEmpty(SqQueue Q)//队列判空操作 
    {
    	if(Q.front == Q.rear)//如果队列为空,返回true,否则返回false 
    		return true;
    	else
    		return false;
    }
    
    int DeQueue(SqQueue &Q)//出队 
    {
    	int a = 0;
    	if(QueueEmpty(Q))//首先判断队列是否为空,队列为空的条件是 Q.front == Q.rear
    		printf("队列为空!\n");
    	else
    	{
    		a = Q.data[Q.front];//导出队头元素数据 
    		Q.front++;//使队头加一 
    		if(!QueueEmpty(Q))//在队列非空的情况下,如果队头等于最大值,也对最大值做求余运算 
    			Q.front = Q.front%MVNum;
    	}
    	return a;
    }
    //创建矩阵表操作 
    typedef struct ArcNode
    {
    	int adjvex;//该边所指向的顶点的位置 
    	struct ArcNode *nextarc;//该向下一条边的指针 
    	int weight;//权值 
    }ArcNode;
    typedef struct VNode//顶点信息 
    {
    	char data;//顶点名称 
    	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MVNum];//AdjList表示邻接表类型 
    typedef struct//邻接表 
    {
    	AdjList vertices;
    	int vexnum,arcnum;//图的当前顶点数和边数 
    }ALGraph;
    
    void InitGraph(ALGraph &G)//图的初始化 
    {
    	int i;
    	for(i=0;i<MVNum;i++)
    		G.vertices[i].firstarc = NULL;//使所有的第一个结点都置空,也就是后面设定的尾指针的判空操作 
    }
    
    void CreateGraph(ALGraph &G)//图的创建 
    {
    	int i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&G.vexnum,&G.arcnum);//顶点数和边数的赋值 
    	Interrupt();//该函数用于检测并吸收换行符 
    	printf("请输入顶点名称(连续输入):");
    	for(i=0;i<G.vexnum;i++)//利用循环输入图中顶点名称 
    	{
    		scanf("%c",&a);
    		G.vertices[i].data = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量,j和k是用来记录次数的 
    	for(i=0;i<G.arcnum;i++)//利用循环输入所有边的两个顶点和权值 
    	{
    		printf("请输入边的两个顶点:");
    		scanf("%c %c",&b,&c);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.arcnum;j++)//该操作为书上的函数LocateVex操作 
    		{
    			if(G.vertices[j].data == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.arcnum;k++)
    		{
    			if(G.vertices[k].data == c)//找到输入的顶点c的位置 
    			break;
    		}
    		ArcNode *p1,*p2;//创建两个野结点 
    		p1 = (ArcNode*)malloc(sizeof(ArcNode));
    		p1->adjvex = k;
    		p1->weight = 1;//权值赋值 
    		p1->nextarc = G.vertices[j].firstarc;//类似于头插法 
    		G.vertices[j].firstarc = p1;//并使头结点永远放在第一位 
    		p2 = (ArcNode*)malloc(sizeof(ArcNode));
    		p2->adjvex = j;
    		p2->weight = 1;
    		p2->nextarc = G.vertices[k].firstarc;
    		G.vertices[k].firstarc = p2;
    	}
    }
    
    void InputGraph(ALGraph G)//邻接表的输出 
    {
    	int i,j;//记录次数 
    	ArcNode *p1;//用于遍历链表 
    	printf("邻接表为:\n");
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{
    		printf("%c",G.vertices[i].data);
    		p1 = G.vertices[i].firstarc;
    		while(p1)//当p为空时,结束循环 
    		{
    			printf(" --> %d",p1->adjvex);
    			p1 = p1->nextarc;//p指向p的下一个结点 
    		}	
    		printf("\n");
    	}
    }
    //广度优先搜索遍历 
    ArcNode *p;//创建一个全局变量,以便于进行查找 
    int FirstAdjVex(ALGraph G,int u)//表示u的第一个邻接点 
    {
    	p = G.vertices[u].firstarc;//全局变量的赋值 
    	if(p == NULL)//如果头结点的下一个结点为空,返回负数,否则返回p结点的值 
    		return -1;
    	else
    		return p->adjvex;
    }
    int NextAdjVex(ALGraph G)//下一个邻接点 
    {
    	p = p->nextarc;//由于p为全局变量,这里直接指向下一个便是 
    	if(p == NULL)//如果头结点的下一个结点为空,返回负数,否则返回p结点的值  
    		return -1;
    	else
    		return p->adjvex;
    }
    bool visited[MVNum];//访问标志数组 ,其初始值为false 
    void InitVisited(bool *visited)//标志数组初始化 
    {
    	for(int i=0;i<MVNum;i++)
    		visited[i] = false;
    } 
    void BFS(ALGraph G,int v)//广度优先搜索遍历 ,非递归形式 
    {
    	int u;
    	printf("%c",G.vertices[v].data);
    	visited[v] = true;//访问第v个顶点,并置访问标志数组相应分量值为true 
    	SqQueue Q;
    	InitQueue(Q);//引入队列,初始化 
    	EnQueue(Q,v);//入队 
    	while(!QueueEmpty(Q))//队列非空 
    	{
    		u = DeQueue(Q);//出队,别赋值给变量u 
    		for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G))//依次检查u的所有邻接点w,w>=0表示存邻接点
    		//函数FirstAdjVex(G,u)表示u的第一个邻接点,函数NextAdjVex(G)表示相对于w的下一个邻接点 
    			if(!visited[w])//w为u的尚未访问的邻接点 
    			{
    				printf("%c",G.vertices[w].data);
    				visited[w] = true;//访问第w个顶点,并置访问标志数组相应分量值为true 
    				EnQueue(Q,w);//w入队 
    			}
    	}
    }
    
    int main()
    {
    	ALGraph G;
    	InitGraph(G);//初始化 
    	CreateGraph(G);//邻接表的创建 
    	InputGraph(G);//邻接表的输出 
    	BFS(G,2);//广度优先搜索遍历 ,其中的2为测试值,可更换成变量 
    	return 0;
    }
    
    

    结果演示:
    代码中广度优先遍历函数是从2开始输出的(也就是C)。
    在这里插入图片描述

    展开全文
  • 经典算法之图的广度优先搜索遍历

    千次阅读 2017-12-14 12:50:04
    图的广度优先搜索遍历(BFS)类似于树的程序遍历。它的基本思想是:首先访问起始顶点v,然后选取与v邻接的全部顶点w1...wn进行访问,再依次访问与w1,....,wn邻接的全部顶点(已经访问过的除外),以此类推,直到所有...
    /************************
    author's email:wardseptember@gmail.com
    data:2017.12.14
    图的广度优先搜索遍历
    ************************/
    /*
    图的广度优先搜索遍历(BFS)类似于树的程序遍历。它的基本思想是:首先访问起始顶点v,然后选取
    与v邻接的全部顶点w1...wn进行访问,再依次访问与w1,....,wn邻接的全部顶点(已经访问过的
    除外),以此类推,直到所有顶点都被访问完。
    */
    #include<iostream>
    #define maxSize 8
    using namespace std;
    typedef struct Node {
    	int vertex;
    	struct Node *pNext;
    }Node;
    typedef struct head {
    	char data;
    	Node *first;
    }head, *Graph;
    int visit[maxSize];       //定义一个全局变量,用来判断某一结点是否被访问过
    Graph create_graph();    //创建一个邻接表
    void BFS(Graph graph, int v,int visit[maxSize]); //广度遍历连通图
    void bfs(Graph graph);       //广度遍历非连通图
    void BFSTrave(Graph graph, int i, int j);//判断顶点i和顶点j(i!=j)之间是否有路径
    int main() {
    	Graph graph = create_graph();
    	cout << "广度遍历连通图结果为:";
    	BFS(graph, 7,visit);	//Bfs(graph);广度遍历非连通图
    	cout << endl;
    
    	int i, j;
    	cout << "请输入要判断的两个顶点(0-7):";
    	cin >> i >> j;
    	BFSTrave(graph, i, j);
    	return 0;
    }
    Graph create_graph()
    {
    	//为保存顶点相关信息的数组分配空间,并对数据域赋值
    	Graph graph = (Graph)malloc(maxSize * sizeof(head));
    	int i;
    	//顶点的序号按照输入顺序从0依次向后
    	for (i = 0; i < maxSize; i++)
    		graph[i].data = 'A' + i;
    
    	//为每个节点对应的的单链表中的节点分配空间
    	Node *p00 = (Node *)malloc(sizeof(Node));
    	Node *p01 = (Node *)malloc(sizeof(Node));
    	Node *p10 = (Node *)malloc(sizeof(Node));
    	Node *p11 = (Node *)malloc(sizeof(Node));
    	Node *p12 = (Node *)malloc(sizeof(Node));
    	Node *p20 = (Node *)malloc(sizeof(Node));
    	Node *p21 = (Node *)malloc(sizeof(Node));
    	Node *p22 = (Node *)malloc(sizeof(Node));
    	Node *p30 = (Node *)malloc(sizeof(Node));
    	Node *p31 = (Node *)malloc(sizeof(Node));
    	Node *p40 = (Node *)malloc(sizeof(Node));
    	Node *p41 = (Node *)malloc(sizeof(Node));
    	Node *p50 = (Node *)malloc(sizeof(Node));
    	Node *p51 = (Node *)malloc(sizeof(Node));
    	Node *p60 = (Node *)malloc(sizeof(Node));
    	Node *p61 = (Node *)malloc(sizeof(Node));
    	Node *p70 = (Node *)malloc(sizeof(Node));
    	Node *p71 = (Node *)malloc(sizeof(Node));
    
    	//为各单链表中的节点的相关属性赋值
    	p00->vertex = 1;
    	p00->pNext = p01;
    	p01->vertex = 2;
    	p01->pNext = NULL;
    	p10->vertex = 0;
    	p10->pNext = p11;
    	p11->vertex = 3;
    	p11->pNext = p12;
    	p12->vertex = 4;
    	p12->pNext = NULL;
    	p20->vertex = 0;
    	p20->pNext = p21;
    	p21->vertex = 5;
    	p21->pNext = p22;
    	p22->vertex = 6;
    	p22->pNext = NULL;
    	p30->vertex = 1;
    	p30->pNext = p31;
    	p31->vertex = 7;
    	p31->pNext = NULL;
    	p40->vertex = 1;
    	p40->pNext = p41;
    	p41->vertex = 7;
    	p41->pNext = NULL;
    	p50->vertex = 2;
    	p50->pNext = p51;
    	p51->vertex = 6;
    	p51->pNext = NULL;
    	p60->vertex = 2;
    	p60->pNext = p61;
    	p61->vertex = 5;
    	p61->pNext = NULL;
    	p70->vertex = 3;
    	p70->pNext = p71;
    	p71->vertex = 4;
    	p71->pNext = NULL;
    
    	//将顶点与每个单链表连接起来
    	graph[0].first = p00;
    	graph[1].first = p10;
    	graph[2].first = p20;
    	graph[3].first = p30;
    	graph[4].first = p40;
    	graph[5].first = p50;
    	graph[6].first = p60;
    	graph[7].first = p70;
    
    	return graph;
    }
    void BFS(Graph graph, int v, int visit[maxSize]) {//广度优先遍历连通图
    	Node *p;
    	int que[maxSize], front = 0, rear = 0;//定义一个顺序队,并初始化
    	int j;
    	cout << graph[v].data<<' ';
    	visit[v] = 1;
    	rear = (rear + 1) % maxSize;    //v入队
    	que[rear] = v;
    	while (front != rear) {   //对空说明遍历完成
    		front = (front + 1) % maxSize;   //顶点出队
    		j = que[front];
    		p = graph[j].first;      //p指向出队顶点j的第一条边
    		while (p != NULL) {     //将p的所有邻接点中未被访问的入队
    			if (visit[p->vertex] == 0) {//当前邻接顶点未被访问,则进队
    				cout << graph[p->vertex].data<<' ';
    				visit[p->vertex] = 1;
    				rear = (rear + 1) % maxSize;//该顶点进队
    				que[rear] = p->vertex;
    			}
    			p = p->pNext;       //p指向j的下一条边
    		}
    	}
    }
    void bfs(Graph graph) {   //广度优先遍历非连通图
    	int i;
    	for (i = 0; i < maxSize; ++i)
    		if (visit[i] == 0)
    			BFS(graph, i,visit);
    }
    void BFSTrave(Graph graph, int i, int j) {//判断顶点i和顶点j(i!=j)之间是否有路径
    	int k;
    	for (k = 0; k < maxSize; ++k)
    		visit[k] = 0;
    	BFS(graph, i, visit);
    	cout << endl;
    	if (visit[j] == 1)//visit[j]=1则证明访问过程遇到了j
    		cout << "两顶点间有路径" << endl;
    	else
    		cout << "两顶点间无路径" << endl;
    }
    
    

    在这里插入图片描述

    展开全文
  • 要求建立图的存储结构(邻接表或邻接矩阵),输入任意的一个图,显示图的广度优先搜索遍历路径。
  • 图的广度优先搜索遍历: 存储的数据结构为无向图的多重邻接表 类似于树的层序遍历,依次按照路径为1,2,3…进行遍历,因而每次要获得一个节点然后得到这点的未经访问的邻近点后再将此点抛弃,因此我们用队列这一...

    图的广度优先搜索遍历:

    • 存储的数据结构为无向图的多重邻接表
    • 类似于树的层序遍历,依次按照路径为1,2,3…进行遍历,因而每次要获得一个节点然后得到这点的未经访问的邻近点后再将此点抛弃,因此我们用队列这一结构。
    void BFSReverse(AMLGraph G) {
    	queue<int> a;
    	for(int i = 0; i < G.vexnum; ++i) {
    		visit[i] = unvisited;
    	}
    	for(int i = 0; i < G.vexnum; ++i) {
    		if (visit[i] == unvisited) {
    			a.push(i);
    			visit[i] = visited;
    			cout << G.adjmulist[i].data << endl;
    			while (!a.empty()) {
    				int v = a.front();
    				a.pop();
    				for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    					if (visit[w] == unvisited) {
    						a.push(w);
    						cout << G.adjmulist[w].data << endl;
    						visit[w] = visited;
    					}
    				}
    			}
    		}
    	}
    }
    

    求图的任意两点间的最短路径:

    如下:
    在这里插入图片描述
    将队列的结构改为如图所示,即每次不将队列的头部退出队列内而是每次通过移动头部指针来完成,而其他节点都附加一个前向指针(front),指向引导当前节点的前一个节点,也就是每一次的head。

    struct Node {
    	Node *next;
    	Node *front;
    	int data;
    };
    int BFSPath(AMLGraph G, string v1, string v2) {
    	int i1 = LocateVex(G.adjmulist, G.vexnum, v1);
    	int i2 = LocateVex(G.adjmulist, G.vexnum, v2);
    	//int num = 0;
    	Node *head;
    	Node *rear;
    	head = NULL;
    	rear = NULL;
    	for(int i = 0; i < G.vexnum; ++i) {
    		visit[i] = unvisited;
    	}
    	visit[i1] = visited;
    	Node *temp = new Node;
    	temp->data = i1;
    	temp->front = NULL;
    	temp->next = NULL;
    	head = rear = temp;
    	while (head) {
    		int v = head->data;
    		for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    			if (visit[w] == unvisited) {
    				Node *temp0 = new Node;
    				temp0->data = w;
    				temp0->front = head;
    				temp0->next = NULL;
    				rear->next = temp0;
    				rear = temp0;
    				visit[w] = visited;
    				if (rear->data == i2) {
    					Node *p = rear;
    					while(p) {
    						cout << p->data << endl;
    						p = p->front;
    					}
    					return 1;
    				}
    			}
    		}
    		head = head->next;
    	}
    	cout << "Not Find!" << endl;
    	return 0;
    }
    

    用如下效果图测试:

    有两个连通图:
    在这里插入图片描述
    在这里插入图片描述

    最后附上全部代码:

    //无向图的邻接多重表
    //广度优先搜索的实现
    //求两个顶点之间一条路径长度最短的路径
    #include <iostream>
    #include <stack>
    #include <list>
    #include <queue>
    using namespace std;
    #define MAX_VERTEX_NUM 20
    enum VisitIf {unvisited, visited};
    VisitIf visit[MAX_VERTEX_NUM];
    class EBox {
    public:
    	VisitIf mark; //访问标记
    	int ivex, jvex; //该边依附的两个顶点位置
    	EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
    };
    
    class VexBox {
    public:
    	string data;
    	EBox *firstedge; //指向第一条依附该顶点的边
    };
    
    class AMLGraph {
    public:
    	VexBox adjmulist[MAX_VERTEX_NUM];
    	int vexnum, edgenum; //无向图的当前顶点数和边数
    };
    
    struct Node {
    	Node *next;
    	Node *front;
    	int data;
    };
    
    int LocateVex(VexBox adj[], int num, string v) {
    	for (int i = 0; i < num; i++) {
    		if (adj[i].data == v) {
    			return i;
    		}
    	}
    }
    
    void CreateGraph(AMLGraph *G) {
    	cout << "请输入顶点数和弧数: " << endl;
    	cin >> G->vexnum >> G->edgenum;
    	cout << "请输入顶点: " << endl;
    	for (int i = 0; i < G->vexnum; i++) {
    		cin >> G->adjmulist[i].data;
    		G->adjmulist[i].firstedge = NULL;
    	}
    	for (int i = 0; i < G->edgenum; i++) {
    		cout << "请输入边的两个顶点: " << endl;
    		string v1, v2;
    		cin >> v1 >> v2;
    		int i1 = LocateVex(G->adjmulist, G->vexnum, v1);
    		int i2 = LocateVex(G->adjmulist, G->vexnum, v2);
    		//cout << i1 << "...." << i2 << endl;
    		EBox *p = new EBox;
    		p->mark = unvisited;
    		p->ivex = i1;
    		p->jvex = i2;
    		p->ilink = G->adjmulist[i1].firstedge;
    		p->jlink = G->adjmulist[i2].firstedge;
    		G->adjmulist[i1].firstedge = p;
    		G->adjmulist[i2].firstedge = p;
    	}
    }
    
    int FirstAdjVex(AMLGraph G, int v) {
    	int i = v;
    	if (G.adjmulist[i].firstedge) {
    		if (G.adjmulist[i].firstedge->ivex == i) {
    			return G.adjmulist[i].firstedge->jvex;
    		}
    		else {
    			return G.adjmulist[i].firstedge->ivex;
    		}
    	}
    	else
    		return -1;
    }
    //v是G中的某个顶点,w是v的邻接顶点
    //返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回空
    
    int NextAdjVex(AMLGraph G, int v, int w) {
    	int i1 = v;
    	int i2 = w;
    	EBox *p = G.adjmulist[i1].firstedge;
    	while (p) {
    		if (p->ivex == i1 && p->jvex != i2) {
    			p = p->ilink;
    		}
    		else {
    			if (p->ivex != i2 && p->jvex == i1) {
    				p = p->jlink;
    			}
    			else {
    				break;
    			}
    		}
    	}
    	if (p && p->ivex == i1 && p->jvex == i2) {
    		p = p->ilink;
    		if (p&&p->ivex == i1) {
    			return p->jvex;
    		}
    		else if (p&&p->jvex == i1)
    			return p->ivex;
    	}
    	if (p && p->ivex == i2 && p->jvex == i1) {
    		p = p->jlink;
    		if (p&&p->ivex == i1) {
    			return p->jvex;
    		}
    		else if (p&&p->jvex == i1)
    			return p->ivex;
    	}
    	return -1;
    }
    
    void BFSReverse(AMLGraph G) {
    	queue<int> a;
    	for(int i = 0; i < G.vexnum; ++i) {
    		visit[i] = unvisited;
    	}
    	for(int i = 0; i < G.vexnum; ++i) {
    		if (visit[i] == unvisited) {
    			cout << "连通图:" << endl;
    			a.push(i);
    			visit[i] = visited;
    			cout << G.adjmulist[i].data << endl;
    			while (!a.empty()) {
    				int v = a.front();
    				a.pop();
    				for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    					if (visit[w] == unvisited) {
    						a.push(w);
    						cout << G.adjmulist[w].data << endl;
    						visit[w] = visited;
    					}
    				}
    			}
    		}
    	}
    }
    
    int BFSPath(AMLGraph G, string v1, string v2) {
    	if (v1 == v2) {
    		cout << "the same point!" << endl;
    		return 0;
    	}
    	int i1 = LocateVex(G.adjmulist, G.vexnum, v1);
    	int i2 = LocateVex(G.adjmulist, G.vexnum, v2);
    	//int num = 0;
    	Node *head;
    	Node *rear;
    	head = NULL;
    	rear = NULL;
    	for(int i = 0; i < G.vexnum; ++i) {
    		visit[i] = unvisited;
    	}
    	visit[i1] = visited;
    	Node *temp = new Node;
    	temp->data = i1;
    	temp->front = NULL;
    	temp->next = NULL;
    	head = rear = temp;
    	stack<string> a;
    	while (head) {
    		int v = head->data;
    		for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
    			if (visit[w] == unvisited) {
    				Node *temp0 = new Node;
    				temp0->data = w;
    				temp0->front = head;
    				temp0->next = NULL;
    				rear->next = temp0;
    				rear = temp0;
    				visit[w] = visited;
    				if (rear->data == i2) {
    					Node *p = rear;
    					while(p) {
    						a.push(G.adjmulist[p->data].data);
    						p = p->front;
    					}
    					cout << a.top();
    					a.pop();
    					while (!a.empty()) {
    						cout << "->" << a.top();
    						a.pop();
    					}
    					cout << endl;
    					return 1;
    				}
    			}
    		}
    		head = head->next;
    	}
    	cout << "Not Find!" << endl;
    	return 0;
    }
    
    void PrintGraph(AMLGraph G)
    {
        EBox *p;
        for(int i = 0; i < G.vexnum; ++i)
        {
            p = G.adjmulist[i].firstedge;
            while(p != NULL)
            {
                if(p->ivex == i)    //判断相等才能知道连接上的是ivex还是jvex;
                {
                	cout <<  G.adjmulist[p->ivex].data << "------" << G.adjmulist[p->jvex].data << endl;
                    //printf("%d--%d\n", G.adjmulist[p->ivex].data, G.adjmulist[p->jvex].data);
                    p = p->ilink;
                }
                else
                {
                   cout <<  G.adjmulist[p->jvex].data << "------" << G.adjmulist[p->ivex].data << endl;
                    p = p->jlink;
                }
            }
        }
    }
    int main () {
    	AMLGraph g;
    	CreateGraph(&g);
    	//PrintGraph(g);
    	BFSReverse(g);
    	//DFSTraverse(g);
    	while (1) {
    		string v1, v2;
    		cout << "请输入你想查询的两点: " << endl;
    		cin >> v1 >> v2;
    		BFSPath(g, v1, v2);
    	}
    	return 0;
    }
    
    展开全文
  • 图的广度优先搜索遍历这里只列了迭代的算法,递归比较困难搜索遍历需要借助一个队列。 每次将当前节点出队列,以及让该节点的所有未被访问的邻接节点入队列,重复直至队列为空。 节点的出队列的顺序构成了广度优先...

    图的广度优先搜索遍历这里只列了迭代的算法,递归比较困难

    搜索遍历需要借助一个队列。
    每次将当前节点出队列,以及让该节点的所有未被访问的邻接节点入队列,重复直至队列为空。
    节点的出队列的顺序构成了广度优先搜索的遍历序列。

    采用邻接表时,复杂度为O(V+E)。采用邻接矩阵时,复杂度为O(V^2)。V为顶点数、E为边数。
    两者的空间复杂度相同。

    C++代码如下:
    这里有2个函数,分别是:
    邻接表 BFS
    邻接矩阵 BFS

    #include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    typedef int DATA_TYPE;  // 权值为int型
    const DATA_TYPE NO_EDGE = 10000000;  // 表示没有该边
    
    // 邻接矩阵
    struct AdjMatrixGraph
    {
        vector<vector<DATA_TYPE> > weights;
    };
    
    // 邻接表
    struct AdjTableGraph
    {
        vector<vector<int> > adjTable;
        vector<vector<DATA_TYPE> > adjWeights;  // 暂时用不到 维数与adjTable一致
    };
    
    // 邻接表广度优先搜索算法
    vector<int> AdjTableBFS(AdjTableGraph graph, int startNode)
    {
        int vertexNum = graph.adjTable.size();
        vector<int> visited(vertexNum, 0);
        vector<int> visitOrder;
        queue<int> trace;
        trace.push(startNode);
        visited[startNode] = 1;
    
        while (!trace.empty())
        {
            int currentNode = trace.front();
            trace.pop();
            visitOrder.push_back(currentNode);
    
            if (graph.adjTable[currentNode].size() > 0)
            {
                for (size_t i = 0; i < graph.adjTable[currentNode].size(); ++i)
                {
                    if (visited[graph.adjTable[currentNode][i]] == 0)
                    {
                        trace.push(graph.adjTable[currentNode][i]);
                        visited[graph.adjTable[currentNode][i]] = 1;
                    }
                }
            }
        }
    
        return visitOrder;
    }
    
    
    // 邻接矩阵深度优先搜索算法
    vector<int> AdjMatrixBFS(AdjMatrixGraph graph, int startNode)
    {
        int vertexNum = graph.weights.size();
        vector<int> visited(vertexNum, 0);
        vector<int> visitOrder;
        queue<int> trace;
        trace.push(startNode);
        visited[startNode] = 1;
    
        while (!trace.empty())
        {
            int currentNode = trace.front();
            trace.pop();
            visitOrder.push_back(currentNode);
    
            for (size_t i = 0; i < vertexNum; ++i)
            {
                if (visited[i] == 0 && graph.weights[currentNode][i] < NO_EDGE)
                {
                    trace.push(i);
                    visited[i] = 1;
                }
            }
        }
    
        return visitOrder;
    }
    
    
    int main(int argc, char *argv[])
    {
    
        // 图的初始化
        // 顶点编号必须为从0开始的连续的整数(若不是,先转换)
        // 图为有向图
    
        // ================邻接表方式===============
        AdjTableGraph graph;
        graph.adjTable.push_back(vector<int>{1, 3});
        graph.adjTable.push_back(vector<int>{2});
        graph.adjTable.push_back(vector<int>{4});
        graph.adjTable.push_back(vector<int>{2});
        graph.adjTable.push_back(vector<int>{});
    
        // 邻接表
        vector<int> visitOrder = AdjTableBFS(graph, 0);
        cout << "邻接表 BFS: ";
        for (size_t i = 0; i < visitOrder.size(); ++i)
        {
            cout << visitOrder[i] << " ";
        }
        cout << endl;
    
    
        // ===============邻接矩阵方式===============
        AdjMatrixGraph graph2;
        graph2.weights.push_back(vector<DATA_TYPE>{0, 8, NO_EDGE, 5, NO_EDGE});
        graph2.weights.push_back(vector<DATA_TYPE>{NO_EDGE, 0, 3, NO_EDGE, NO_EDGE});
        graph2.weights.push_back(vector<DATA_TYPE>{NO_EDGE, NO_EDGE, 0, NO_EDGE, 6});
        graph2.weights.push_back(vector<DATA_TYPE>{NO_EDGE, NO_EDGE, 9, 0, NO_EDGE});
        graph2.weights.push_back(vector<DATA_TYPE>{NO_EDGE, NO_EDGE, NO_EDGE, NO_EDGE, 0});
    
        // 邻接矩阵
        vector<int> visitOrder2 = AdjMatrixBFS(graph2, 0);
        cout << "邻接矩阵 BFS: ";
        for (size_t i = 0; i < visitOrder2.size(); ++i)
        {
            cout << visitOrder2[i] << " ";
        }
        cout << endl;
    
        return 0;
    }

    测试用例图如下:

    这里写图片描述

    编译环境(CLion 2016 with MinGW G++, GDB 7.11)

    输出结果:
    邻接表 BFS: 0 1 3 2 4
    邻接矩阵 BFS: 0 1 3 2 4

    展开全文
  • 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
  • 概念: 广度优先搜素算法(BFS) 实现类似树层次遍历,我们在实现他时候一般借助一个队列来进行实现,利用队列先进先出特点来对图进行广度优先搜索算法实现。 具体实现思路: 1、 同样,先创建一个...
  • 不过小哼已经收集了很多航班信息,现在小哼希望找到一种乘坐方式,使得转机次数最少,如何解决呢? 输入 第一行有两个整数n m s e,n表示有n个城市(城市编号为1~n),m表示有m条航线,s表示起点城市,e表示...
  • #include const intn=8; //表示最大顶点数 const inte=15; //最大边数 typedefint elemtype; boolvisited[n+1]; //标志数组用于记载某个顶点是否被访问过 classlink //定
  • 图的存储方法:邻接矩阵、邻接表  例如:有一个图如下所示: 则上图用邻接矩阵可以表示为: 用邻接表可以表示如下: 邻接矩阵可以很容易的用二维数组表示,下面主要看看怎样构成邻接表:  邻接表存储方法是一...
  • 在研究生考试中,图的深度优先搜索遍历和广度优先搜索遍历是重中之重,而通用的考试代码是C++,今天就站在考试的角度上,来分析一下这两种不同遍历。 深度优先遍历 图的深度优先遍历(DFS)类似于二叉树的先序遍历...
  • 图的广度优先搜索遍历根树的层次遍历类似 首先访问其实顶点v,然后选取与v邻接的全部顶点w0,w1,w2......进行访问,再依次访问与w0,w1,w2........邻接的所有顶点,依此类推 也就是说用到一个队列 首先让一个顶点...
  • 图的遍历   从图中某个顶点出发游历图,访遍图中其余顶点,并且使图中的每个顶点仅被访问一次的过程。 遇到的问题:图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点...
  • 图的应用——深度优先/广度优先搜索遍历 要求:以邻接矩阵或邻接表为存储结构(学号为单号的同学以邻接矩阵为存储结构,双号的同学以邻接表为存储结构)建立无向连通图,从键盘上输入指定的顶点为起始点,实现...
  • 一、 实验题目: 图的应用——深度优先/广度优先搜索遍历 二、 实验内容: 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法,实现图的深度优先和广度优先搜索遍历操作。
  • 图的遍历方式主要有两种:深度优先搜索遍历和广度优先搜索遍历。 深度优先搜索遍历 深度优先搜索遍历是类似于树的先序遍历,尽可能的对纵深方向进行搜索。基本思想为从图的某个顶点v0出发,访问此节点,然后依次从...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,776
精华内容 1,110
关键字:

图的广度优先搜索遍历