用c语言编程 1创建图的邻接矩阵和邻接表 2验证图的深度优先、广度优先遍历算法 3验证最短路径
这些是c++的代码不知是否满足你的要求。
1、邻接表表示的图中分别用DFS和BFS遍历#include #include #include using namespace std;\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 图的邻接表的结点struct Edge{ int dest; \\\/\\\/ 目标结点下标\\\/\\\/ int value; \\\/\\\/ 路径长度 Edge *link; \\\/\\\/ 下一个结点};\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 为图添加一条边\\\/\\\/ Input: edge - 欲加边的结点; dest - 目的结点\\\/\\\/ Output: edge - 加边后的结点\\\/\\\/ Tags: void AddEdge(Edge *&edge, int dest){ \\\/\\\/ 简单的链表操作 if (!edge) { edge = new Edge; edge->dest = dest; edge->link = 0; } else { Edge *tail = edge; while (tail->link) tail = tail->link; tail->link = new Edge; tail = tail->link; tail->dest = dest; tail->link = 0; }}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: Console下输入图的边\\\/\\\/ Input: Graph - 图; n - 图的结点的个数; EdgeNumber - 添加边的个数;\\\/\\\/ Output: Graph - 添加边后的图\\\/\\\/ Tags: 用户输入点对(a, b), 表示添加a->b的路径void Input(Edge **&graph, int n, int EdgeNumber){ int i = 0, a, b; for (i = 0; i < EdgeNumber; i++) { scanf(%d %d, &a, &b); \\\/\\\/ 用户输入起点终点 AddEdge(graph[a], b); \\\/\\\/ 添加a->b的边 }}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 深度优先搜索并输出\\\/\\\/ Input: Graph - 图; n - 图的结点的个数; StartEdge — 开始的结点;\\\/\\\/ Output: Console下输出遍历的顺序\\\/\\\/ Tags: 递归调用 _dfs过程、回溯算法void _dfs(Edge **&graph, bool *visited, int n, int index);void DFS(Edge **&graph, int n, int StartEdge){ bool *visited = new bool[n]; \\\/\\\/ 标记每个结点是否已访问 memset(visited, (int)false, sizeof(bool) * n); visited[StartEdge] = true; printf(start edge: %d\\\ , StartEdge); _dfs(graph, visited, n, StartEdge); visited[StartEdge] = false;}\\\/\\\/ _dfs过程：\\\/\\\/ Input: Graph - 图; n - 图的结点的个数; index - 当前的下标, visited - 记录结点是否已访问\\\/\\\/ Output: Console下输出遍历的顺序void _dfs(Edge **&graph, bool *visited, int n, int index){ int nIndex; \\\/\\\/ 下一个结点下标 Edge *edge = graph[index]; \\\/\\\/ 遍历用结点 while (edge) \\\/\\\/ 遍历所有的邻接结点 { nIndex = edge->dest; if (!visited[nIndex]) { visited[nIndex] = true; printf(%d\\\, nIndex); _dfs(graph, visited, n, nIndex); } edge = edge->link; }}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 广度优先搜索并输出\\\/\\\/ Input: Graph - 图; n - 图的结点的个数; StartEdge - 开始的结点\\\/\\\/ Output: Console下输出遍历的顺序\\\/\\\/ Tags: 需要一个队列记录所有的灰色结点void BFS(Edge **&graph, int n, int StartEdge){ bool *visited = new bool[n]; \\\/\\\/ 记录结点是否已访问 memset(visited, (int)false, sizeof(bool) * n); queue Q; \\\/\\\/ 记录准备访问的结点 Edge *edge; \\\/\\\/ 记录当前遍历的结点 int nIndex; \\\/\\\/ 记录下标 visited[StartEdge] = true; printf(start edge:%d\\\ , StartEdge); Q.push(StartEdge); while (!Q.empty()) { edge = graph[Q.front()]; while (edge) { nIndex = edge->dest; if (!visited[nIndex]) { visited[nIndex] = true; printf(%d\\\, nIndex); Q.push(nIndex); } edge = edge->link; } Q.pop(); }}int main(){ const int NODE_NUMBER = 7; \\\/\\\/ 10结点 const int EDGE_NUMBER = 11; \\\/\\\/ 10边 Edge **graph = new Edge *[NODE_NUMBER]; \\\/\\\/ 图 memset(graph, 0, sizeof(Edge *) * NODE_NUMBER); \\\/\\\/ 一开始没边 Input(graph, NODE_NUMBER, EDGE_NUMBER); \\\/\\\/ 输入边 printf(DFS:\\\ ); DFS(graph, NODE_NUMBER, 0); \\\/\\\/ 深度优先 printf(\\\ ); printf(BFS:\\\ ); BFS(graph, NODE_NUMBER, 0); \\\/\\\/ 广度优先 printf(\\\ ); return 0;}2、邻接矩阵表示的图中利用bellman-ford算法获得单点最短路#include #include using namespace std;#define INTEGER_INF 0xffff \\\/\\\/ 表示无穷大路径\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 邻接矩阵表示的图struct Graph{ int **value; \\\/\\\/ 权值 int number; \\\/\\\/ 结点个数};\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 初始化图\\\/\\\/ Input: number - 结点个数\\\/\\\/ Output: graph - 图void InitGraph(Graph &graph, int number){ int i, j; graph.value = new int *[number]; for (i = 0; i < number; i++) graph.value[i] = new int[number]; for (i = 0; i < number; i++) { for (j = 0; j < number; j++) { if (i == j) graph.value[i][j] = 0; else graph.value[i][j] = INTEGER_INF; } } graph.number = number;}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 析构图\\\/\\\/ Input: graph - 图\\\/\\\/ Output: graph - 析构后的图的壳子void FreeGraph(Graph &graph){ int i; for (i = 0; i < graph.number; i++) delete []graph.value[i]; delete []graph.value; graph.number = 0;}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: 用户在Console下输入图的边\\\/\\\/ Input: n - 边的数量\\\/\\\/ Output: graph - 加边后的图void AddEdge(Graph &graph, int n){ int i, a, b, v; for (i = 0; i < n; i++) { scanf(%d%d%d, &a, &b, &v); graph.value[a][b] = v; }}\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/\\\/ Description: BellmanFord 算法计算单源最短路\\\/\\\/ Input: graph - 图, index - 起点\\\/\\\/ Output: true - 存在最短路 且 Console 下输出起点到各个顶点的最短路\\\/\\\/ false - 不存在最短路(存在边权和为负的环路)bool BellmanFord(Graph &graph, int index){ int num = graph.number; \\\/\\\/ 结点个数 int *v = new int[num]; \\\/\\\/ 记录最短路 int i, j, t; \\\/\\\/ 设定初值 for (t = 1; t < num; t++) v[t] = INTEGER_INF; v[index] = 0; \\\/\\\/ 松弛 for (t = 0; t < num - 1; t++) \\\/\\\/ 循环i-1次 for (i = 0; i < num; i++) for(j = 0; j < num; j++) if (i != j && graph.value[i][j] != INTEGER_INF) \\\/\\\/ 如果两顶点间有路 if (v[j] > v[i] + graph.value[i][j]) \\\/\\\/ 松弛 v[j] = v[i] + graph.value[i][j]; \\\/\\\/ 判断是否存在边权和为负的环路 for (i = 0; i < num; i++) for (j = 0; j < num; j++) if (graph.value[i][j] != INTEGER_INF && v[j] > v[i] + graph.value[i][j]) return false; \\\/\\\/ 输出 for (t = 1; t < num; t++) printf(%d\\\, v[t]); return true;}int main(){ Graph graph; InitGraph(graph, 5); AddEdge(graph, 10); if (!BellmanFord(graph, 0)) printf(该图中存在边权和为负的环路!\\\ ); FreeGraph(graph); return 0;}
一个具有n个顶点和e条边的无向图，采用邻接表表示，表向量的大小为多少，所有顶点邻接表的结点总数为
表向量的大小为n，结点总数是2e，因为是无向图，所以一条边被存储了2次
n个顶点的无向图的邻接表最多有几个表结点
无向图就是不分方向的图 连接表的横列有N项，纵列也是N项 形成的N*N项每项都被称为边结点 每项都有纵横两个坐标，例如点（N,N-1），表示的就是从第N点向第N-1点有无路径。
由于有E条边，自然有E条路径，但是由于无向，=双向，所以要乘以二
哪位高手能具体解释一下在EIGRP和OSPF路由协议中邻接关系与邻居关系的区别。
尽量详细点。
谢谢。
。
我这里就说比较实在、比较俗一点吧，同时楼主也好理解一点。
一步一步的讲：如下一，如果网络中的路由器开启了，首先会发送hello报文，该报文中携带的有路由器的接口地址\\\/掩码、Area ID、Hello Interva、Dead Interval、接口认证等，然后路由器间根据这些参数开始相互协商，如果协商成功，便成为了邻居关系。
二，成为了邻居关系之后就要想办法成为邻接关系，因为不是每个邻居关系的路由器都会成为邻接关系的，特别是多址址广播网络。
总结一下，邻接关系的建立如下步骤。
1，失效状态 down， 表示该接口还未启用，不能收到任何信息。
2，初始化状态 Init，表示检测到了从邻居发来的hello报文了。
但还没建立双向通信。
（建立邻居后的路由器会发送hello报文给自己的邻居，hello信息包括路由器的router id、路由器的优先级等。
）3，双向通信状态 Two-way ，从邻居发过来的hello报文中，检测发现了自己的router id 号，如果是广播网络还需要选择DR、BDR ，再建立邻接关系，然后到下一步。
4，初始状态Exstart，确定两台路由器的主从关系，用做后面的数据库同步（即谁先发送LSA给另一方）5，状态 Exchange ，这一状态路由器会发送一个DD报文，用来描述他们的链路数据库等，既两台路由器开始准备同步，用来发现我路由器数据库里面缺什么，少什么的。
6，加载状态loading ，紧跟上一步，在进行了同步观察后，双方就知道自己的数据库里面的需求，即开始了开始了有关LSA 的请求。
7，完全邻接 full ，紧跟上一步，当发送了有关LSA的请求后，这一步就开始发送有关LSA的数据，一直到双方的LSA数据库同步。
此时，双方邻接关系完全形成。
个人描述，非复制的。
仅供参考。
