#include<iostream>
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;typedef char VertexType;
typedef int EdgeType;#define MAXVEX 100
#define INF 65535
bool visited[MAXVEX] ;typedef struct Graph
{VertexType vexs[MAXVEX];   //頂點表EdgeType arc[MAXVEX][MAXVEX]; // 鄰接矩陣，邊表int vexnum, arcnum;		      //圖的當前頂點數和弧數
}MGraph;void CreateGraph(MGraph* Graph)
{cout << "請輸入頂點數和邊數："<<endl;cin >> Graph->vexnum >> Graph->arcnum;//請輸入頂點cout << "請輸入頂點" << endl;for (int i = 0; i < Graph->vexnum; i++){cin >> Graph->vexs[i];}//初始化鄰接矩陣for (int i = 0; i < Graph->vexnum; i++){for (int j = 0; j < Graph->vexnum; j++){Graph->arc[i][j] = INF;}}//輸入邊cout << "請輸入邊:" << endl;for (int i = 0; i < Graph->arcnum; i++){int x, y, v;cin >> x >> y >> v;Graph->arc[x][y] = v;Graph->arc[y][x] = v;}}void print_graph(MGraph* G)
{for (int i = 0; i < G->vexnum; i++){for (int j = 0; j < G->vexnum; j++){cout << G->arc[i][j] << "\t";}cout << "\n";}}//深度遍歷（遞歸）
void DFS(const MGraph* G, int i)
{visited[i] = true;cout << i << "\t";for (int j = 0; j < G->vexnum; j++){if (!visited[j] && G->arc[i][j] != INF ){DFS(G, j);}}
}//深度遍歷(非遞歸)
void DFS01(const MGraph* G, int i)
{visited[i] = true;stack<int> s;s.push(i);while (!s.empty()){i = s.top();s.pop();cout << i << "\t";for (int j = 0; j < G->vexnum; j++){if (!visited[j] && G->arc[i][j] != INF){visited[j] = true;s.push(j);}}}}//廣度遍歷
void BFS(const MGraph* G, int i)
{queue<int> Q;Q.push(i);visited[i] = true;while (!Q.empty()){//出隊列i = Q.front();Q.pop();cout << i << "\t";//入隊列for (int j = 0; j < G->vexnum; j++){if (!visited[j] && G->arc[i][j] != INF){visited[j] = true;Q.push(j);}}}}
int main()
{MGraph* G = new MGraph;CreateGraph(G);print_graph(G);BFS(G, 0);}