程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 無向圖的一節點到另一節點的最短路徑(邊數最少的路徑)(采用鄰接表存儲)

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

編輯:關於C語言

 

// 無向圖的一節點到另一節點的最短路徑(邊數最少的路徑)(采用鄰接表存儲).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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved