建立图的存储结构（图的类型是有向图、无向图、有向网、无向网，），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵，邻接表等。可以实现图的某种功能，比如（最短路径等）C++实现

以下是有向图、无向图、有向网、无向网的存储结构和实现代码：

## 有向图存储结构及实现代码

### 邻接矩阵

const int MAXN = 100;

struct Graph {
    int n;
    int matrix[MAXN][MAXN];
};

void init(Graph &g, int n) {
    g.n = n;
    memset(g.matrix, 0, sizeof(g.matrix));
}

void addEdge(Graph &g, int u, int v) {
    g.matrix[u][v] = 1;
}

void printAdjMatrix(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

### 邻接表

struct Edge {
    int to, next;
};

const int MAXN = 100;

struct Graph {
    int n, m;
    Edge edges[MAXN];
    int head[MAXN], edgeCnt;
};

void init(Graph &g, int n) {
    g.n = n;
    g.m = 0;
    memset(g.head, -1, sizeof(g.head));
    g.edgeCnt = 0;
}

void addEdge(Graph &g, int u, int v) {
    g.edges[g.edgeCnt].to = v;
    g.edges[g.edgeCnt].next = g.head[u];
    g.head[u] = g.edgeCnt++;
}

void printAdjList(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        cout << i << ": ";
        for (int j = g.head[i]; j != -1; j = g.edges[j].next) {
            cout << g.edges[j].to << " ";
        }
        cout << endl;
    }
}

## 无向图存储结构及实现代码

### 邻接矩阵

const int MAXN = 100;

struct Graph {
    int n;
    int matrix[MAXN][MAXN];
};

void init(Graph &g, int n) {
    g.n = n;
    memset(g.matrix, 0, sizeof(g.matrix));
}

void addEdge(Graph &g, int u, int v) {
    g.matrix[u][v] = 1;
    g.matrix[v][u] = 1;
}

void printAdjMatrix(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            cout << g.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

### 邻接表

struct Edge {
    int to, next;
};

const int MAXN = 100;

struct Graph {
    int n, m;
    Edge edges[MAXN * 2];
    int head[MAXN], edgeCnt;
};

void init(Graph &g, int n) {
    g.n = n;
    g.m = 0;
    memset(g.head, -1, sizeof(g.head));
    g.edgeCnt = 0;
}

void addEdge(Graph &g, int u, int v) {
    g.edges[g.edgeCnt].to = v;
    g.edges[g.edgeCnt].next = g.head[u];
    g.head[u] = g.edgeCnt++;
    g.edges[g.edgeCnt].to = u;
    g.edges[g.edgeCnt].next = g.head[v];
    g.head[v] = g.edgeCnt++;
}

void printAdjList(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        cout << i << ": ";
        for (int j = g.head[i]; j != -1; j = g.edges[j].next) {
            cout << g.edges[j].to << " ";
        }
        cout << endl;
    }
}

## 有向网存储结构及实现代码

### 邻接矩阵

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

struct Graph {
    int n;
    int matrix[MAXN][MAXN];
};

void init(Graph &g, int n) {
    g.n = n;
    memset(g.matrix, INF, sizeof(g.matrix));
    for (int i = 0; i < n; i++) {
        g.matrix[i][i] = 0;
    }
}

void addEdge(Graph &g, int u, int v, int w) {
    g.matrix[u][v] = w;
}

void printAdjMatrix(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            if (g.matrix[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << g.matrix[i][j] << " ";
            }
        }
        cout << endl;
    }
}

### 邻接表

struct Edge {
    int to, w, next;
};

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

struct Graph {
    int n, m;
    Edge edges[MAXN];
    int head[MAXN], edgeCnt;
};

void init(Graph &g, int n) {
    g.n = n;
    g.m = 0;
    memset(g.head, -1, sizeof(g.head));
    g.edgeCnt = 0;
}

void addEdge(Graph &g, int u, int v, int w) {
    g.edges[g.edgeCnt].to = v;
    g.edges[g.edgeCnt].w = w;
    g.edges[g.edgeCnt].next = g.head[u];
    g.head[u] = g.edgeCnt++;
}

void printAdjList(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        cout << i << ": ";
        for (int j = g.head[i]; j != -1; j = g.edges[j].next) {
            cout << g.edges[j].to << "(" << g.edges[j].w << ")" << " ";
        }
        cout << endl;
    }
}

## 无向网存储结构及实现代码

### 邻接矩阵

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

struct Graph {
    int n;
    int matrix[MAXN][MAXN];
};

void init(Graph &g, int n) {
    g.n = n;
    memset(g.matrix, INF, sizeof(g.matrix));
    for (int i = 0; i < n; i++) {
        g.matrix[i][i] = 0;
    }
}

void addEdge(Graph &g, int u, int v, int w) {
    g.matrix[u][v] = w;
    g.matrix[v][u] = w;
}

void printAdjMatrix(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            if (g.matrix[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << g.matrix[i][j] << " ";
            }
        }
        cout << endl;
    }
}

### 邻接表

struct Edge {
    int to, w, next;
};

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

struct Graph {
    int n, m;
    Edge edges[MAXN * 2];
    int head[MAXN], edgeCnt;
};

void init(Graph &g, int n) {
    g.n = n;
    g.m = 0;
    memset(g.head, -1, sizeof(g.head));
    g.edgeCnt = 0;
}

void addEdge(Graph &g, int u, int v, int w) {
    g.edges[g.edgeCnt].to = v;
    g.edges[g.edgeCnt].w = w;
    g.edges[g.edgeCnt].next = g.head[u];
    g.head[u] = g.edgeCnt++;
    g.edges[g.edgeCnt].to = u;
    g.edges[g.edgeCnt].w = w;
    g.edges[g.edgeCnt].next = g.head[v];
    g.head[v] = g.edgeCnt++;
}

void printAdjList(Graph &g) {
    for (int i = 0; i < g.n; i++) {
        cout << i << ": ";
        for (int j = g.head[i]; j != -1; j = g.edges[j].next) {
            cout << g.edges[j].to << "(" << g.edges[j].w << ")" << " ";
        }
        cout << endl;
    }
}

## 最短路径算法实现

以下是使用 Dijkstra 算法计算有向网的最短路径的实现代码：

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w, next;
};

struct Graph {
    int n, m;
    Edge edges[MAXN * 2];
    int head[MAXN], edgeCnt;
};

void init(Graph &g, int n) {
    g.n = n;
    g.m = 0;
    memset(g.head, -1, sizeof(g.head));
    g.edgeCnt = 0;
}

void addEdge(Graph &g, int u, int v, int w) {
    g.edges[g.edgeCnt].to = v;
    g.edges[g.edgeCnt].w = w;
    g.edges[g.edgeCnt].next = g.head[u];
    g.head[u] = g.edgeCnt++;
}

void dijkstra(Graph &g, int s, int dist[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    memset(dist, INF, sizeof(int) * g.n);
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (int i = g.head[u]; i != -1; i = g.edges[i].next) {
            int v = g.edges[i].to;
            int w = g.edges[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    Graph g;
    init(g, 5);
    addEdge(g, 0, 1, 10);
    addEdge(g, 0, 3, 30);
    addEdge(g, 0, 4, 100);
    addEdge(g, 1, 2, 50);
    addEdge(g, 2, 4, 10);
    addEdge(g, 3, 2, 20);
    addEdge(g, 3, 4, 60);

    int dist[MAXN];
    dijkstra(g, 0, dist);

    for (int i = 0; i < g.n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}