最短路径

图G采用邻接表存储，设计算法求不带权无向连通图G从顶点u到顶点v的一条最短路径

由于是不带权的图，采用广度优先，对于每一个结点，都需要将和它联通的所有结点访问，比较是否等于v

//图G采用邻接表存储，设计算法求不带权无向连通图G从顶点u到顶点v的一条最短路径//由于是不带权的无向连通图，一条边的长度为1，所以u和v的最短路径即距离u到v的边数最少的顶点序列//利用队列结构输出最短路径（逆路径序列）//设计非循环队列#define maxn 100typedef struct anode {
       int adjvex;//该边的邻接点编号    struct anode* nexarc;//指向下一条边的指针    int weight;//该边的相关信息，比如权值}arcnode;//边结点类型typedef struct vnode {
       //InfoTyoe info; 顶点的其他信息    arcnode* firstarc;//指向第一个边结点}Vnode;//邻接表头结点类型typedef struct {
       vnode adjlist[10000];//邻接表头结点数组    int n, e;//图中顶点数n和边数e}adjgraph;typedef struct {
   	int data;	int parent;//前一个顶点的位置}Queue;//用front和rear两个整型变量分别作为队列的头尾指针void ShortPath(adjgraph* G, int u, int v) {
       int w, h;    arcnode* p;    Queue qu[maxn];    int front = -1,rear=-1;    int visited[maxn];    rear++;//rear++表示有一个结点进队    qu[rear].data = u;    qu[rear].parent = -1;     for (int i = 0; i < G->n; i++) {
           visited[i] = 0;    }      visited[u] = 1;//u结点入队 标记为已经访问过    while(front!=rear){
   //队不空时循环        front++;//出此时队的顶点        w = qu[front].data;                 if (w == v) {
               h = front;//通过队列输出路径之逆            cout << "path:";            while (qu[h].parent != -1)            {
                        cout << "->" << qu[h].data;                h = qu[h].parent;                       }            break;        }        p = G->adjlist[w].firstarc;   while(p!=NULL) {
               if (visited[p->adjvex] == 0)            {
                   visited[p->adjvex] = 1;                rear++;//将未访问过的点加入邻接点                qu[rear].data = p->adjvex;                qu[rear].parent = front;            }            p = p->nexarc;        }    }}

注意：

通过

w = qu[front].data;

p = G->adjlist[w].firstarc;

来进行：出队一个结点（此结点为队列中最早入队的结点）访问与这个结点相邻的所有结点

最远顶点

图G采用邻接表存储，设计算法求不带权无向连通图G从顶点u出发最远的一个顶点

思路：即求距离顶点u的边数最多的顶点，从u出发一层一层拓展，最后到达的一个顶点即为距离u最远的顶点

不需要求出具体路径，因此采用普通队列（STL中的queue)

#define maxn 100int Maxdist(adjgraph* G, int v) {
       arcnode* p;    int visited[maxn];    for (int i = 0; i < G->n; i++) {
           visited[i] = 0;    }//也可以用memset(visited,0,sizeof(visited))    queue
   
    qu;    qu.push(v);    int m;     while (!qu.empty()) {
           m = qu.front();        qu.pop();        p = G->adjlist[m].firstarc;//找第一个邻接点        while (p != nullptr) {
               if (visited[p->adjvex] != 0) {
                   qu.push(p->adjvex);                //j = p->adjvex 邻接点为顶点j                visited[p->adjvex] = 1;            }            p = p->nexarc;        }   //步骤为:先找第一个邻接点，再将所有未访问过的邻接点入队，且判断是否已经访问过，如果未访问过则进队改邻接点，然后找下一个邻接点            }    return m;}

习题1.有一人在1号城市，目标是5号城市，可是无法直达。现在求一种乘坐方式，使得转机的次数最少

输入

5 7 1 5

1 2

1 3

2 3

2 4

3 4

3 5

4 5

输出2

//最少转机次数#include 
   
     struct note {
   int x;//城市编号 int s;//转机次数};int main(){
   struct note que[2501]; int e[51][51]={
   0},visited[51]={
   0}; int head,tail; int i,j,n,m,a,b,cur,start,end,flag=0;cin>>n>>m>>start>>end;//城市个数 航线数 起点 终点for(i = 1;i <= n;i++){
   for(j = 1;j <= n;j++)if(i == j) e[i][j] = e[j][i] = 0;elsee[i][j] = e[j][i] = 1e6;//初始化距离}for(i = 1;i <=m;i++){
   	cin>>a>>b;e[a][b] = e[b][a] = 1;}head = 1;tail = 1;//队列初始化que[tail].x = start;que[tail].s = 0;visited[start] = 1;tail++;while(tail > head){
   	cur = que[head].x;//当前队列中首元素的编号	for(i = 1;i <= n;i++)	{
   		if(visited[i] == 0 && e[cur][i] < 1e6)		{
   			que[tail].x = i;			que[tail].s  = que[head].s +1;			tail++;			visited[i] = 1;//标记进入了队列		}		if(que[tail].x == end)		{
   			flag = 1;			break;		}	}	if(flag)	 break;	head++;//注意head++要写在后面，只有一个点拓展结束后才能进行出队，一开始自己写的是cur = que[head++].x;}cout<

你可能感兴趣的文章

TensorFlow初学者必须了解的55个经典案例