資料結構實驗6 ：圖的存儲與周遊（鄰接矩陣的深度優先周遊DFS和鄰接表的廣度優先周遊BFS）

文章目錄

• 題目一
• • 題目要求
  • 輸入
  • 輸出
  • 說明
• 代碼實作
• • 鄰接矩陣圖相關定義：
  • 鄰接矩陣圖的相關操作：
  • 深度優先搜尋DFS和列印鄰接矩陣圖
  • 主函數
  • 運作結果
• 題目二
• • 題目要求
  • 輸入
  • 輸出
  • 說明
• 代碼實作
• • 鄰接表相關定義
  • 圖的相關操作
  • 深度優先搜尋BFS和列印鄰接表圖
  • 主函數
  • 運作結果圖

題目一

題目要求

利用鄰接矩陣存儲無向圖，并從0号頂點開始進行深度優先周遊。

輸入

輸入第一行是兩個整數n1 n2，其中n1表示頂點數（則頂點編号為0至n1-1），n2表示圖中的邊數。

之後有n2行輸入，每行輸入表示一條邊，格式是“頂點1 頂點2”，把邊插入圖中。

例如：

4 4

0 1

1 3

0 3

0 2

輸出

先輸出存儲圖的鄰接矩陣，同一行元素之間空1格，最後一個元素之後不要有空格。

之後空一行後輸出從0号頂點開始的深度優先周遊序列，頂點編号之間空1格。

例如，對于上面的示例輸入，輸出為：

0 1 1 1

1 0 0 1

1 0 0 0

1 1 0 0

0 1 3 2

說明

輸入第1個4表示有4個頂點，第2個4表示有4條邊。之後的4行輸入代表4條邊的頂點。輸出的前4行為鄰接矩陣，之後空一行，然後輸出的“0 1 3 2”是深度優先周遊序列。

代碼實作

鄰接矩陣圖相關定義：

typedef int Vertex;
typedef int WeightType;
typedef struct EdgeNode {
    Vertex v1, v2;
}*Edge;
typedef struct MatrixGraphNode {
    int vertexNum; /* 頂點數 */
    int edgeNum; /* 邊數 */
    WeightType** adjMatrix; /* 鄰接矩陣 */
    int* visited; /* 标記數組，用來标記某一個點是否被通路過，DFS時要用到，也可以把它定義為全局變量，這裡為了友善就寫在結構體裡 */
} *MatrixGraph;
           

鄰接矩陣圖的相關操作：

這裡選擇動态建立二維數組，因為不知道測試樣例最大頂點數是多少。讀者當然可以直接在定義結構體把就把

adjMatrix

定義為一個足夠大的二維數組，而不必如此麻煩的動态建立。

MatrixGraph createMatrixGraph(int vertexNum) {
    MatrixGraph graph = (MatrixGraph)malloc(sizeof(struct MatrixGraphNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;
    graph->visited = (int*)malloc(sizeof(int) * graph->vertexNum);
    /* 動态建立二維數組 */
    graph->adjMatrix = (WeightType**)malloc(sizeof(WeightType*) * graph->vertexNum);
    for (int i = 0;i < graph->vertexNum;i++)
        graph->adjMatrix[i] = (WeightType*)malloc(sizeof(WeightType) * graph->vertexNum);
    /* 初始化鄰接矩陣adjMatrix和标記數組visited */
    for (int i = 0;i < graph->vertexNum;i++) {
        graph->visited[i] = 0;
        for (int j = 0;j < graph->vertexNum;j++)
            graph->adjMatrix[i][j] = 0;
    }
    return graph;
}
void insertEdge(MatrixGraph graph, Edge edge) {
    graph->adjMatrix[edge->v1][edge->v2] = 1;
    graph->adjMatrix[edge->v2][edge->v1] = 1;
}
MatrixGraph buildMatrixGraph() {
    Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
    int vertexNum;
    scanf("%d", &vertexNum);
    MatrixGraph graph = createMatrixGraph(vertexNum);
    scanf("%d", &graph->edgeNum);
    for (int i = 0;i < graph->edgeNum;i++) {
        scanf("%d%d", &edge->v1, &edge->v2);
        insertEdge(graph, edge);
    }
    return graph;
}
           

深度優先搜尋DFS和列印鄰接矩陣圖

void DFS(MatrixGraph graph, Vertex v) {
	/* 通路目前頂點 */
    printf("%d ", v);
    graph->visited[v] = 1;
    for (int i = 0;i < graph->vertexNum;i++)
    	/* 如果w沒有被通路且和v相連，就遞歸地通路它 */
        if (!graph->visited[i] && isEdge(graph, v, i))
            DFS(graph, i);
}
void printGraph(MatrixGraph graph) {
    for (int i = 0;i < graph->vertexNum;i++)
        for (int j = 0;j < graph->vertexNum;j++)
            j == graph->vertexNum - 1 ? printf("%d\n", graph->adjMatrix[i][j]) : printf("%d ", graph->adjMatrix[i][j]);
}
           

主函數

int main() {
    MatrixGraph graph = buildMatrixGraph();
    printGraph(graph);
    DFS(graph, 0);
    system("pause");
    return 0;
}
           

運作結果

題目二

題目要求

利用鄰接表存儲無向圖，并從0号頂點開始進行廣度優先周遊。

輸入

輸入第一行是兩個整數n1 n2，其中n1表示頂點數（則頂點編号為0至n1-1），n2表示圖中的邊數。

之後有n2行輸入，每行輸入表示一條邊，格式是“頂點1 頂點2”，把邊插入圖中。在連結清單中插入元素時，在連結清單頭部插入。需要注意，由于是無向圖，是以同一條邊需要在兩條連結清單中都插入。

例如：

4 4

0 1

1 3

0 3

0 2

輸出

先按0至n1-1輸出存儲圖的鄰接表，每個連結清單占1行，同一行元素之間空1格，最後一個元素之後不要有空格。先輸出頂點編号，之後按連結清單順序輸出相鄰頂點編号。

之後空一行後輸出從0号頂點開始的廣度優先周遊序列，頂點編号之間空1格。

例如，對于上面的示例輸入，輸出為：

0 2 3 1

1 3 0

2 0

3 0 1

0 2 3 1

說明

輸入第1個4表示有4個頂點，第2個4表示有4條邊。之後的4行輸入代表4條邊的頂點。輸出前4行為鄰接表中的4個連結清單，之後空一行，然後輸出的“0 2 3 1”是深度優先周遊序列。

代碼實作

鄰接表相關定義

typedef int Vertex;
/* 邊 */
typedef struct EdgeNode {
    Vertex v1, v2;
}*Edge;
/* 鄰接點 */
typedef struct AdjVNode {
    Vertex adjVertex;
    struct AdjVNode* next;
}*AdjVNodePtr;
/* 鄰接表頭節點 */
typedef struct VertexNode {
    AdjVNodePtr firstEdge;
}*AdjList;
/* 鄰接表圖 */
typedef struct ListGraphNode {
    int vertexNum;
    int edgeNum;
    AdjList adjList;
    int* visited;
}*ListGraph;
           

圖的相關操作

ListGraph createListGraph(int vertexNum) {
    ListGraph graph = (ListGraph)malloc(sizeof(struct ListGraphNode));
    graph->vertexNum = vertexNum;
    graph->edgeNum = 0;
    graph->visited = (int*)malloc(sizeof(int));
    graph->adjList = (AdjList)malloc(sizeof(struct VertexNode) * graph->vertexNum);
    /* 初始化鄰接表和标記數組 */
    for (int i = 0;i < graph->vertexNum;i++) {
        graph->adjList[i].firstEdge = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}
void insertEdge(ListGraph graph, Edge edge) {
	/* 插入邊<v1,v2> */
    AdjVNodePtr newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
    newNode->adjVertex = edge->v2;
    newNode->next = graph->adjList[edge->v1].firstEdge;
    graph->adjList[edge->v1].firstEdge = newNode;
	/* 插入邊<v2,v1> */
    newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
    newNode->adjVertex = edge->v1;
    newNode->next = graph->adjList[edge->v2].firstEdge;
    graph->adjList[edge->v2].firstEdge = newNode;
}
ListGraph buildListGraph() {
    Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
    int vertexNum;
    scanf("%d", &vertexNum);
    ListGraph graph = createListGraph(vertexNum);
    scanf("%d", &graph->edgeNum);
    for (int i = 0;i < graph->edgeNum;i++) {
        scanf("%d%d", &edge->v1, &edge->v2);
        insertEdge(graph, edge);
    }
    return graph;
}
           

深度優先搜尋BFS和列印鄰接表圖

/* 隊列及相關操作 */
typedef struct QueueNode {
    int* data;
    int front, rear;
    int maxSize;
}*Queue;
Queue createQueue(int maxSize) {
    Queue queue = (Queue)malloc(sizeof(struct QueueNode));
    queue->maxSize = maxSize;
    queue->data = (int*)malloc(sizeof(int) * queue->maxSize);
    queue->front = queue->rear = 0;
    return queue;
}
int isFull(Queue queue) {
    return queue->front == (queue->rear + 1) % queue->maxSize;
}
int isEmpty(Queue queue) {
    return queue->front == queue->rear;
}
void addQueue(Queue queue, int data) {
    if (isFull(queue))
        return;
    queue->data[queue->rear] = data;
    queue->rear = (queue->rear + 1) % queue->maxSize;
}
int deleteQueue(Queue queue) {
    if (isEmpty(queue))
        return -1;
    int data = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->maxSize;
    return data;
}
/* 深度優先搜尋 */
void BFS(ListGraph graph, Vertex start) {
    Queue queue = createQueue(graph->vertexNum);
    printf("%d ", start);
    graph->visited[start] = 1;
    addQueue(queue, start);
    Vertex v;
    while (!isEmpty(queue)) {
        v = deleteQueue(queue);
        for (AdjVNodePtr w = graph->adjList[v].firstEdge;w;w = w->next) {
            if (!graph->visited[w->adjVertex]) {
                printf("%d ", w->adjVertex);
                graph->visited[w->adjVertex] = 1;
                addQueue(queue, w->adjVertex);
            }
        }
    }
}
/* 列印圖 */
void printGraph(ListGraph graph) {
    for (int i = 0;i < graph->vertexNum;i++) {
        printf("%d ", i);
        for (AdjVNodePtr w = graph->adjList[i].firstEdge;w;w = w->next)
            w->next == NULL ? printf("%d\n", w->adjVertex) : printf("%d ", w->adjVertex);
    }
}
           

主函數

int main() {
    ListGraph graph = buildListGraph();
    printGraph(graph);
    BFS(graph, 0);
    system("pause");
    return 0;
}
           

運作結果圖