1、可用顶点表示机场为航空网络建模。特别地，用有向边表示航班，该边从表示出发机场的顶点指向表示目的机场的顶点，我们每天可以为某个航线的所有航班建模。 用绘图软件画出表示航空公司航线的图模型(有向图箭头建议放置在线的中间)，并注明所用图的类型(参考表1)，其中每天有4个航班从波士顿到纽华克、2个航班从纽华克到波士顿、3个航班从纽华克到迈阿密、2个航班从迈阿密到纽华克、1个航班从纽华克到底特律、2个航班从底特律到纽华克、3个航班从纽华克到华盛顿、2个航班从华盛顿到纽华克、1个航班从华盛顿到迈阿密。 注： (a) 若城市之间有航班(任何方向)，则在表示城市的顶点之间有边。 (b) 对城市之间的每个航班(任何方向)来说，在表示城市的顶点之间有边。 (c) 对城市之间的每个航班(任何方向)来说，在表示城市的顶点之间有边，并且增加一个环，表示从迈阿密起飞和降落的特殊的观光旅行。 (d) 从表示航班出发城市的顶点到表示航班终止城市的顶点之间有边。 (e) 对每个航班，从表示出发城市的顶点到表示终止城市的顶点之间有边。 表1 图术语 类型 边 允许多重边 允许环 简单图 无向 否 否 多重图 无向 是 否 伪图 无向 是 是 简单有向图 有向 否 否 有向多重图 有向 是 是 混合图 有向和无向 是 是

以下是所需的图模型，为有向多重图，因为同一天可能有多个航班在同一条航线上。其中，红色箭头表示特殊的观光旅行。

波士顿 --> 纽华克 (4)
纽华克 --> 波士顿 (2)
纽华克 --> 迈阿密 (3)
迈阿密 --> 纽华克 (2)
纽华克 --> 底特律 (1)
底特律 --> 纽华克 (2)
纽华克 --> 华盛顿 (3)
华盛顿 --> 纽华克 (2)
华盛顿 --> 迈阿密 (1) 


相关问题

用数据结构c语言代码表示在邻接矩阵里两个顶点是否有边

假设邻接矩阵是一个二维数组，名为adjMatrix，其中adjMatrix[i][j]表示从顶点i到顶点j是否有边。如果adjMatrix[i][j]的值为1，则表示有边；如果为0，则表示没有边。

那么判断顶点i到顶点j是否有边的代码如下：

if(adjMatrix[i][j] == 1){
    printf("顶点%d到顶点%d有边\n", i, j);
}
else{
    printf("顶点%d到顶点%d没有边\n", i, j);
}

其中，printf语句可以根据实际情况进行修改，例如输出布尔值等。

采用邻接表表示法，构造无向网G；并从任意一个顶点出发，递归地深度优先遍历该图G

好的，那么让我们采用邻接表表示法来构造无向网G，并从任意一个顶点出发，递归地深度优先遍历该图G。

首先，我们需要定义一个邻接表的数据结构来表示无向图。邻接表的每个节点表示一个顶点，每个节点保存了该顶点相邻的所有顶点的信息（即边的信息）。我们可以使用链表来实现邻接表。具体的，我们可以定义一个结构体来表示每个节点，它包括两个部分：一个顶点标识符和一个指向链表头的指针。链表头节点包括了该顶点的度数和一个指向相邻顶点的指针数组。

下面是这个结构体的定义：

typedef struct node {
    int dest; // 相邻顶点的标识符
    int weight; // 边的权重
    struct node* next; // 指向下一个节点的指针
} Node;

typedef struct graph {
    int num_vertices; // 顶点数目
    Node** adj_lists; // 邻接表数组
} Graph;

接下来，我们可以使用这个数据结构来构造一个无向网。我们可以使用一个函数来初始化邻接表，并添加边。这个函数接受一个空的邻接表和一组边，然后在邻接表中添加这些边。具体的，我们可以遍历边数组，对于每条边，我们可以在邻接表中找到对应的两个节点，然后将它们相互连接起来。

下面是这个函数的代码实现：

void add_edge(Graph* graph, int src, int dest, int weight) {
    // 将 dest 添加到 src 的邻接表中
    Node* new_node = malloc(sizeof(Node));
    new_node->dest = dest;
    new_node->weight = weight;
    new_node->next = graph->adj_lists[src];
    graph->adj_lists[src] = new_node;

    // 将 src 添加到 dest 的邻接表中
    new_node = malloc(sizeof(Node));
    new_node->dest = src;
    new_node->weight = weight;
    new_node->next = graph->adj_lists[dest];
    graph->adj_lists[dest] = new_node;
}

Graph* create_graph(int num_vertices, int num_edges, int edges[][3]) {
    // 创建一个空的邻接表
    Graph* graph = malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    graph->adj_lists = malloc(sizeof(Node*) * num_vertices);

    for (int i = 0; i < num_vertices; i++) {
        graph->adj_lists[i] = NULL;
    }

    // 添加边
    for (int i = 0; i < num_edges; i++) {
        int src = edges[i][0];
        int dest = edges[i][1];
        int weight = edges[i][2];
        add_edge(graph, src, dest, weight);
    }

    return graph;
}

现在，我们已经构造好了一个无向网。接下来，我们可以使用递归的深度优先搜索算法来遍历这个网。具体的，我们从任意一个顶点开始，一直深入到没有未访问的邻居节点为止。为了避免重复访问节点，我们需要维护一个标记数组，记录每个节点是否已经被访问过。

下面是深度优先搜索算法的代码实现：

void dfs(Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    Node* adj_list = graph->adj_lists[vertex];
    while (adj_list != NULL) {
        int adj_vertex = adj_list->dest;
        if (visited[adj_vertex] == 0) {
            dfs(graph, adj_vertex, visited);
        }
        adj_list = adj_list->next;
    }
}

void depth_first_search(Graph* graph, int start_vertex) {
    int* visited = malloc(sizeof(int) * graph->num_vertices);
    for (int i = 0; i < graph->num_vertices; i++) {
        visited[i] = 0;
    }

    dfs(graph, start_vertex, visited);
}

现在，我们已经实现了一个完整的程序，可以用来构造无向网G，并从任意一个顶点出发，递归地深度优先遍历该网G。你可以调用 `create_graph()` 函数来构造一个网，然后调用 `depth_first_search()` 函数来遍历这个网。