/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號
//定義鄰接矩陣表示的圖類型Graph:
typedef struct
{
VType v[MAXVNUM]; //頂點序列(頂點編號從0開始)
EType w[MAXVNUM][MAXVNUM]; //鄰接矩陣
int vn, en; //頂點數,邊數
int kind; //圖的種類：=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
}Graph;
int visited[MAXVNUM]; //訪問標誌數組(=1已訪問，=0未訪問)。遍歷時用到的全局量。
/* 創建圖G
參數Vex是存放頂點序列的數組
參數VVW是整數數組，以{Vi,Vj,Wij,...,-1}的形式依次存放各邊的起止點序號(Vi,Vj)和權(Wij)，-1是數據結束標誌
參數kind=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //頂點數
G.kind = kind; //圖的種類
//置頂點序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化鄰接矩陣:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//構造鄰接矩陣:
p = 0; //VVW數組元素“指針”
n = 0; //邊計數器
while (VVW[p] != -1)
{//只要p未到結束位置便繼續:
i = VVW[p]; //邊的起點序號
j = VVW[p + 1]; //邊的終點序號
w = VVW[p + 2]; //邊的權
G.w[i][j] = w; //置鄰接矩陣的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是無向圖(網),
G.w[j][i] = G.w[i][j]; //則置(i,j)的對稱位置(j,i)
n++; //邊計數器加1
p += 3; //p指向下壹組(Vi,Vj,Wij)
}//end while
G.en = n; //邊數
}//CreateGraph
/* 返回G中頂點i的壹個未曾訪問過的鄰接點(序號) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //鄰接點序號初始為"空"
//在鄰接矩陣的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若當前元素是無效元素,
continue; //則繼續找。
if (!visited[j])
{//若當前有效元素未曾訪問過,則作為鄰接點a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 訪問頂點i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 從第i個頂點出發深度優先遍歷連通圖G */
/* 調用DFS前可能需初始化數組visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //訪問i頂點
visited[i] = 1; //標註i頂點已訪問
a = NextAdjVex(G, i); //找出壹個i的鄰接點a
while (a != EMPTY)
{//只要a存在便繼續:
if (visited[a] == 0) //若a未曾訪問,
DFS(G, a); //則從a出發繼續進行深度優先遍歷。
a = NextAdjVex(G, i); //找出i的下壹個鄰接點a
}//end while
}//DFS
/* 從第i個頂點出發深度優先遍歷圖G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各頂點的訪問標誌為0(未曾訪問):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //從i出發遍歷
//若G非連通圖，執行壹次DFS無法遍歷所有頂點，還需用如下for對尚未訪問的頂點DFS。
//若G是連通圖，執行壹次DFS就已遍歷所有頂點，此時如下for什麽也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //對尚未訪問的頂點DFS
}//DFSTrav
//顯示圖的鄰接矩陣
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //頂點數
//以表格形式輸出數組：
//輸出表頭：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//輸出表體(矩陣元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM