無向圖的一節點到另一節點的最短路徑（邊數最少的路徑）（采用鄰接表存儲）

 

// 無向圖的一節點到另一節點的最短路徑（邊數最少的路徑）（采用鄰接表存儲）.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include<iostream>

#define MAX 100

#define MAXQ 50

using namespace std;

struct edgeNode

{

 int no; //邊端的序號

 char info; //邊端的名稱

 struct edgeNode * next; //下一個

};

struct vexNode

{

 char info;  //節點名稱

 struct edgeNode *link; //與之相連的端點

};

//存儲節點信息

vexNode adjlist[MAX];

//循環隊列

int queue[MAXQ];

//訪問標志

bool visited[MAX];

//存儲從指定點到每一個點的路徑

int parent[MAX];

//建立鄰接表存儲,返回節點個數

int createGraph(vexNode *adjlist)

{

 int n,e;

 cout<<"請輸入節點數：";

 cin>>n;

 cout<<"請輸入邊數：";

 cin>>e;

 int i;

 for(i=1;i<=n;i++)

 {

  cout<<"請輸入節點"<<i<<"的名稱：";

  cin>>adjlist[i].info;

  adjlist[i].link = NULL;

 }

 edgeNode *p1,*p2;

   int v1,v2;

 for(i=1;i<=e;i++)

 {

  cout<<"請輸入邊"<<i<<"的二端的節點序號：";

  cin>>v1>>v2;

  p1 = (edgeNode*)malloc(sizeof(edgeNode));

  p2 = (edgeNode*)malloc(sizeof(edgeNode));

  p1->no = v1;

  p1->info = adjlist[v1].info;

  p1->next = adjlist[v2].link;

  adjlist[v2].link = p1;

  p2->no = v2;

  p2->info = adjlist[v2].info;

  p2->next = adjlist[v1].link;

  adjlist[v1].link = p2;

 }

 return n;

}

//廣度優先搜索無向無權圖,返回起始點

int BFS(vexNode *adjlist,int *queue,bool *visited,int *parent)

{

 int front,rear,v1;

 cout<<"請輸入從哪個序號的點開始搜索：";

 cin>>v1;

 front = 0;

 rear = 1;

 queue[rear] = v1;

 int i;

 //訪問標志清空

 for(i=1;i<MAX;i++)

  visited[i] = false;

 visited[v1] = true;

 cout<<"廣度優先搜索次序為："<<endl;

 cout<<"節點"<<v1<<",名稱"<<adjlist[v1].info<<endl;

 int vx;

 edgeNode *p;

 while(front != rear)

 {

  front = (front + 1)%MAXQ;

  vx = queue[front];

  p = adjlist[vx].link;

  while(p!=NULL)

  {

   if(!visited[p->no])

   {

    visited[p->no] = true;

    cout<<"節點"<<p->no<<",名稱"<<adjlist[p->no].info<<endl;

    rear = (rear + 1)%MAXQ;

    queue[rear] = p->no;

    parent[p->no] = vx;

   }

   p=p->next;

  }

 }

 return v1;

}

//打印起始點到目標節點的最少邊數目的路徑（最短路徑）

//v是目標節點

void print_line(vexNode *adjlist,int *parent,int v)

{

 int j = v;

 if(parent[j] != 0)

  print_line(adjlist,parent,parent[j]);

 cout<<adjlist[j].info<<"  ";

}

 

 

int _tmain(int argc, _TCHAR* argv[])

{

 int cases;

 cout<<"請輸入案例的個數：";

 cin>>cases;

 while(cases--)

 {

  //創建鄰接表

  int n = createGraph(adjlist);

  //廣度優先搜索

  int v1 = BFS(adjlist,queue,visited,parent);

  //起始節點沒有前驅節點

  parent[v1] =0;

  int v;

  cout<<"請輸入目標節點：";

  cin>>v;

  //打印起始點到目標節點的最少邊數目的路徑（最短路徑）

  cout<<"從起始節點"<<adjlist[v1].info<<"到"<<adjlist[v].info<<"節點的最短路徑為："<<endl;

  print_line(adjlist,parent,v);

  cout<<endl;

 }

 system("pause");

 return 0;

}

------------------------------------------------程序測試------------------------------------------------

                                        

 

請輸入案例的個數：1

請輸入節點數：8

請輸入邊數：10

請輸入節點1的名稱：r

請輸入節點2的名稱：s

請輸入節點3的名稱：t

請輸入節點4的名稱：u

請輸入節點5的名稱：v

請輸入節點6的名稱：w

請輸入節點7的名稱：x

請輸入節點8的名稱：y

請輸入邊1的二端的節點序號：1 2

請輸入邊2的二端的節點序號：1 3

請輸入邊3的二端的節點序號：2 4

請輸入邊4的二端的節點序號：3 5

請輸入邊5的二端的節點序號：3 6

請輸入邊6的二端的節點序號：5 6

請輸入邊7的二端的節點序號：5 8

請輸入邊8的二端的節點序號：6 7

請輸入邊9的二端的節點序號：6 8

請輸入邊10的二端的節點序號：7 8

請輸入從哪個序號的點開始搜索：2

廣度優先搜索次序為：

節點2,名稱s

節點4,名稱u

節點1,名稱r

節點3,名稱t

節點6,名稱w

節點5,名稱v

節點8,名稱y

節點7,名稱x

請輸入目標節點：6

從起始節點s到w節點的最短路徑為：

s  r  t  w

請按任意鍵繼續. . .

 

作者 heyongluoyao8