有向图的邻接表的输出
时间: 2024-05-27 07:05:06 浏览: 14
有向图的邻接表是一种常用的图的表示方法,它通过使用一个数组来存储图中的顶点,并使用链表来存储每个顶点的邻接顶点。下面是一个示例来演示如何输出有向图的邻接表:
假设有以下有向图的邻接表表示:
```python
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['A']
}
```
我们可以使用循环遍历图的每个顶点,并输出其邻接顶点。具体步骤如下:
```python
for vertex, neighbors in graph.items():
print(vertex, '->', neighbors)
```
输出结果如下:
```
A -> ['B', 'C']
B -> ['C', 'D']
C -> ['D']
D -> ['A']
```
这样就可以输出有向图的邻接表了。
相关问题
c语言有向图邻接表输出及广度遍历
有向图的邻接表和无向图的邻接表类似,只是边表结点需要记录边的方向。下面是C语言有向图邻接表的输出及广度遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 顶点表结点
typedef struct {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 邻接表结构体
typedef struct {
AdjList vertices; // 顶点表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
int i;
G->vexnum = 0;
G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void AddArc(ALGraph *G, int v, int w) {
ArcNode *p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->next = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
G->arcnum++;
}
// 输出邻接表
void PrintGraph(ALGraph *G) {
int i;
ArcNode *p;
for (i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vertices[i].data);
p = G->vertices[i].firstarc;
while (p != NULL) {
printf("%d ", G->vertices[p->adjvex].data);
p = p->next;
}
printf("\n");
}
}
// 广度优先遍历
void BFS(ALGraph *G, int v) {
int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否被访问过
int queue[MAX_VERTEX_NUM]; // 队列
int front = 0, rear = 0;
ArcNode *p;
visited[v] = 1;
queue[rear++] = v;
while (front < rear) {
int u = queue[front++]; // 出队
printf("%d ", G->vertices[u].data);
p = G->vertices[u].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = 1;
queue[rear++] = w; // 入队
}
p = p->next;
}
}
}
int main() {
ALGraph G;
InitGraph(&G);
G.vexnum = 5;
G.arcnum = 7;
G.vertices[0].data = 0;
G.vertices[1].data = 1;
G.vertices[2].data = 2;
G.vertices[3].data = 3;
G.vertices[4].data = 4;
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 2);
AddArc(&G, 2, 0);
AddArc(&G, 2, 3);
AddArc(&G, 3, 3);
AddArc(&G, 4, 3);
printf("邻接表:\n");
PrintGraph(&G);
printf("广度遍历:\n");
BFS(&G, 2);
printf("\n");
return 0;
}
```
示例代码中的邻接表和无向图邻接表的定义和添加边的方法相同,区别在于有向图的边是有方向的,需要在添加边的时候指定边的起点和终点。在输出邻接表和广度遍历时,也需要考虑边的方向。
c++实现有向图邻接表
有向图邻接表的实现可以使用C++的STL库的vector和list容器来实现。vector用来存储图中所有结点的信息,list存储每个节点的邻接表信息。
下面是一个简单的有向图邻接表的实现:
```c++
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class Graph {
private:
int V; // 结点数量
vector<list<int>> adjList; // 邻接表
public:
Graph(int V) {
this->V = V;
adjList.resize(V);
}
// 添加一条边
void addEdge(int v, int w) {
adjList[v].push_back(w);
}
// 输出邻接表
void printGraph() {
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (auto it = adjList[i].begin(); it != adjList[i].end(); it++) {
cout << *it << " ";
}
cout << endl;
}
}
};
int main() {
Graph g(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);
g.printGraph();
return 0;
}
```
上述代码中,Graph类中使用vector来存储结点信息,list来存储每个结点的邻接表信息。addEdge()方法用于添加一条边,printGraph()方法用于输出邻接表。在main()函数中,我们创建了一个有向图,并添加了6条边,最后输出邻接表。