python的一些问题

图的创建及输出（要求：所有图的创建及输出，即无向图、有向图、无向网、有向网）；
图的创建及遍历（要求：DFS和BFS）；
在图创建的基础上实现图的基本运算（参考教材相关实例，编程能力强的同学可做图的相关应用算法）；
有序表的二分查找（要求：递归和非递归两种方式实现；设计相应的查找成功和查找不成功的测试案例；输出比较元素和比较次数）

以下是使用Python实现图的创建、遍历和基本运算的示例代码：

# 图的创建及输出
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, src, dest):
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1

    def print_graph(self):
        for row in self.adj_matrix:
            print(row)


# 图的遍历（DFS和BFS）
def dfs(graph, start, visited):
    visited[start] = True
    print(start, end=" ")

    for i in range(graph.vertices):
        if graph.adj_matrix[start][i] == 1 and not visited[i]:
            dfs(graph, i, visited)


def bfs(graph, start):
    visited = [False] * graph.vertices
    queue = []

    visited[start] = True
    queue.append(start)

    while queue:
        vertex = queue.pop(0)
        print(vertex, end=" ")

        for i in range(graph.vertices):
            if graph.adj_matrix[vertex][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)


# 图的基本运算
def get_indegree(graph, vertex):
    indegree = 0
    for i in range(graph.vertices):
        if graph.adj_matrix[i][vertex] == 1:
            indegree += 1
    return indegree


def get_outdegree(graph, vertex):
    outdegree = 0
    for i in range(graph.vertices):
        if graph.adj_matrix[vertex][i] == 1:
            outdegree += 1
    return outdegree


# 创建一个无向图并输出
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

print("无向图的邻接矩阵：")
g.print_graph()

# DFS遍历无向图
print("DFS遍历无向图：")
visited = [False] * g.vertices
dfs(g, 0, visited)
print()

# BFS遍历无向图
print("BFS遍历无向图：")
bfs(g, 0)
print()

# 获取无向图中某个顶点的入度和出度
vertex = 2
print(f"顶点{vertex}的入度为：{get_indegree(g, vertex)}")
print(f"顶点{vertex}的出度为：{get_outdegree(g, vertex)}")
对于有向图和带权图的创建和操作，可以根据需要进行相应的修改和扩展。

至于有序表的二分查找，以下是使用递归和非递归两种方式实现的示例代码：

# 递归实现有序表的二分查找
def binary_search_recursive(arr, low, high, target):
    if low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search_recursive(arr, mid + 1, high, target)
        else:
            return binary_search_recursive(arr, low, mid - 1, target)
    else:
        return -1


# 非递归实现有序表的二分查找
def binary_search_iterative(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1


# 测试有序表的二分查找
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 12

# 递归方式查找
index_recursive = binary_search_recursive(arr, 0, len(arr) - 1, target)
if index_recursive != -1:
    print(f"递归方式：元素{target}在索引{index_recursive}处找到")
else:
    print(f"递归方式：元素{target}未找到")

# 非递归方式查找
index_iterative = binary_search_iterative(arr, target)
if index_iterative != -1:
    print(f"非递归方式：元素{target}在索引{index_iterative}处找到")
else:
    print(f"非递归方式：元素{target}未找到")

以上代码演示了如何创建图、进行遍历和基本运算，以及如何实现有图的相关应用算法。以下是一个示例，展示如何使用图来实现最短路径算法（Dijkstra算法）：

import sys

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, src, dest, weight):
        self.adj_matrix[src][dest] = weight
        self.adj_matrix[dest][src] = weight

    def dijkstra(self, src):
        visited = [False] * self.vertices
        distance = [sys.maxsize] * self.vertices
        distance[src] = 0

        for _ in range(self.vertices):
            min_distance = sys.maxsize
            min_vertex = -1

            for v in range(self.vertices):
                if not visited[v] and distance[v] < min_distance:
                    min_distance = distance[v]
                    min_vertex = v

            visited[min_vertex] = True

            for v in range(self.vertices):
                if (
                    self.adj_matrix[min_vertex][v] > 0
                    and not visited[v]
                    and distance[v] > distance[min_vertex] + self.adj_matrix[min_vertex][v]
                ):
                    distance[v] = distance[min_vertex] + self.adj_matrix[min_vertex][v]

        return distance


# 创建一个有向网并输出
g = Graph(6)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 7)
g.add_edge(2, 4, 3)
g.add_edge(3, 4, 2)
g.add_edge(3, 5, 1)
g.add_edge(4, 5, 5)

print("有向网的邻接矩阵：")
for row in g.adj_matrix:
    print(row)

# 使用Dijkstra算法计算最短路径
src_vertex = 0
distances = g.dijkstra(src_vertex)

print(f"从顶点{src_vertex}到其他顶点的最短路径：")
for v in range(g.vertices):
    print(f"顶点{src_vertex}到顶点{v}的最短距离为：{distances[v]}")

以上代码演示了如何使用图来实现最短路径算法（Dijkstra算法）。你可以根据需要进行修改和扩展，实现其他图的相关应用算法。

【由 http://www.gpt100.chat/ 生成,人工整理】

这篇博客: 【4月第二周学习记录】数据结构与算法王卓-第六章图-图的遍历（邻接矩阵与邻接表，DFS与BFS）中的 表示图的深度优先搜索遍历） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
数据结构与算法王卓-习题-第六章图-采用邻接矩阵表示图的深度优先搜索遍历(DFS)算法_Finale_R的博客-CSDN博客目录算法描述算法预期效果重难点思路个人解法总结测试样例与输出算法描述创建图的邻接矩阵, 并输出dfs深度优先搜索遍历结果算法预期效果依次输入顶点数，边数，顶点V1~Vn，边A1~An，根据输入的顶点与边的关系，输出形如右边的邻接矩阵，接着使用DFS进行深度优先遍历，输出所有结点。效果一：输出形如右边的邻接矩阵效果二：输出类似右下角的遍历结果重难点个人认为难点一是理解递归的结构，以及如何回退；难点二是visited数组如何声明与引用思路.https://blog.csdn.net/weixin_42189468/article/details/124084244?spm=1001.2014.3001.5501

以下回答由chatgpt基于相关博客总结生成:

问题解答：

创建并输出图形，包括无向图、有向图、无向网和有向网：

无向图（包括邻接矩阵和邻接表两种表示方法）
邻接矩阵方式：

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000;
int n, m;
int g[MAXN][MAXN];

int main(){
    cin >> n >> m;
    memset(g, 0, sizeof(g)); //初始化全局数组全部为0
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
        g[b][a] = 1; //无向图定义是双向的
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << g[i][j] << " ";
        }
        cout << endl; //每输出一行要换行
    }
    return 0;
}

邻接表方式：

#include<iostream>
#include<vector>
using namespace std;

const int MAXN = 1000;
int n, m;
vector<int> adj[MAXN]; //使用vector类型数组定义邻接表

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a); //双向定义，两个端点同时作为vector数组的下标
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < adj[i].size(); j++){ //遍历每个vector下的数值
            cout << adj[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

有向图（同样包括邻接矩阵和邻接表两种表示方法，此处不赘述）
无向网和有向网的创建和输出方式与无向图和有向图类似，只是需要把原本为0的点更改为一个较大的值，如本例中取10000作为不连通的大值：
无向网：

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000;
const int INF = 10000; //定义一个极大值
int n, m;
int g[MAXN][MAXN];

int main(){
    cin >> n >> m;
    memset(g, INF, sizeof(g)); //初始化全局数组全部为INF
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = w;
        g[b][a] = w; //无向网定义是双向的
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(g[i][j] == INF){ //如果两点不连通
                cout << "INF" << " ";
            }
            else{
                cout << g[i][j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

有向网：

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000;
const int INF = 10000; //定义一个极大值
int n, m;
int g[MAXN][MAXN];

int main(){
    cin >> n >> m;
    memset(g, INF, sizeof(g)); //初始化全局数组全部为INF
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = w;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(g[i][j] == INF){ //如果两点不连通
                cout << "INF" << " ";
            }
            else{
                cout << g[i][j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

图的遍历，包括DFS和BFS：

DFS： DFS使用递归或栈的方式遍历图中每一个节点，依次访问每个可达节点，直到所有节点都被访问过为止。以下给出DFS的递归代码实现：

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000;
bool visited[MAXN] = {false}; //visited数组初始全部为false
int n, m;
int g[MAXN][MAXN];

void DFS(int u){
    visited[u] = true;
    for(int v = 0; v < n; v++){
        if(g[u][v] != 0 && !visited[v]){ //如果两点连通并且未访问
            DFS(v);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(g, 0, sizeof(g));
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
        g[b][a] = 1;
    }

    for(int i = 0; i < n; i++){
        if(!visited[i]){ //如果该点未被访问，从该点开始访问
            DFS(i);
        }
    }

    return 0;
}

BFS: BFS使用队列的方式，按层遍历图中每一个节点，依次访问每个可达节点，直到所有节点都被访问过为止，以下给出BFS的代码实现：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1000;
bool visited[MAXN] = {false}; //visited数组初始全部为false
int n, m;
int g[MAXN][MAXN];

void BFS(int u){
    queue<int> q; //使用队列
    q.push(u);
    visited[u] = true;
    while(!q.empty()){
        int front = q.front();
        q.pop();
        for(int v = 0; v < n; v++){
            if(g[front][v] != 0 && !visited[v]){ //如果两点连通并且沿路访问的点未访问过
                q.push(v);
                visited[v] = true;
            }
        }
    }
}

int main(){
    cin >> n >> m;
    memset(g, 0, sizeof(g));
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
        g[b][a] = 1;
    }

    for(int i = 0; i < n; i++){
        if(!visited[i]){ //如果该点未被访问，从该点开始BFS
            BFS(i);
        }
    }

    return 0;
}

图的基本运算：

图的求连通分量：一个无向图G连通，则G的极大连通子图称为G的连通分量。

在无向图中，我们可以直接使用BFS或DFS进行连通性判断，遍历过程中只要发现有未访问过的点就从该点开始进行遍历