Graphs

Question 1

Types of “graphs”

Answer 1

Undirected graphs
The edges between any two vertices in an “undirected graph” do not have a direction, indicating a two-way relationship.

Directed graphs
The edges between any two vertices in a “directed graph” graph are directional.

Weighted graphs
Each edge in a “weighted graph” has an associated weight. The weight can be of any metric, such as time, distance, size, etc.

Question 2

The Definition of “graph”

Answer 2

“Graph” is a non-linear data structure consisting of vertices and edges.

Question 3

Vertex

Answer 3

nodes such as A, B, and C are called vertices of the graph.

Question 4

Edge

Answer 4

The connection between two vertices are the edges of the graph.

Question 5

Path

Answer 5

the sequence of vertices to go through from one vertex to another.

Question 6

Path Length

Answer 6

the number of edges in a path

Question 7

Cycle

Answer 7

a path where the starting point and endpoint are the same vertex

Question 8

Negative Weight Cycle

Answer 8

In a “weighted graph”, if the sum of the weights of all edges of a cycle is a negative value, it is a negative weight cycle

Question 9

Connectivity

Answer 9

if there exists at least one path between two vertices, these two vertices are connected

Question 10

Degree of a Vertex

Answer 10

the term “degree” applies to unweighted graphs. The degree of a vertex is the number of edges connecting the vertex

Question 11

In-Degree

Answer 11

“in-degree” is a concept in directed graphs. If the in-degree of a vertex is d, there are d directional edges incident to the vertex.