243 lines
5.8 KiB
C++
243 lines
5.8 KiB
C++
/* 圖形的追蹤: 相鄰串列與廣度優先搜尋法(BFS) - 含權重顯示 */
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <string.h>
|
||
#define MAX_V 100 /*最大節點數*/
|
||
#define TRUE 1
|
||
#define FALSE 0
|
||
|
||
/*定義資料結構*/
|
||
typedef struct node_tag {
|
||
int vertex;
|
||
struct node_tag *link;
|
||
} Node;
|
||
|
||
/*定義佇列結構*/
|
||
typedef struct {
|
||
int items[MAX_V];
|
||
int front;
|
||
int rear;
|
||
} Queue;
|
||
|
||
Node *adjlist[MAX_V+1]; /*宣告相鄰串列*/
|
||
int visited[MAX_V+1]; /*記錄頂點是否已拜訪*/
|
||
int total_vertex;
|
||
int weight_matrix[MAX_V+1][MAX_V+1]; /* 儲存權重矩陣 */
|
||
|
||
void build_adjlist(void);
|
||
void show_adjlist(void);
|
||
void show_weight_matrix(void);
|
||
void bfs(int);
|
||
Node *searchlast(Node *);
|
||
|
||
/*佇列操作函數*/
|
||
Queue* createQueue() {
|
||
Queue *q = (Queue*)malloc(sizeof(Queue));
|
||
q->front = -1;
|
||
q->rear = -1;
|
||
return q;
|
||
}
|
||
|
||
int isEmpty(Queue* q) {
|
||
return q->front == -1;
|
||
}
|
||
|
||
void enqueue(Queue* q, int value) {
|
||
if(q->front == -1)
|
||
q->front = 0;
|
||
q->rear++;
|
||
q->items[q->rear] = value;
|
||
}
|
||
|
||
int dequeue(Queue* q) {
|
||
int item = q->items[q->front];
|
||
if(q->front == q->rear) {
|
||
q->front = -1;
|
||
q->rear = -1;
|
||
} else {
|
||
q->front++;
|
||
}
|
||
return item;
|
||
}
|
||
|
||
int main()
|
||
{
|
||
build_adjlist(); /*以相鄰串列表示圖形*/
|
||
show_weight_matrix(); /*顯示權重矩陣*/
|
||
show_adjlist(); /*顯示串列之資料*/
|
||
puts("\n------Breadth First Search------");
|
||
bfs(1); /*圖形之廣度優先搜尋，以頂點1為啟始頂點*/
|
||
printf("\n");
|
||
return 0;
|
||
}
|
||
|
||
void build_adjlist()
|
||
{
|
||
FILE *fptr;
|
||
Node *node, *lastnode;
|
||
int vi, vj;
|
||
char line[256];
|
||
int weight;
|
||
int line_count = 0;
|
||
|
||
fptr = fopen("down_1.dat", "r");
|
||
if (fptr == NULL) {
|
||
perror("down_1.dat");
|
||
exit(0);
|
||
}
|
||
|
||
// 計算總頂點數
|
||
while (fgets(line, sizeof(line), fptr)) {
|
||
line_count++;
|
||
}
|
||
total_vertex = line_count; // 修改：移除減1
|
||
rewind(fptr);
|
||
|
||
// 初始化權重矩陣為0
|
||
for(int i = 0; i <= total_vertex; i++)
|
||
for(int j = 0; j <= total_vertex; j++)
|
||
weight_matrix[i][j] = 0;
|
||
|
||
// 初始化相鄰串列
|
||
for (vi = 1; vi <= total_vertex; vi++) {
|
||
visited[vi] = FALSE;
|
||
adjlist[vi] = (Node *)malloc(sizeof(Node));
|
||
adjlist[vi]->vertex = vi;
|
||
adjlist[vi]->link = NULL;
|
||
}
|
||
|
||
// 讀取下三角形矩陣
|
||
for (vi = 1; vi <= total_vertex; vi++) {
|
||
// 修改：只讀取到第vi個元素（下三角部分）
|
||
for (vj = 1; vj < vi; vj++) {
|
||
if (fscanf(fptr, "%d", &weight) != 1) {
|
||
printf("Error reading weight at vi=%d, vj=%d\n", vi, vj);
|
||
continue;
|
||
}
|
||
|
||
// 儲存權重到矩陣
|
||
weight_matrix[vi][vj] = weight;
|
||
weight_matrix[vj][vi] = weight; // 因為是無向圖，所以對稱儲存
|
||
|
||
// 若有相鄰關係（weight = 1），則建立連結
|
||
if (weight == 1) {
|
||
// 加入 vi -> vj 的連結
|
||
node = (Node *)malloc(sizeof(Node));
|
||
node->vertex = vj;
|
||
node->link = NULL;
|
||
lastnode = searchlast(adjlist[vi]);
|
||
lastnode->link = node;
|
||
|
||
// 加入 vj -> vi 的連結（因為是無向圖）
|
||
node = (Node *)malloc(sizeof(Node));
|
||
node->vertex = vi;
|
||
node->link = NULL;
|
||
lastnode = searchlast(adjlist[vj]);
|
||
lastnode->link = node;
|
||
}
|
||
}
|
||
// 讀取對角線元素（一定是0，可以跳過）
|
||
fscanf(fptr, "%d", &weight);
|
||
}
|
||
|
||
fclose(fptr);
|
||
}
|
||
|
||
/* 修改顯示權重矩陣的函數，使其更清晰 */
|
||
void show_weight_matrix()
|
||
{
|
||
int i, j;
|
||
printf("\n=== Weight Matrix ===\n");
|
||
printf(" ");
|
||
for(j = 1; j <= total_vertex; j++) {
|
||
printf("V%-3d", j);
|
||
}
|
||
printf("\n");
|
||
|
||
for(i = 1; i <= total_vertex; i++) {
|
||
printf("V%-3d", i);
|
||
for(j = 1; j <= total_vertex; j++) {
|
||
printf("%-4d", weight_matrix[i][j]);
|
||
}
|
||
printf("\n");
|
||
}
|
||
printf("\n");
|
||
}
|
||
|
||
/*顯示各相鄰串列之資料*/
|
||
void show_adjlist()
|
||
{
|
||
int index;
|
||
Node *ptr;
|
||
puts("Head adjacency nodes");
|
||
puts("------------------------------");
|
||
for (index = 1; index <= total_vertex; index++) {
|
||
printf("V%-2d ",adjlist[index]->vertex);
|
||
ptr = adjlist[index]->link;
|
||
while (ptr != NULL) {
|
||
printf("--> V%d ",ptr->vertex);
|
||
ptr = ptr->link;
|
||
}
|
||
printf("\n");
|
||
}
|
||
}
|
||
|
||
/*圖形之廣度優先搜尋*/
|
||
void bfs(int start)
|
||
{
|
||
Queue* q = createQueue();
|
||
Node* ptr;
|
||
|
||
// 將起始節點加入佇列
|
||
enqueue(q, start);
|
||
visited[start] = TRUE;
|
||
|
||
while(!isEmpty(q)) {
|
||
// 從佇列取出節點並印出
|
||
int currentVertex = dequeue(q);
|
||
printf("V%d ", currentVertex);
|
||
|
||
// 將所有相鄰且未拜訪的節點加入佇列，並按節點編號排序
|
||
int neighbors[MAX_V];
|
||
int neighborCount = 0;
|
||
|
||
// 收集所有未訪問的相鄰節點
|
||
ptr = adjlist[currentVertex]->link;
|
||
while(ptr != NULL) {
|
||
if(!visited[ptr->vertex]) {
|
||
neighbors[neighborCount++] = ptr->vertex;
|
||
}
|
||
ptr = ptr->link;
|
||
}
|
||
|
||
// 將相鄰節點按編號排序
|
||
for(int i = 0; i < neighborCount - 1; i++) {
|
||
for(int j = 0; j < neighborCount - i - 1; j++) {
|
||
if(neighbors[j] > neighbors[j + 1]) {
|
||
int temp = neighbors[j];
|
||
neighbors[j] = neighbors[j + 1];
|
||
neighbors[j + 1] = temp;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 按順序加入佇列
|
||
for(int i = 0; i < neighborCount; i++) {
|
||
enqueue(q, neighbors[i]);
|
||
visited[neighbors[i]] = TRUE;
|
||
}
|
||
}
|
||
|
||
free(q);
|
||
}
|
||
|
||
/*搜尋串列最後節點函數*/
|
||
Node *searchlast(Node *linklist)
|
||
{
|
||
Node *ptr;
|
||
ptr = linklist;
|
||
while (ptr->link != NULL)
|
||
ptr = ptr->link;
|
||
return ptr;
|
||
}
|