C語言基礎總結思維導圖 - 小K之心有猛虎的個人空間 - 詳情 - 1024程序員節,c語言,Graph,i++,鄰接表,JavaScript,前端開發網絡安全俠博客

C語言需要掌握的基礎知識點之圖

圖是一種非常重要的非線性數據結構，由頂點的集合和頂點之間邊的集合組成。以下是C語言中圖的詳細介紹和實現。

圖的基本概念

圖的定義
頂點（Vertex）：圖的基本單元
邊（Edge）：頂點之間的連接
有向圖：邊有方向
無向圖：邊沒有方向
權重圖：邊帶有權值

圖的表示方法

鄰接矩陣

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX  // 表示無窮大

typedef struct Graph {
    int numVertices;
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

// 初始化圖
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    
    // 初始化鄰接矩陣
    for(int i = 0; i < vertices; i++) {
        for(int j = 0; j < vertices; j++) {
            if(i == j)
                graph->adjacencyMatrix[i][j] = 0;  // 對角線為0
            else
                graph->adjacencyMatrix[i][j] = INF; // 初始為無窮大
        }
    }
    return graph;
}

// 添加邊（無向圖）
void addEdgeUndirected(Graph* graph, int src, int dest, int weight) {
    graph->adjacencyMatrix[src][dest] = weight;
    graph->adjacencyMatrix[dest][src] = weight;
}

// 添加邊（有向圖）
void addEdgeDirected(Graph* graph, int src, int dest, int weight) {
    graph->adjacencyMatrix[src][dest] = weight;
}

// 打印鄰接矩陣
void printGraph(Graph* graph) {
    printf("鄰接矩陣:\n");
    for(int i = 0; i < graph->numVertices; i++) {
        for(int j = 0; j < graph->numVertices; j++) {
            if(graph->adjacencyMatrix[i][j] == INF)
                printf("INF ");
            else
                printf("%3d ", graph->adjacencyMatrix[i][j]);
        }
        printf("\n");
    }
}

鄰接表

// 鄰接表節點
typedef struct AdjListNode {
    int dest;
    int weight;
    struct AdjListNode* next;
} AdjListNode;

// 鄰接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 圖結構（鄰接表）
typedef struct GraphList {
    int numVertices;
    AdjList* array;
} GraphList;

// 創建鄰接表節點
AdjListNode* createAdjListNode(int dest, int weight) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 創建圖（鄰接表）
GraphList* createGraphList(int vertices) {
    GraphList* graph = (GraphList*)malloc(sizeof(GraphList));
    graph->numVertices = vertices;
    
    graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
    
    for(int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加邊（無向圖-鄰接表）
void addEdgeListUndirected(GraphList* graph, int src, int dest, int weight) {
    // 添加從src到dest的邊
    AdjListNode* newNode = createAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    
    // 添加從dest到src的邊
    newNode = createAdjListNode(src, weight);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 添加邊（有向圖-鄰接表）
void addEdgeListDirected(GraphList* graph, int src, int dest, int weight) {
    AdjListNode* newNode = createAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// 打印鄰接表
void printGraphList(GraphList* graph) {
    printf("鄰接表:\n");
    for(int i = 0; i < graph->numVertices; i++) {
        AdjListNode* temp = graph->array[i].head;
        printf("頂點 %d: ", i);
        while(temp) {
            printf("-> %d(w:%d) ", temp->dest, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

圖的遍歷算法

深度優先搜索（DFS）

// DFS遞歸實現（鄰接矩陣）
void DFS_Matrix(Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("%d ", vertex);
    
    for(int i = 0; i < graph->numVertices; i++) {
        if(graph->adjacencyMatrix[vertex][i] != INF && !visited[i]) {
            DFS_Matrix(graph, i, visited);
        }
    }
}

void DFSTraversal(Graph* graph, int startVertex) {
    int visited[MAX_VERTICES] = {0};
    printf("DFS遍歷: ");
    DFS_Matrix(graph, startVertex, visited);
    printf("\n");
}

廣度優先搜索（BFS）

// 隊列實現
typedef struct Queue {
    int items[MAX_VERTICES];
    int front;
    int rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

int isEmpty(Queue* q) {
    return q->rear == -1;
}

void enqueue(Queue* q, int value) {
    if(q->rear == MAX_VERTICES - 1)
        printf("隊列已滿\n");
    else {
        if(q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue* q) {
    int item;
    if(isEmpty(q)) {
        printf("隊列為空\n");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if(q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// BFS遍歷（鄰接矩陣）
void BFS_Matrix(Graph* graph, int startVertex) {
    int visited[MAX_VERTICES] = {0};
    Queue* q = createQueue();
    
    visited[startVertex] = 1;
    enqueue(q, startVertex);
    
    printf("BFS遍歷: ");
    
    while(!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);
        
        for(int i = 0; i < graph->numVertices; i++) {
            if(graph->adjacencyMatrix[currentVertex][i] != INF && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
    printf("\n");
}

圖的最小生成樹算法

Prim算法

// Prim算法求最小生成樹
void primMST(Graph* graph) {
    int parent[MAX_VERTICES];    // 存儲MST
    int key[MAX_VERTICES];       // 權值數組
    int mstSet[MAX_VERTICES];    // 標記頂點是否在MST中
    
    // 初始化
    for(int i = 0; i < graph->numVertices; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }
    
    key[0] = 0;        // 從第一個頂點開始
    parent[0] = -1;    // 第一個頂點是根節點
    
    for(int count = 0; count < graph->numVertices - 1; count++) {
        // 選擇最小權值的頂點
        int min = INF, minIndex;
        for(int v = 0; v < graph->numVertices; v++) {
            if(!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        
        int u = minIndex;
        mstSet[u] = 1;
        
        // 更新相鄰頂點的權值
        for(int v = 0; v < graph->numVertices; v++) {
            if(graph->adjacencyMatrix[u][v] != INF && !mstSet[v] && 
               graph->adjacencyMatrix[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph->adjacencyMatrix[u][v];
            }
        }
    }
    
    // 打印MST
    printf("Prim算法 - 最小生成樹:\n");
    for(int i = 1; i < graph->numVertices; i++) {
        printf("%d - %d : %d\n", parent[i], i, graph->adjacencyMatrix[i][parent[i]]);
    }
}

Kruskal算法

// 邊的結構體
typedef struct Edge {
    int src, dest, weight;
} Edge;

// 並查集結構
typedef struct Subset {
    int parent;
    int rank;
} Subset;

// 查找根節點
int find(Subset subsets[], int i) {
    if(subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

// 合併兩個集合
void unionSets(Subset subsets[], int x, int y) {
    int rootX = find(subsets, x);
    int rootY = find(subsets, y);
    
    if(subsets[rootX].rank < subsets[rootY].rank)
        subsets[rootX].parent = rootY;
    else if(subsets[rootX].rank > subsets[rootY].rank)
        subsets[rootY].parent = rootX;
    else {
        subsets[rootY].parent = rootX;
        subsets[rootX].rank++;
    }
}

// 比較函數（用於排序）
int compareEdges(const void* a, const void* b) {
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;
    return edge1->weight - edge2->weight;
}

// Kruskal算法
void kruskalMST(Graph* graph) {
    int V = graph->numVertices;
    Edge result[V];  // 存儲MST結果
    int e = 0;       // 結果數組的索引
    int i = 0;       // 排序後邊的索引
    
    // 獲取所有邊
    Edge* edges = (Edge*)malloc(V * V * sizeof(Edge));
    int edgeCount = 0;
    
    for(int u = 0; u < V; u++) {
        for(int v = u + 1; v < V; v++) {
            if(graph->adjacencyMatrix[u][v] != INF) {
                edges[edgeCount].src = u;
                edges[edgeCount].dest = v;
                edges[edgeCount].weight = graph->adjacencyMatrix[u][v];
                edgeCount++;
            }
        }
    }
    
    // 按權值排序
    qsort(edges, edgeCount, sizeof(Edge), compareEdges);
    
    // 分配內存給並查集
    Subset* subsets = (Subset*)malloc(V * sizeof(Subset));
    
    // 初始化並查集
    for(int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    
    // 處理每條邊
    while(e < V - 1 && i < edgeCount) {
        Edge nextEdge = edges[i++];
        
        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);
        
        // 如果不形成環，加入MST
        if(x != y) {
            result[e++] = nextEdge;
            unionSets(subsets, x, y);
        }
    }
    
    // 打印MST
    printf("Kruskal算法 - 最小生成樹:\n");
    int minimumCost = 0;
    for(i = 0; i < e; i++) {
        printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("最小生成樹總權值: %d\n", minimumCost);
    
    free(edges);
    free(subsets);
}

最短路徑算法

Dijkstra算法

// Dijkstra算法求單源最短路徑
void dijkstra(Graph* graph, int src) {
    int dist[MAX_VERTICES];    // 最短距離數組
    int visited[MAX_VERTICES]; // 已訪問標記
    
    // 初始化
    for(int i = 0; i < graph->numVertices; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[src] = 0;
    
    for(int count = 0; count < graph->numVertices - 1; count++) {
        // 選擇最小距離的頂點
        int min = INF, minIndex;
        for(int v = 0; v < graph->numVertices; v++) {
            if(!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        
        int u = minIndex;
        visited[u] = 1;
        
        // 更新相鄰頂點的距離
        for(int v = 0; v < graph->numVertices; v++) {
            if(!visited[v] && graph->adjacencyMatrix[u][v] != INF && 
               dist[u] != INF && dist[u] + graph->adjacencyMatrix[u][v] < dist[v]) {
                dist[v] = dist[u] + graph->adjacencyMatrix[u][v];
            }
        }
    }
    
    // 打印最短路徑
    printf("Dijkstra算法 - 從頂點%d到各頂點的最短距離:\n", src);
    for(int i = 0; i < graph->numVertices; i++) {
        if(dist[i] == INF)
            printf("到頂點%d: 不可達\n", i);
        else
            printf("到頂點%d: %d\n", i, dist[i]);
    }
}

Floyd-Warshall算法

// Floyd-Warshall算法求所有頂點對最短路徑
void floydWarshall(Graph* graph) {
    int dist[MAX_VERTICES][MAX_VERTICES];
    int V = graph->numVertices;
    
    // 初始化距離矩陣
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            dist[i][j] = graph->adjacencyMatrix[i][j];
        }
    }
    
    // Floyd-Warshall算法核心
    for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                if(dist[i][k] != INF && dist[k][j] != INF && 
                   dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 打印結果
    printf("Floyd-Warshall算法 - 所有頂點對最短距離:\n");
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            if(dist[i][j] == INF)
                printf("INF ");
            else
                printf("%3d ", dist[i][j]);
        }
        printf("\n");
    }
}

拓撲排序

// 拓撲排序（鄰接表）
void topologicalSortUtil(GraphList* graph, int v, int visited[], int stack[], int* top) {
    visited[v] = 1;
    
    AdjListNode* temp = graph->array[v].head;
    while(temp != NULL) {
        int adjVertex = temp->dest;
        if(!visited[adjVertex]) {
            topologicalSortUtil(graph, adjVertex, visited, stack, top);
        }
        temp = temp->next;
    }
    
    stack[++(*top)] = v;
}

void topologicalSort(GraphList* graph) {
    int stack[MAX_VERTICES];
    int top = -1;
    int visited[MAX_VERTICES] = {0};
    
    for(int i = 0; i < graph->numVertices; i++) {
        if(!visited[i]) {
            topologicalSortUtil(graph, i, visited, stack, &top);
        }
    }
    
    printf("拓撲排序: ");
    while(top >= 0) {
        printf("%d ", stack[top--]);
    }
    printf("\n");
}

完整示例程序

int main() {
    int V = 5;  // 頂點數
    
    // 創建圖（鄰接矩陣）
    Graph* graph = createGraph(V);
    
    // 添加邊（無向圖）
    addEdgeUndirected(graph, 0, 1, 2);
    addEdgeUndirected(graph, 0, 3, 6);
    addEdgeUndirected(graph, 1, 2, 3);
    addEdgeUndirected(graph, 1, 3, 8);
    addEdgeUndirected(graph, 1, 4, 5);
    addEdgeUndirected(graph, 2, 4, 7);
    addEdgeUndirected(graph, 3, 4, 9);
    
    // 打印圖
    printGraph(graph);
    
    // 圖遍歷
    DFSTraversal(graph, 0);
    BFS_Matrix(graph, 0);
    
    // 最小生成樹
    primMST(graph);
    kruskalMST(graph);
    
    // 最短路徑
    dijkstra(graph, 0);
    floydWarshall(graph);
    
    // 創建有向圖進行拓撲排序
    GraphList* graphList = createGraphList(6);
    addEdgeListDirected(graphList, 5, 2, 1);
    addEdgeListDirected(graphList, 5, 0, 1);
    addEdgeListDirected(graphList, 4, 0, 1);
    addEdgeListDirected(graphList, 4, 1, 1);
    addEdgeListDirected(graphList, 2, 3, 1);
    addEdgeListDirected(graphList, 3, 1, 1);
    
    printGraphList(graphList);
    topologicalSort(graphList);
    
    // 釋放內存
    free(graph);
    
    return 0;
}

圖的應用場景

C語言基礎總結思維導圖 - 小K之心有猛虎的個人空間 -_#c語言

本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。

網絡安全俠博客

網絡安全俠博客

博客 / 詳情

C語言基礎總結思維導圖 - 小K之心有猛虎的個人空間 -

C語言需要掌握的基礎知識點之圖

圖的基本概念

圖的表示方法

圖的遍歷算法

圖的最小生成樹算法

最短路徑算法

完整示例程序

圖的應用場景

發佈評論

Product

Company

Support

Company

博客 / 詳情

C語言基礎總結思維導圖 - 小K之心有猛虎的個人空間 -

C語言需要掌握的基礎知識點之圖

圖的基本概念

圖的表示方法

圖的遍歷算法

圖的最小生成樹算法

最短路徑算法

完整示例程序

圖的應用場景

發佈 評論

發佈評論