圖鄰接表建立無向圖存儲周遊

//1圖的鄰接矩陣表示法和鄰接表建立無向圖存儲

#include<iostream>
using namespace std;
#define//最大頂點數

//1.1圖的鄰接矩陣表示法建立無向圖存儲
#define//無窮
typedef char VerType;//資料類型
typedef int ArcType;//權值類型
//圖結構類型
typedef struct {
  VerType  v[MaxNum];//頂點表
  ArcType a[MaxNum][MaxNum];//鄰接矩陣
  int vernum, arcnum;  //點數，邊數
}AMGraph;
//定位
int locate(AMGraph G, VerType v1) {
  for (int i = 0; i < G.vernum; i++) {
    if (G.v[i] == v1)
      return i;
  }
  return -1;
}
//建立無向圖
bool createUDN(AMGraph &G) {
  cout << "Please input the vernum and arcnum" << endl;
  cin >> G.vernum >> G.arcnum;
  int i,j,p,q;
  VerType v1, v2;
  ArcType w;
  //初始化點的名字
  cout << "Please input the name of vernum in order " << endl;
  for (i = 0; i < G.vernum; i++) cin >> G.v[i];
  //初始化鄰接矩陣
  for (i = 0; i < G.vernum; i++) {
    for (j = 0; j < G.vernum; j++) {
      if (i != j)
        G.a[i][j] = MaxInt;
      else
        G.a[i][j] = 0;
    }
  }
  //開始操作,構造鄰接表
  cout << "Please input arcnum graph " << endl;
  for (i = 0; i < G.arcnum; i++) {
    cin >> v1 >> v2 >> w;
    p = locate(G, v1); q = locate(G, v2);
    G.a[p][q] = w;
     G.a[q][p] = G.a[p][q];
  }
  return true;
}
void show(AMGraph G) {
  int i, j;
  for (i = 0; i < G.vernum; i++) {
    for (j = 0; j < G.vernum; j++) {
      if(G.a[i][j]==MaxInt)  printf("INF\t");
      else printf("%-3d\t", G.a[i][j]);
    }
    cout << endl;
  }
}      

bool visited[MaxNum] = { false };      

//1.深度優先搜尋
void Dfs_AM(AMGraph G, int v) {//從第v個
  cout << G.v[v] << " ";
  visited[v] = true;
  for (int w = 0; w < G.vernum; w++) {
    if ((G.a[v][w] != 0 )&& (G.a[v][w] != MaxInt) && (!visited[w])) {//表示是為未被通路過的鄰接點
      Dfs_AM(G, w);
    }
  }
}      

//隊的結構
typedef  int QElemType;
typedef struct QNode {
  QElemType node;
  struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
  QueuePtr front, rear;
}LinkQueue;
//1.初始化有帶頭結點的隊
bool initQueue(LinkQueue &L) {
  L.front = L.rear = new QNode;
  L.front->next = NULL;
  return true;
}
//2.判空
bool isEmpty(LinkQueue L) {
  if (L.front == L.rear) return true;
  else return false;
}
//3.入隊
bool EnQueue(LinkQueue &L, QElemType e) {
  QNode * p = new QNode;
  p->node = e;
  p->next = NULL;
  L.rear->next = p;
  L.rear = p;
  return true;
}
//4.出隊
bool DeQueue(LinkQueue&L, QElemType &node) {
  if (isEmpty(L))
    return false;
  QNode * temp = L.front->next;//從首元結點開始出去
  node = temp->node;
  L.front->next = temp->next;
  //隊最後一出隊
  if (L.rear == temp) {
    L.rear = L.front;
  }
  delete temp;
  temp = NULL;
  return true;
}      

//廣度搜尋
int FirstAdjVex(AMGraph G, int u) {
  for (int i = 0; i < G.vernum; i++) {
    if (G.a[u][i] != 0 && G.a[u][i] != MaxInt) {
      return i;
    }
  }
  return -1;
}
int NextAdjVex(AMGraph G, int u, int w) {
  for (int i = w+1; i < G.vernum; i++) {
    if (G.a[u][i] != 0 && G.a[u][i] != MaxInt) {
      return i;
    }
  }
  return -1;
}      

void BFS(AMGraph G, int v) {
  LinkQueue L;
  initQueue(L);
  EnQueue(L, v);
  visited[v] = true;
  cout << G.v[v] << " ";
  while (!isEmpty(L)) {
    DeQueue(L,v);
    for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
      if (!visited[w]) {
        cout << G.v[w]<<" ";
        EnQueue(L, w); visited[w] = true;
      }
    }
  }
}      

int main() {
  AMGraph G;
  createUDN(G);
  show(G);
  char ch;
  cout << "Please input the value of initial point" << endl;
  cin >> ch;
  int v = locate(G, ch);
  cout << "深度搜尋" << endl;
  Dfs_AM(G, v); cout << endl;
  memset(visited, false, sizeof(visited));
  cout << "廣度搜尋" << endl;
  BFS(G, v);
}