当前位置: 首页> 科技> 能源 > 网络营销策划有哪些_济南疫情最新情况风险区_竞价托管代运营_百度问一问客服人工在线咨询

网络营销策划有哪些_济南疫情最新情况风险区_竞价托管代运营_百度问一问客服人工在线咨询

时间:2025/7/11 20:28:14来源:https://blog.csdn.net/weixin_44929475/article/details/144497450 浏览次数:0次
网络营销策划有哪些_济南疫情最新情况风险区_竞价托管代运营_百度问一问客服人工在线咨询

        图(Graph)是一种非常灵活且强大的数据结构,用于表示实体之间的复杂关系。在图结构中,数据由一组节点(或称为顶点)和连接这些节点的边组成。图可以用于表示社交网络、交通网络、网络路由等场景。

1. 基本概念

  • 节点(Vertex):图中的一个点,代表一个对象或实体。

  • 边(Edge):连接两个节点的线,代表节点之间的关系。

  • 邻接(Adjacency):如果两个节点之间有边相连,则称这两个节点是邻接的。

  • 路径(Path):一系列相连的边,从一个节点开始,经过若干个中间节点,到达另一个节点。

  • 环(Cycle):起点和终点是同一个节点的路径。

  • 连通图(Connected Graph):图中任意两个节点之间都存在路径。

  • 强连通图(Strongly Connected Graph):有向图中,任意两个节点之间都存在有向路径。

  • 树(Tree):一种特殊的图,没有环,且任意两个节点之间只有一条路径。

2. 表示方法

2.1 邻接矩阵(Adjacency Matrix)

  • 使用一个二维数组来表示图,数组的行和列代表节点,元素值表示节点之间是否有边。

  • 适用于稠密图,即边的数量接近节点数量平方的图。

2.2 邻接表(Adjacency List)

  • 使用一个链表数组来表示图,每个链表包含与该节点相连的所有节点。

  • 适用于稀疏图,即边的数量远小于节点数量平方的图。

3. 遍历算法

3.1 深度优先搜索(Depth-First Search, DFS)

  • 类似于树的前序遍历,使用栈(递归或显式栈)来实现。

  • 从任意节点开始,尽可能深地搜索图的分支。

 
public class GraphDFS {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表// 构造函数@SuppressWarnings("unchecked")public GraphDFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// DFS算法public void DFS(int v) {boolean visited[] = new boolean[V];// 调用递归的DFS函数DFSUtil(v, visited);}// 递归的DFS函数void DFSUtil(int v, boolean visited[]) {// 标记当前节点为已访问visited[v] = true;System.out.print(v + " ");// 递归访问所有未访问的邻接节点for (int i = 0; i < adj[v].size(); i++) {int n = adj[v].get(i);if (!visited[n])DFSUtil(n, visited);}}// 测试DFS算法public static void main(String[] args) {GraphDFS g = new GraphDFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("DFS starting from vertex 2 : ");g.DFS(2);}
}

3.2 广度优先搜索(Breadth-First Search, BFS)

  • 类似于树的层序遍历,使用队列来实现。

  • 从任意节点开始,逐层遍历图中的节点。

 
import java.util.*;public class GraphBFS {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表// 构造函数@SuppressWarnings("unchecked")public GraphBFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// BFS算法public void BFS(int s) {boolean visited[] = new boolean[V];// 创建一个队列用于BFSQueue<Integer> queue = new LinkedList<>();// 标记起始节点为已访问并入队visited[s] = true;queue.add(s);while (queue.size() != 0) {// 出队一个节点s = queue.poll();System.out.print(s + " ");// 访问其所有未访问的邻接节点for (int i = 0; i < adj[s].size(); ++i) {int n = adj[s].get(i);if (!visited[n]) {visited[n] = true;queue.add(n);}}}}// 测试BFS算法public static void main(String[] args) {GraphBFS g = new GraphBFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("BFS starting from vertex 2 : ");g.BFS(2);}
}

4. 算法应用

  1. 最短路径问题

    1. Dijkstra算法:适用于带有非负权重的图。

    2. Bellman-Ford算法:适用于带有负权重的图。

    3. Floyd-Warshall算法:计算图中所有节点对的最短路径。

  2. 最小生成树问题

    1. Kruskal算法:贪心算法,适用于边的集合是无序的。

    2. Prim算法:贪心算法,适用于节点的集合是无序的。

  3. 网络流问题

    1. Ford-Fulkerson方法:计算网络中的最大流。

    2. Edmonds-Karp算法:使用BFS来实现Ford-Fulkerson方法。

关键字:网络营销策划有哪些_济南疫情最新情况风险区_竞价托管代运营_百度问一问客服人工在线咨询

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: