用廣搜搜鄰接矩陣

只是從某一點開始搜，如果是遍歷全圖的話就每個頂點挨個搜一遍

#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #include<queue> #define inf 65535 using namespace std; typedef struct mygraph {int ver[1000];int arc[100][100];int num_ver,num_edge; } Graph; int vis[100]; void create(Graph *G)//鄰接矩陣建圖 {int i,j,k;scanf("%d%d",&G->num_ver,&G->num_edge);//輸入節點數和邊數for(i=0; i<G->num_ver; i++)//輸入邊集scanf("%d",&G->ver[i]);for(i=0; i<G->num_ver; i++)//權值初始化{for(j=0; j<G->num_edge; j++)G->arc[i][j]=inf;}int a,b,c;for(i=0; i<G->num_edge; i++)//輸入邊集{scanf("%d%d%d",&a,&b,&c);G->arc[a][b]=c;G->arc[b][a]=c;} }queue<int>q; void bfs(Graph *g,int x)//廣搜 {int i,tmp,tmp1,tmp2;while(!q.empty())q.pop();q.push(x);vis[x]=1;while(!q.empty()){tmp=q.front();printf("%d",tmp);q.pop();for(i=0; i<g->num_ver; i++){if(!vis[i]&&g->arc[tmp][i]!=inf){q.push(i);vis[i]=1;}}} }int main() {int i,j,k;Graph myG;create(&myG);memset(vis,0,sizeof(vis));bfs(&myG,0);printf("\n");// for(i=0; i<myG.num_ver; i++)//打印鄰接矩陣 // { // for(j=0; j<myG.num_ver; j++) // printf("%5d ",myG.arc[i][j]); // printf("\n"); // }return 0; }/* 5 6 0 1 2 3 4 0 1 9 0 2 2 0 4 6 1 2 3 2 3 5 3 4 1 */

測試數據中5 ?6代表節點數為5，邊數為,6，下面是結點名0 1 2 3 4 ?下面幾行中分別為為 弧尾(邊的起點)，弧首(邊的終點)，和邊的權值

轉載于:https://www.cnblogs.com/hjch0708/p/7554834.html

總結

以上是生活随笔為你收集整理的图论 用广搜搜邻接矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。